具有凸资源消耗函数的最小化Makespan的平行机调度问题

作     者：李凯 史烨 马英 LI Kai;SHI Ye;MA Ying

作者机构：合肥工业大学管理学院安徽合肥230009 过程优化与智能决策教育部重点实验室安徽合肥230009 中国科学技术大学管理学院安徽合肥230026 

基　　金：国家自然科学基金资助项目(71101040 70871032 90924021) 安徽省自然科学基金资助项目(11040606Q27) 

出 版 物：《管理工程学报》 (Journal of Industrial Engineering and Engineering Management)

年 卷 期：2013年第27卷第1期

页      码：56-62页

摘      要：研究了一类资源受限的平行机调度问题,其中假定作业的处理时间是其消耗资源量的凸减函数,调度的目标是在限定资源总量的情况下最小化Makespan(最大完工时间)。给出了此类NP-hard问题的形式化描述。定义了关键机器与非关键机器,给出了非最优解必定存在非关键机器的论断。尽快缩短非关键机器与关键机器之间工作量的差距能够有效逼近最优解,从而构造了快速的模拟退火算法。设计了一个下界用于衡量解的精度,并用于构造模拟退火算法迭代结束条件。算法性能通过20000组随机数值算例进行了测试,实验结果表明所构造的模拟退火算法能够在0.1秒之内有效求解1000个作业的问题并将相对误差控制在0.01%以内。该算法体现出很高的精度和计算效率。

主 题 词：平行机调度 Makespan 资源分配 可控处理时间 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 08[工学] 070105[070105] 0701[理学-数学类] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3969/j.issn.1004-6062.2013.01.008

馆 藏 号：203278970...