在退化维修活动下具有多窗口及退化效应的单机排序问题

Single Machine Scheduling with Multiple Common Due-window Assignment and Aging Effect under a Deteriorating Maintenance Activity Consideration

【目的】对多窗口和具有退化效应与退化维护活动的单机排序问题进行求解。【方法】假设任务的实际加工时间是关于该任务加工位置的函数,一个窗口不能包含另一个窗口。由于机器存在退化效应,适时地对机器进行维护能提高机器的生产效率。一旦维护活动结束,机器恢复到最初状态,并且任务的退化效应更新,机器维护活动持续的时间取决于维护活动的开始时间。将所有任务分成若干个任务集,任务集个数已知,每一个任务集共用一个窗口。目标是得到每个任务集最优窗口的位置、大小和最优维护活动的位置及任务的最优加工顺序使得任务的提前惩罚费用、延误惩罚费用、窗口开始时间及宽度费用之和最小。【结果】证明了此问题可以通过转化为指派问题求得最优解。【结论】并给出一个多项式时间算法来解该问题。

[Purposes]It considers multiple common due-window assignment and single machine scheduling with a job-dependent aging effect and a deteriorating maintenance activity. [Methods]The processing time of a job is a function about its position and its aging factor in a sequence. Once the maintenance activity has been completed, the machine will revert to its initial condition and the aging effect will start anew, the maintenance duration depends on its starting time. All jobs were divided into some groups. Every group has a common due-window. The objective is to find the due-window position and size, the maintenance activity position and the joh sequence to minimize the total of earliness, tardiness, the starting time of due-window and the size of due-window. [Findings]It is proved that the optimal solution can be obtained by solving the assignment problem. [Conclusions]It introduces an algorithm to solve the problem, and prove that the problem can be solved in polynomial time.