大规模作业车间的瓶颈分解调度算法  

Scheduling algorithm based on bottleneck operations decomposition for large-scale Job Shop scheduling problems

作　　者：翟颖妮[1] 孙树栋[1] 王军强[1] 郭世慧[1] 

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

出　　处：《计算机集成制造系统》2011年第4期826-831,共6页Computer Integrated Manufacturing Systems

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

摘　　要：针对大规模作业车间生产调度问题,提出一种基于瓶颈工序分解的调度算法。该算法采用正交试验进行瓶颈设备的识别,在设备层分解的基础上进一步进行工序级的分解,将大规模调度问题分解为瓶颈工序集调度、上游非瓶颈工序集调度和下游非瓶颈工序集调度三个子问题,通过子问题的求解和协调获得原问题的解。该算法遵循约束理论中"瓶颈机主导非瓶颈机"的原则,抓住调度问题的关键因素,采用分而治之的调度策略,不仅较大程度地降低了原问题的计算规模和复杂度,还兼顾了求解的质量。仿真结果表明了该算法的优越性和可推广性。Aiming at large-scale Job Shop scheduling problems,a scheduling algorithm based on the bottleneck operations decomposition was proposed.In this algorithm,by the bottleneck was recognized by orthogonal experiment.Then,the operations decomposition was carried out,therefore the large-scale Job Shop scheduling problem was decomposed into three scheduling sub-problems：bottleneck-operations set,preceding-bottleneck-operations set,and following-bottleneck-operations set.The solution to the original problem was obtained by solving the sub-problems and coordinating the solutions of the sub-problems.According to the principle of ＂Bottleneck machines leads non-bottleneck machines＂ in Theory of Constraints（TOC）,this algorithm improved the computation efficiency and the quality of the solution by the decomposition strategy and the coordination techniques for the solution of the sub-problems.Simulation results showed the advantage and extensibility of proposed algorithm.

关 键 词：大规模作业车间 调度 瓶颈工序 正交试验 

分 类 号：TH166[机械工程—机械制造及自动化] TP391[自动化与计算机技术—计算机应用技术]