| 具有凸资源消耗函数的最小化Makespan的平行机调度问题 |
| |
| 引用本文： | 李凯,史烨,马英.具有凸资源消耗函数的最小化Makespan的平行机调度问题[J].管理工程学报,2013,27(1):56-62. |
| |
| 作者姓名： | 李凯 史烨 马英 |
| |
| 作者单位： | 1. 合肥工业大学管理学院,安徽合肥230009;过程优化与智能决策教育部重点实验室,安徽合肥230009
2. 中国科学技术大学管理学院,安徽合肥,230026 |
| |
| 基金项目： | 国家自然科学基金资助项目，安徽省自然科学基金资助项目 |
| |
| 摘 要： | 研究了一类资源受限的平行机调度问题,其中假定作业的处理时间是其消耗资源量的凸减函数,调度的目标是在限定资源总量的情况下最小化Makespan(最大完工时间)。给出了此类NP-hard问题的形式化描述。定义了关键机器与非关键机器,给出了非最优解必定存在非关键机器的论断。尽快缩短非关键机器与关键机器之间工作量的差距能够有效逼近最优解,从而构造了快速的模拟退火算法。设计了一个下界用于衡量解的精度,并用于构造模拟退火算法迭代结束条件。算法性能通过20000组随机数值算例进行了测试,实验结果表明所构造的模拟退火算法能够在0.1秒之内有效求解1000个作业的问题并将相对误差控制在0.01%以内。该算法体现出很高的精度和计算效率。
|
| 关 键 词： | 平行机调度 Makespan 资源分配 可控处理时间 |
Parallel Machine Scheduling Problems with a Convex Resource Consumption Function to Minimize the Makespan |
| |
| LI Kai
,
SHI Ye
,
MA Ying.Parallel Machine Scheduling Problems with a Convex Resource Consumption Function to Minimize the Makespan[J].Journal of Industrial Engineering and Engineering Management,2013,27(1):56-62. |
| |
| Authors: | LI Kai SHI Ye MA Ying |
| |
| Institution: | 1,2(1.School of management,Hefei University of Technology,Hefei 230009,China;2.Key Laboratory of Process Optimization and Intelligent Decision-making,Ministry of Education,Hefei 230009,China;3.School of management,University of Science and Technology of China,Hefei 230026,China) |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
