加工时间依赖于资源消耗量的平行机调度问题  

Parallel machine scheduling problem with resource dependent processing times

作　　者：史烨[1,2] 李凯[1,3] 左春荣[1,3] 

机构地区：[1]合肥工业大学管理学院,合肥230009 [2]中国科学技术大学管理学院,合肥230026 [3]过程优化与智能决策教育部重点实验室,合肥230009

出　　处：《系统工程理论与实践》2012年第7期1485-1493,共9页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(71101040;70971035;90924021);安徽省自然科学基金(11040606Q27)

摘　　要：研究了一类平行机调度问题,其中假定作业加工时间是资源消耗量的线性减函数,调度的目标是在限定最大完工时间时最小化资源消耗总量.分析了对应单机问题的最优算法和下界构造方法,进而提出了两个优化策略用于构造模拟退火算法和禁忌搜索算法.考虑了多种最大完工时间限制情形,构造了大量随机实验数据,对算法解的精确度及计算效率进行了测试.实验表明所构造的模拟退火算法能够在合理的时间内提供高质量的满意解.We consider the parallel-machine scheduling problem under the consumption that the processing time of each job is a linear decreasing function of the resource consumed. The objective is to minimize the total amount of the consumed resources with the constraint that the makespan does not exceed a given limit. We analyze the optimal algorithm for the corresponding single-machine scheduling problem and the method to construct a lower bound. Two optimization strategies are proposed to design simulated annealing algorithm and tabu search algorithm. A large number of random instances with different characters are generated to examine the accuracy and efficiency of the algorithms. The computational results show that the presented simulated algorithm can yield high-quality solutions for the parallel machine scheduling problems with resource dependent processing times in a reasonable time.

关 键 词：平行机调度 资源分配 模拟退火 禁忌搜索 

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