基于TOC理论的大规模作业车间调度问题研究  

A Study of Large-scale Job Shop Scheduling Problem Based on TOC

作　　者：翟颖妮[1] 王军强[2] 褚崴[1] 刘昌军[1] 

机构地区：[1]西安建筑科技大学机电工程学院,西安710055 [2]西北工业大学现代设计与集成制造教育部重点实验室,西安710072

出　　处：《机械科学与技术》2015年第8期1222-1228,共7页Mechanical Science and Technology for Aerospace Engineering

基　　金：陕西省教育厅自然科学专项项目(2013JK1035);陕西省自然科学基础研究计划项目(2012JM7017);西安建筑科技大学校人才基金项目(DB06035)资助

摘　　要：针对大规模Job Shop调度问题,提出了一种基于TOC(theory of constraints)的免疫遗传算法。该算法依据TOC理论中瓶颈机约束生产系统性能的思想,利用瓶颈机器的特性,在染色体编码及遗传操作过程中,对瓶颈机与非瓶颈机采用不同的处理方式,以使瓶颈工序得到最优化调度。而非瓶颈工序在满足瓶颈工序的调度方案的基础上进行快速调度,降低大规模作业车间调度问题的复杂度,提高算法的求解效率。为提高算法求解质量,克服遗传算法的随机性及迭代退化问题,将TOC理论中的瓶颈机器拓展至瓶颈工件,提出候选瓶颈工件集及瓶颈工件的定义。通过对瓶颈机接种"瓶颈工件邻域对换"免疫算子,充分利用种群中个体的特征信息,辅助遗传算法的优化过程。仿真结果表明:瓶颈特征的应用以及免疫算子的融入是有效的,免疫遗传算法可以在较短的时间内求得令人满意的解。An immune genetic algorithm for a large-scale job shop scheduling problem is proposed based on the Theory of Constraints( TOC). According to the theory,bottleneck mechanisms constrain the performance of a manufacturing system,so we use an immune genetic algorithm to encode the bottleneck mechanisms and nonbottleneck mechanisms respectively. The bottleneck mechanisms are scheduled deeply,and the non-bottleneck mechanisms are scheduled quickly to enhance the computational efficiency of the algorithm. To do so,we define a set of candidate bottleneck jobs and add them to the bottleneck mechanisms according to the TOC. The characteristic information on chromosomes is used to assist the optimization of the immune genetic algorithm with the operation of interchanging the sequences of the job shop scheduling problem on the bottleneck mechanisms. The simulation results show that the applications of bottleneck mechanisms and immune operators are effective,and the immune genetic algorithm can obtain satisfactory solutions within acceptable time.

关 键 词：大规模 JOB Shop调度问题 瓶颈机器 瓶颈工件 

分 类 号：TB497[一般工业技术]