具有负载依赖型维护时长和弹性维护开始时刻的单机调度问题

考虑维护时长为负载依赖型且维护开始时刻具有一定弹性的单机调度问题,其中机器在加工过程中需要进行一次维护,维护的开始时刻是决策量且需位于一个事先给定的时间段内,维护时长依赖于机器维护前已加工工件的加工时长之和,目标是确定维护的开始时刻并安排所有工件的加工使得制造期最小化。对维护时长函数的导函数大于或等于1的情形,给出了一个最优调度方案。对维护时长函数的导函数小于1的情形,证明了任何非延迟调度算法的最坏情况界都不超过2,并证明了经典的LS算法、LPT算法和SPT算法及它们的一些变形算法的最坏情况界均为2。