分布式环境下批处理机调度启发式算法求解  

Metaheuristics for scheduling batch processing machines in distributed environment

作　　者：李小林[1] 杜冰[1] 谭琦[1] 陈华平[1] 

机构地区：[1]中国科学技术大学管理学院,安徽合肥230026

出　　处：《系统工程学报》2012年第1期99-110,共12页Journal of Systems Engineering

基　　金：创新研究群体科学基金资助项目(70821001);国家白然科学基金资助项目(71171184)

摘　　要：将批处理机调度问题扩展到分布式环境下,提出了批调度问题的一个新模型.模型中,工件动态到达各批处理机,且在加工之前和之后需要有运输时间.证明了该模型是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.

关 键 词：批处理机 生产调度 分布式模型 启发式算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]