具有负载依赖型维护时长的平行机调度问题

Parallel Machine Scheduling Problem with Workload-dependent Maintenance Duration

本文考虑具有工具更换的平行机调度问题,机器的维护时长依赖于维护前的负载,目标为最小化时间表长.首先,基于维护时长函数为单调不减函数得到最优调度方案应有的两个性质——单台机器加工的工件个数最多相差一个;每台机器在最后一个维护间隔应尽可能多地加工工件.其次,对维护时长函数为凹函数、凸函数和线性函数的情况分别给出算法MNJF, SJF和SLE.最后,证明算法MNJF, SJF以及SLE均为对应情况的最优算法,且算法MNJF对于维护时长函数为线性函数的情况也是一种最优算法.

In this paper a parallel machine scheduling problem with tool changes, where the tool change durations are workload-dependent, is considered. The objective is to minimize the makespan. Firstly, based on the fact that the maintenance duration function is a monotone undiminished function, two properties of the optimal scheduling scheme are obtained: the difference between the numbers of job processed by each machine is at most one, and each machine in its last maintenance interval should process as many jobs as possible. Secondly, for each case that the maintenance duration function is concave, convex, or linear, a corresponding optimal optimal algorithm MNJF, SFF or SLE is presented respectively. Finally, it is proved that the algorithms MNJF, SJF and SLE are all optimal in the corresponding cases, and the algorithm MNJF is also optimal when the maintenance duration function is linear.