退化条件下具有维修活动的单机排序问题

The Problems of Single-machine Scheduling with Rate-modifying Activities Under Deterioration

在现实的环境中,工件的加工时间可能与其在机器上的开工时间有关,工件的开工时间越晚其加工时间越长,这种现象称为"退化效应"(Deteriorateing effect)。针对机器具有退化效应和维修活动(Rate-modifying activity,RMA)的单机排序模型,考虑一个序列无关的,在简单线性退化条件下工件的加工时间与工件所处的位置有关的,并且可以在任务序列中安排多个维修活动(RMAs)的单机极小化最大完工时间问题。在这一问题中,机器在加工过程中产生退化使效率降低;然而,对机器进行维修活动能使机器的加工效率得到恢复,从而能够使排在维修活动后的工件的加工时间缩短。在对本文问题的模型进行分析和适当的假设后,利用分组平衡原则,证明了当维修活动的次数确定时,最优排序满足分组平衡原则;最后,在满足一定的条件下,解决了是否安排维修活动、安排的次数以及安排在工件排序中的位置以便使最大完工时间最小这一问题,并提出了一个多项式最优算法。本文的结果推广和改进了已有文献中的结论。

In the real word, the processing time of a job may be dependent on its starting time in a schedule and the later a job starts, the longer it takes to process, this phenomenon is called ＂deteriorateing effect＂. Aiming at the single-machine scheduling model, which is the integration of scheduling models with deteriorateing effect and scheduling models with a rate-modifying activity（RMA） , we explore a sequence-independent, single processor makespan problem with position-dependent processing times and several rate-modifying activities. In the model, the machine deteriorates during the processing procedure making the efficiency of processing jobs lower. However, the rate-modifying activity restores the processing efficiency of the machine so that the processing times of the jobs scheduled after the RMAs is shortened. After the analysis of this problem model and appropriate assumptions, we prove that when determining the number of rate-modifying activities, the optimal scheduling to meet the group balance principle. Finally, we resolve the question of whether to arrange RMA, the times of RMAs, and the position of RMA in the scheduling in order to minimize the makespan under certain conditions and provide a polynomial-time optimal algorithm. The results of this paper generalize and improve the conclusions of the existing reference.