大规模作业车间多瓶颈调度算法  

Multi-bottleneck scheduling algorithm for large-scale Job Shop

作　　者：翟颖妮[1] 孙树栋[1] 杨宏安[1] 牛刚刚[1] 袁宗寅[1] 

机构地区：[1]西北工业大学现代设计与集成制造技术教育部重点实验室,陕西西安710072

出　　处：《计算机集成制造系统》2011年第7期1486-1494,共9页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(50705076;50705077);国家863计划资助项目(2007AA04Z187);陕西省自然科学基础研究计划资助项目(2009JQ9002)~~

摘　　要：针对大规模作业车间调度问题,提出一种基于滚动窗分解的多瓶颈调度算法。该算法基于关键路径法进行多瓶颈机器的识别,沿时域将大规模调度问题分解为多个子问题进行求解。在子问题创建过程中,提出负荷均衡分布的规则,使得各工件在各子问题中的负荷均匀分布,以实现算法求解过程的稳定性;在子问题的求解过程中,遵循约束理论中瓶颈机主导非瓶颈机的原则,采用瓶颈工序最优化调度、非瓶颈工序采用分派规则快速调度的调度策略,提高算法的求解效率;通过相邻子问题间的工序衔接再优化过程,以及全局解评价子问题染色体适应度值策略,有效避免了子问题分解创建和求解过程的局限性,提高了算法的求解质量。仿真结果表明,该算法具有较佳的求解效率和质量。To solve Large-Scale Job Shop Scheduling Problems（LSJSSP）,a multi-bottleneck scheduling algorithm based on rolling horizon decomposition was proposed.This algorithm adopted critical path method to detect bottlenecks,and solved the LSJSSP by decomposing it into a series of sub-problems according to the process routines of the jobs.In the construction process of the sub-problems,the idea of load balanced distribution was proposed to distribute the load of each job in the sub-problems and to realize the stability of the solution process.In the solving process of the sub-problems.the bottleneck operations were scheduled by genetic algorithm,and the non-bottleneck operations were scheduled by dispatching rules according to the principle of ＂bottleneck machines lead non-bottleneck machines＂ in Theory of Constraints（TOC）,the solving efficiency was improved.Through re-optimization process for the overlapping operations in the adjacent sub-problems and the strategy of evaluating the chromosome＇s fitness by the global solution,limitations of the decomposition and solving process were avoided,and the solution quality was improved.Simulation results showed that the proposed algorithm for LSJSSP was with satisfactory solution efficiency and quality.

关 键 词：作业车间 调度算法 滚动窗 多瓶颈 关键路径 

分 类 号：F406.2[经济管理—产业经济]