| 带机器准备时间的同类机调度问题的启发式算法 |
| |
| 引用本文： | 马英,杨善林,汤大为. 带机器准备时间的同类机调度问题的启发式算法[J]. 系统工程理论与实践, 2012, 32(9): 2022-2030. DOI: 10.12011/1000-6788(2012)9-2022 |
| |
| 作者姓名： | 马英 杨善林 汤大为 |
| |
| 作者单位： | 1. 合肥工业大学 管理学院, 合肥 230009;2. 过程优化与智能决策教育部重点实验室, 合肥 230009;3. Manchester Business School, University of Manchester, Manchester M15 6PB, UK |
| |
| 基金项目： | 国家自然科学基金(71101040);国家自然科学基金重点项目(71131002);安徽省自然科学基金(11040606Q27,1208085QG133) |
| |
| 摘 要： | 研究了带机器准备时间的同类机最大完工时间调度问题, 首先证明了工件互换的四个性质, 进而提出了一种启发式算法, 此算法以LPT算法得到的序列作为初始解, 利用互换性质重复对最大完工时间最大和最大完工时间最小的两台机器上的工件进行交换, 以提高解的质量. 实验结果证明了此算法的有效性.
|
| 关 键 词： | 同类机调度 机器准备时间 LPT |
| 收稿时间： | 2010-05-19 |
Heuristic algorithm for uniform-machine scheduling with machine release times |
| |
| MA Ying , YANG Shan-lin , TANG Da-wei. Heuristic algorithm for uniform-machine scheduling with machine release times[J]. Systems Engineering —Theory & Practice, 2012, 32(9): 2022-2030. DOI: 10.12011/1000-6788(2012)9-2022 |
| |
| Authors: | MA Ying YANG Shan-lin TANG Da-wei |
| |
| Affiliation: | 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. Manchester Business School, University of Manchester, Manchester M15 6PB, UK |
| |
| Abstract: | This paper considers a problem of uniform-machine scheduling with machine release times to minimize makespan.Firstly,four properties of swapping jobs are proposed.Then,based on the properties, a heuristic algorithm is presented,which takes the LPT schedule as its initial solution and improves the solution by repeatedly swapping the jobs between two machines with the maximal and minimal makespan. Finally,computational results show that the presented heuristic is efficient and effective. |
| |
| Keywords: | uniform-machine scheduling machine release times longest processing time |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《系统工程理论与实践》浏览原始摘要信息 |
|
点击此处可从《系统工程理论与实践》下载全文 |
|
