释放时间具有凸减函数约束的单机调度问题

Single machine scheduling problem with release dates under the constraint of convex decreasing functions

研究了作业释放时间具有凸减资源消耗函数约束的单机调度问题,调度的目标是在限定Makespan的条件下使得作业消耗资源总量最小化.对于此类强NP-hard问题,定义了作业右移和左移两种基本运算以及交换和插入两种邻域生成方式,并在此基础上构造了模拟退火算法.为评价算法的性能,将此问题松弛成指派问题,从而用匈牙利方法得到松弛问题的最优解,并进一步改进下界的质量.实验表明所构造的模拟退火算法能够在合理的时间内提供高质量的满意解.

This paper considers a single machine scheduling problem, in which the release dates of the jobs are convex decreasing functions of the consumed resource. The objective is minimizing the total resource consumption with a limited Makespan. For the NP-hard problem in the strong sense, two basic operators, left-move and right-move, and two neighborhood generation methods, insert and swap, are defined to build a simulated annealing algorithm. To evaluate the accuracy of the proposed algorithm, the problem is relaxed to an assignment problem to obtain a lower bound by Hungary method. The computational results show that the presented simulated annealing algorithm can yield high-quality solutions for the considered scheduling problem.