带有多个工期窗口及退化维护的单机排序问题

Single-machine Multiple Due-window Assignment and a Deteriorating Rate-modifying Activity

【目的】讨论带有多个工期窗口及退化维护的单机排序问题。【方法】工件的加工时间是一个和资源分配、工件在排序中的位置以及退化效应有关的凸函数。目标是确定多个最优工期窗口的位置和大小、指派给每个工期窗口的工件集合、分配给每个工件的资源、最优的维修位置和最优的工件排序,最小化提前、误工、工期窗口的开始时间、工期窗口的大小、资源分配、时间表长的总费用。【结果】证明了带有多个工期窗口及退化维护的单机排序问题仍然是多项式可解的。【结论】最优算法是可以在O(n4)时间内求出最优解。

[Purposes]It considers the multiple common due window assignment and single machine scheduling with a job-dependent aging effect and deteriorating maintenance activity. [Methods]It assumes that the processing time of a job is a convex function of the amount of a resource allocated to it, its position in the processing sequence, and its aging effect. The objective is to find the optimal due-window, the optimal maintenance position so as to minimize the total cost, which is a function of earliness, tardiness, due- window starting time, due-window size, resource consumption, makespan. [Findings]It shows that multiple due-window assignment and a deteriorating rate-modifying activity remains polynomial time solvable. [Conclusions]And it introduces an efficient O（n4） algorithm to solve the problem.