摘要
将批处理机调度问题扩展到分布式环境下,提出了批调度问题的一个新模型.模型中,工件动态到达各批处理机,且在加工之前和之后需要有运输时间.证明了该模型是NP难的,并通过问题的一个下界来衡量各算法性能.给出了分布式环境下批分配的一个启发式算法AR(assignment rule)以及一个分批准则BR(batching rule),在此基础上对问题的求解提出了若干启发式算法.仿真实验表明各算法均可以对问题进行有效的求解,加入分批准则对于算法有进一步的优化作用.
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.
出处
《系统工程学报》
CSCD
北大核心
2012年第1期99-110,共12页
Journal of Systems Engineering
基金
创新研究群体科学基金资助项目(70821001)
国家白然科学基金资助项目(71171184)
关键词
批处理机
生产调度
分布式模型
启发式算法
batch processing machines
production scheduling
distributed model
heuristic algorithms
