| 分布式环境下批处理机调度启发式算法求解 |
| |
| 引用本文： | 李小林,杜冰,谭琦,陈华平.分布式环境下批处理机调度启发式算法求解[J].系统工程学报,2012,27(1):99-110. |
| |
| 作者姓名： | 李小林 杜冰 谭琦 陈华平 |
| |
| 作者单位： | 中国科学技术大学管理学院,安徽合肥,230026 |
| |
| 基金项目： | 创新研究群体科学基金资助项目(70821001);国家白然科学基金资助项目(71171184) |
| |
| 摘 要： | 将批处理机调度问题扩展到分布式环境下,提出了批调度问题的一个新模型.模型中,工件动态到达各批处理机,且在加工之前和之后需要有运输时间.证明了该模型是NP难的,并通过问题的一个下界来衡量各算法性能.给出了分布式环境下批分配的一个启发式算法AR(assignment rule)以及一个分批准则BR(batching rule),在此基础上对问题的求解提出了若干启发式算法.仿真实验表明各算法均可以对问题进行有效的求解,加入分批准则对于算法有进一步的优化作用.
|
| 关 键 词： | 批处理机 生产调度 分布式模型 启发式算法 |
Metaheuristics for scheduling batch processing machines in distributed environment |
| |
| LI Xiao-lin
,
DU Bing
,
TAN Qi
,
CHEN Hua-ping.Metaheuristics for scheduling batch processing machines in distributed environment[J].Journal of Systems Engineering,2012,27(1):99-110. |
| |
| Authors: | LI Xiao-lin DU Bing TAN Qi CHEN Hua-ping |
| |
| Institution: | (School of Management,University of Science and Technology of China,Hefei 230026,China) |
| |
| Abstract: | The problem of scheduling batch processing machines was extended to the distributed environment. In the problem,jobs had non-identical release time and the transportation time was considered before and after batch processing.The problem was shown to be strongly NP-hard thus a lower bound was presented to evaluate the performance of approximation algorithms.Several heuristics for the problem were proposed based on algorithm AR(Assignment Rule) and BR(Batching Rule).Computational experiments showed the effectiveness of the heuristics especially when the BR was used. |
| |
| Keywords: | batch processing machines production scheduling distributed model heuristic algorithms |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
