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

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

作　　者：李凯[1,2,3] 罗庆[1] 杨善林[1,2] 

机构地区：[1]合肥工业大学管理学院,合肥230009 [2]过程优化与智能决策教育部重点实验室,合肥230009 [3]武汉大学软件工程国家重点实验室,武汉430072

出　　处：《系统工程理论与实践》2013年第6期1516-1522,共7页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(71101040;71131002;71001032);安徽省自然科学基金(11040606Q27);高等学校博士学科点专项科研基金(20120111120013);武汉大学软件工程国家重点实验室开放基金(SKLSE2012-09-10)

摘　　要：研究了作业释放时间具有凸减资源消耗函数约束的单机调度问题,调度的目标是在限定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.

关 键 词：调度 单机 MAKESPAN 资源分配 释放时间 

分 类 号：O223[理学—运筹学与控制论] TP301[理学—数学]