基于改进遗传算法的置换装配线调度问题研究

doi:10.16381/j.cnki.issn1003-207x.2016.12.008

摘要/Abstract

摘要： 企业的置换装配线调度问题（Permutation Assembly-line Scheduling Problem，PASP）是一类典型的NP-hard型生产调度问题，是现代集成制造系统CIMS极为关心的问题。该问题可以具体描述为n个工件要在m台机器上加工，每个工件需要经过m道工序，每道工序要求不同的机器，这n个工件通过m台机器的顺序相同，它们在每台机器上的加工顺序也相同，问题的主要目标是找到n个工件在每台机器上的最优加工顺序，使得最大完工时间最小。由于PASP问题的NP-hard性质，本文使用遗传算法对其进行求解。尽管遗传算法常用以求解调度问题，但其选择与交叉机制易导致局部最优及收敛慢。因此，本文提出基于区块挖掘与重组的改进遗传算法用于求解置换装配线调度问题。首先通过关联规则挖掘出不同的优秀基因，然后将具有较优结果的基因组合为优势区块，产生具优势的人工解，并引入高收敛性的局部搜索方法，提高搜索到最优解的机会与收敛效率。本文以OR-Library中Taillard标准测试例来验证改进遗传算法的求解质量与效率，结果证明：本文所提算法与其它求解调度问题的现有5种知名算法相比，不仅收敛速度较快，同时求解质量优于它们。

关键词: 组合优化, 装配线调度, 关联规则, 改进遗传算法, 人工解

Abstract: The Permutation Assembly-line Scheduling Problem(PASP) is a kind of typical production scheduling problem,which has the property of NP-Hard and is the key of Computer Integrated Manufacturing System(CIMS). This problem can be described as follows:N jobs are proceeded in M machines; each job requires M working procedures, of which each procedure requires different machine; they go through the machines in the same order while the processing sequence are also the same in each machines. The main goal for the problem is to find out the optimal processing sequence of N jobs in each machine to minimize the makespan. Genetic algorithm is one kind of heuristic algorithms used to solve permutation Assembly-line scheduling problem (PASP). However, the offspring is difficult to have various genes in good solutions because of the evolution of its selection and crossover mechanism and then leads to local optimum. This paper aims to propose an improved genetic algorithm based on block mining with recombination for solving PASP, in which association rule is used to extract various good genes and increase the gene diversity. These genes are also used to generate various block for artificial chromosome combination. The generated blocks can not only improves the opportunities of finding optimal solutions but also enhance the efficiency of convergence. The proposed algorithm is validated and compared with other five algorithms by numerical experiments, namely Taillard in OR-Library. To compare with other algorithms, the solutions of proposed algorithm are closest to the optimal solution. The results show that proposed algorithm can have not only high the convergence speed but also better solution quality by increasing the solutions diversity.

Key words: combination optimization, assembly-line scheduling, association rules, improved genetic algorithm, artificial solution

中图分类号:

TP18

李劲, 李洪, 徐丽丽, 王华. 基于改进遗传算法的置换装配线调度问题研究[J]. 中国管理科学, 2016, 24(12): 63-71.

LI Jin, LI Hong, XU Li-Li, WANG Hua. Research on Assembly Line Scheduling Problem Based on Improved Genetic Algorithm[J]. Chinese Journal of Management Science, 2016, 24(12): 63-71.

参考文献

[1] Andersson M. Industrial scheduling with evolutionary algorithms using a hybrid representation[D]. Skövde:The University of Skövde,2011.

[2] Chen B O, Lee C. Logistics scheduling with batching and transportation[J]. European Journal of Operational Research, 2013, 189(3): 871-876.

[3] Li Bin, LI Wenfeng. Container terminal logistics systems collaborative scheduling based on multi-agent systems[J]. Computer Integrated Manufacturing Systems, 2011, 17(11): 2502-2514(in Chinese).

[4] Wu C L. Inherent delays and operational reliability of airline schedules[J]. Journal of Air Transport Management, 2005, 11(4): 273-282.

[5] Zhang Qiqian, Hu Minghua, Shi Saifeng, et al. Optimization algorithm of flight takeoff and landing on multi-runways[J]. Journal of Traffic and Transportation Engineering, 2012, 12(06): 63-68(in Chinese).

[6] Yuan Wanghong, Nahrstedt K. Energy-efficient soft real-time cpu scheduling for mobile multimedia systems[J]. ACM SIGOPS Operating Systems Review, 2003, 37(5): 149-163.

[7] Chen Jie. GPU/CPU isomerism system energy saving task scheduling method simulation[J]. Computer Simulation, 2013, 30(07): 235-238(in Chinese).

[8] Yenisey M M, Yagmahan B. Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends[J]. Omega, 2014, 45: 119-135.

[9] Zhang Xianchao, Zhou Hong. Variable parameters quantum-inspired evolutionary algorithm and its application in permutation flow-shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2016, 22(3): 774-781(in Chinese).

[10] Yao Yuanyuan,Ye Chunming, Liu Yutai. Cuckoo search algorithm for the permutation flow-shop scheduling problem with learning effect[J]. Mathematical Theory and Applications, 2015, 35(2): 47-55(in Chinese).

[11] Zhang Yu, Li Wenfeng, Robert H S, et al. Mathematic modeling and heuristic algorithm of hybrid flow shop with multi-jobs families and no-buffer[J]. Systems Engineering-Theory & Practice, 2013, 33(8): 2116-2124(in Chinese).

[12] Zhang Qiliang, Chen Yongsheng. Hybrid PSO-NEH algorithm for solving no-wait flexible flow shop scheduling problem[J]. Systems Engineering-Theory & Practice, 2014, 34(3): 802-809(in Chinese).

[13] Wall M B. A genetic algorithm for resource-constrained scheduling[D].Massachusetts: Massachusetts Institute of Technology,1996.

[14] Li Tieke, Su Zhixiong. Two-stage genetic algorithm for SM-CC production scheduling[J]. Chinese Journal of Management Science, 2009, 17(05): 68-74(in Chinese).

[15] Zhou Shuiyin, Liu Yanfeng. Study on scheduling of whole-set orders under flow-shop with service level constraints[J]. Chinese Journal of Management Science, 2009, 17(04): 69-74(in Chinese).

[16] Hao Xinchang, Lin Lin, Gen M, et al. Effective estimation of distribution algorithm for stochastic job shop scheduling problem[J]. Procedia Computer Science, 2013, 20: 102-107.

[17] Reza H, Saghafian S S. Flow shop-scheduling problems with makespan criterion: A review[J]. International Journal of Production Research, 2005, 43(14): 2895-2929.

[18] Sangkavichitr C, Chongstitvatana P. Block as a small evidence of the building blocks existence[M]//Chen Yingping. Exploitation of Linkage Learning in Evolutionary Algorithms,Berlin Heidelberg:Springer, 2010: 25-44.

[19] Ruiz R, Maroto C, Alcaraz J. Two new robust genetic algorithms for the flow shop scheduling problem[J]. Omega, 2006, 34(5): 461-476.

[20] Chang P C, Chen Menghui, Tiwari M K, et al. A block-based evolutionary algorithm for flow-shop scheduling problem[J]. Applied Soft Computing, 2013, 13(12): 4536-4547.

[21] Chen Menghui, Chang P C, Tiwari A, et al. Bi-variance estimation of distribution model to generate block[J]. World Academy of Science, Engineering & Technology, 77, 2013.

[22] Agrawal R, Imieliński T, Swami A. Mining association rules between sets of items in large databases[J]. ACM SIGMOD Record, 1993, 22(2): 207-216.

[23] Sarath K, Ravi V. Association rule mining using binary particle swarm optimization[J]. Engineering Applications of Artificial Intelligence, 2013, 26(8): 1832-1840.

[24] McNicholas P D, Murphy T B, O'Regan M. Standardising the lift of an association rule[J]. Computational Statistics & Data Analysis, 2008, 52(10): 4712-4721.

[25] Taillard E. Benchmarks for basic scheduling problems[J]. European Journal of Operational Research, 1993, 64(2): 278-285.

[26] Chen S H, Chang P C, Cheng T C E, et al. A self-guided genetic algorithm for permutation flow shop scheduling problems[J]. Computers & Operations Research, 2012, 39(7): 1450-1457.