在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报 ›› 2025, Vol. 42 ›› Issue (5): 793-805.doi: 10.3969/j.issn.1005-3085.2025.05.001cstr: 32411.14.cjem.CN61-1269/O1.2025.05.001

• •    下一篇

工件可外包且加工时间可变的单机退化维护调度问题

张思显,  马  冉   

  1. 青岛理工大学管理工程学院，青岛  266520
  • 收稿日期:2023-02-11 接受日期:2023-09-18 出版日期:2025-10-15 发布日期:2025-12-15
  • 基金资助:
    国家自然科学基金 (12271295; 12371319)；山东省自然科学基金 (ZR2020MA028).

Study on Single-machine Problem with Variable Processing Time and Rejection and a Deteriorating Maintenance Activity

ZHANG Sixian,   MA Ran   

  1. School of Management Engineering, Qingdao University of Technology, Qingdao 266520
  • Received:2023-02-11 Accepted:2023-09-18 Online:2025-10-15 Published:2025-12-15
  • Supported by:
    The National Natural Science Foundation of China (12271295; 12371319); the Natural Science Foundation of Shandong Province (ZR2020MA028).

摘要：

研究了工件外包且机器带有退化维护活动的单机生产调度问题，并且考虑了学习效应与退化效应，工件的实际加工时间是一个关于该工件加工位置的函数。为了提高机器的生产效率，每台机器至多执行一次退化维护活动，执行退化维护活动的影响反映在工件处理时间的减少上，退化维护活动的维护时长是其开始时刻的线性非减函数。目标是得到退化维护活动最优的位置及调度的最优的加工顺序，使得调度的最大完工时间、总完工时间、总加权完工时间与外包所需支付的费用之和最小。当调度指标为最大完工时间与总完工时间时，分别提供了解决这两个问题的多项式时间算法。当调度指标为总加权完工时间时，引入了伪多项式时间算法来解决这个NP-难问题。

关键词: 调度, 学习效应, 退化效应, 退化维护活动, 外包

Abstract:

A single-machine production scheduling problem is addressed for jobs with outsourcing and machine with deteriorating maintenance activity. We consider the learning effect and the deteriorating effect. The actual processing time of a job is a function on its position. In order to improve the productivity of the machine, each machine has at most one deteriorating maintenance activity throughout the scheduling horizon, where the impact of performing deteriorating maintenance activities is reflected in the reduction of job processing time. The duration of the maintenance activity increases linearly with its starting time. The objective is to find the position of the maintenance activity and the most available processing order of the task such that the sum of the maximum, the total completion time, the total weighted completion time and the cost to be paid for outsourcing is minimized. When the scheduling measures are the makespan, total completion time, we provide polynomial time algorithms to solve these problems, respectively. When the scheduling measures is the total weighted completion time, we introduce pseudo-polynomial time algorithms to solve this NP-hard problem.

Key words: scheduling, learning effects, deteriorating effects, deteriorating maintenance activity, outsourcing

中图分类号: