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

翟颖妮; 王军强; 褚崴; 刘昌军

doi:10.13433/j.cnki.1003-8728.2015.0815

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

doi: 10.13433/j.cnki.1003-8728.2015.0815

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

基金项目:

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

详细信息

作者简介:
翟颖妮（1983-），讲师，博士，研究方向为计算机集成制造、约束理论等，zhaiyingni@gmail.com

计量
- 文章访问数: 173
- HTML全文浏览量: 18
- PDF下载量: 5
- 被引次数: 0
出版历程
- 收稿日期: 2013-11-12
- 刊出日期: 2015-08-05

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

1.
Department of Mechanical and Electronic Engineering, Xi'an University of Architechure and Technology, Xi'an 710055, China;
2.
The Ministry of Education Key Laboratory of Contemporary Design and Integrated Manufacturing Technology, Northwestern Polytechnical University, Xi'an 710072, China

摘要

摘要: 针对大规模Job Shop调度问题，提出了一种基于TOC（theory of constraints）的免疫遗传算法。该算法依据TOC理论中瓶颈机约束生产系统性能的思想，利用瓶颈机器的特性，在染色体编码及遗传操作过程中，对瓶颈机与非瓶颈机采用不同的处理方式，以使瓶颈工序得到最优化调度。而非瓶颈工序在满足瓶颈工序的调度方案的基础上进行快速调度，降低大规模作业车间调度问题的复杂度，提高算法的求解效率。为提高算法求解质量，克服遗传算法的随机性及迭代退化问题，将TOC理论中的瓶颈机器拓展至瓶颈工件，提出候选瓶颈工件集及瓶颈工件的定义。通过对瓶颈机接种“瓶颈工件邻域对换”免疫算子，充分利用种群中个体的特征信息，辅助遗传算法的优化过程。仿真结果表明：瓶颈特征的应用以及免疫算子的融入是有效的，免疫遗传算法可以在较短的时间内求得令人满意的解。
- 大规模 /
- Job Shop调度问题 /
- 瓶颈机器 /
- 瓶颈工件
Abstract: 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 non-bottleneck 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.
- bottleneck job /
- bottleneck mechanism /
- chromosomes /
- computational efficiency

HTML全文

参考文献(20)

[1]	Johnson S M. Optimal two-and three-stage production schedules with setup times included[J]. Naval Research Logistics Quarterly, 1954,1(1):61-68
[2]	Pinedo M L. Scheduling: theory, algorithms, and systems[M]. Berlin Heidelberg: Springer, 2008
[3]	金锋,吴澄.大规模生产调度问题的研究现状与展望[J].计算机集成制造系统,2006,12(2):161-168 Jin F, Wu C. Research status and prospects for massive production scheduling[J]. Computer Integrated Manufacturing Systems, 2006,12(2):161-168 (in Chinese)
[4]	Chen J, Xu L, Pu X J. Four-dimensional algorithm for job-shop scheduling[J]. Procedia Engineering, 2011,16:653-660
[5]	Braune R, Zäpfel G, Affenzeller M. An exact approach for single machine subproblems in shifting bottleneck procedures for job shops with total weighted tardiness objective[J]. European Journal of Operational Research, 2012,218(1):76-85
[6]	Werner F, Winkler A. Insertion techniques for the heuristic solution of the job shop problem[J]. Discrete Applied Mathematics, 1995,58(2):191-211
[7]	Roslöf J, Harjunkoski I, Westerlund T, et al. A short-term scheduling problem in the paper-converting industry[J]. Computers & Chemical Engineering, 1999,23(Supplement 1):S871-S874
[8]	Roslöf J, Harjunkoski I, Westerlund T, et al. Solving a large-scale industrial scheduling problem using MILP combined with a heuristic procedure[J]. European Journal of Operational Research, 2002,138(1):29-42
[9]	Bassett M H, Pekny J F, Reklaitis G V. Decomposition techniques for the solution of large-scale scheduling problems[J]. AIChE Journal, 1996,42(12):3373-3387
[10]	Liu M, Hao J H, Wu C. A prediction based iterative decomposition algorithm for scheduling large-scale job shops[J]. Mathematical and Computer Modelling, 2008,47(3-4):411-421
[11]	Zhang R, Wu C. A hybrid approach to large-scale job shop scheduling[J]. Applied Intelligence, 2010,32(1):47-59
[12]	Zhang R, Wu C. Operation decomposition and statistical bottleneck machine identification for large-scale job shop scheduling[C]// Control and Decision Conference, Shandong, China, 2008:153-158
[13]	Nishi T, Hiranaka Y, Inuiguchi M. Lagrangian relaxation with cut generation for hybrid flowshop scheduling problems to minimize the total weighted tardiness[J]. Computers & Operations Research, 2010,37(1):189-198
[14]	Gocgun Y, Ghate A. Lagrangian relaxation and constraint generation for allocation and advanced scheduling[J]. Computers & Operations Research, 2012,39(10):2323-2336
[15]	Hodgson T J, Cormier D, Weintraub A J, et al. Satisfying due dates in large job shops[J]. Management Science, 1998,44(10):1442-1446
[16]	翟颖妮,孙树栋,杨宏安,等.大规模作业车间多瓶颈调度算法研究[J].计算机集成制造系统,2011,17(7):1486-1494 Zhai Y N, Sun S D, Yang H A, et al. Multi-bottleneck scheduling algorithm for large-scale Job Shop[J]. Computer Integrated Manufacturing Systems, 2011,17(7):1486-1494 (in Chinese)
[17]	Watson K J, Blackstone J H, Gardiner S C. The evolution of a management philosophy: The theory of constraints[J]. Journal of Operations Management, 2007,25(2):387-402
[18]	翟颖妮,孙树栋,王军强,等.基于正交试验的作业车间瓶颈识别方法[J].计算机集成制造系统,2010,16(9):1945-1952 Zhai Y N, Sun S D, Wang J Q, et al. Bottleneck detection method based on orthogonal experiment for Job Shop[J]. Computer Integrated Manufacturing Systems, 2010,16(9):1945-1952 (in Chinese)
[19]	王凌.车间调度及其遗传算法[M].北京:清华大学出版社,2003 Wang L. Shop scheduling with genetic algorithms[M]. Beijing: Tsinghua University Press, 2003 (in Chinese)
[20]	Haupt R. A survey of priority rule-based scheduling[J]. OR Spektrum, 1989,11(1):3-16