Block-based Evolutionary Algorithm for Permutation Flow-shop Scheduling Problem

doi:10.16182/j.issn1004731x.joss.201808043

Abstract

Abstract: To solve the permutation flow-shop scheduling problem(PFSP), an effective new global evolutionary algorithm based on block model is developed. The probability model is built based on the information of job position through sample and statistic on the good chromosomes, and the association rule is applied to extract continuous or discontinuous blocks which contain job information respectively. The superiority blocks with position probability model for artificial chromosome combinations are integrated. The disadvantage gene is excavated according to the inferior chromosome and used for the later mutation operation. Two efficient local search methods called position model-based interchange and NEH-based insertion are proposed to further filter the dominant solution. Simulation results on Reeves and Taillard suites and comparisons with other well-known algorithms validate its excellent searching ability and efficiency of the proposed algorithm.

Key words: permutation flow-shop scheduling, combination blocks, probability model, artificial chromosome

CLC Number:

TP301

Pei Xiaobing, Zhao Heng. Block-based Evolutionary Algorithm for Permutation Flow-shop Scheduling Problem[J]. Journal of System Simulation, 2018, 30(8): 3170-3178.

References

[1] Garey M R, Graham R L, Johnson D S.Some NP- complete geometric problems[C]// Proceedings of the eighth annual ACM symposium on Theory of computing. ACM, 1976: 10-22.
[2] Chung C S, Flynn J, Kirca O.A branch and bound algorithm to minimize the total flow time for m-machine permutation flow shop problems[J]. International Journal of Production Economics (S0925-5273), 2002, 79(3): 185-196.
[3] Framinan J M, Gupta J N D, leisten R. A review and classification of heuristics for permutation flow-shop scheduling with makespan objective[J]. Journal of the Operational Research Society (S0160-5682), 2004, 55(12): 1243-1255.
[4] Lima C F, Pelikan M, Lobo F G, et al.Loopy sub-structural local search for the Bayesian optimization algorithm[C]// International Workshop on Engineering Stochastic Local Search Algorithms. Springer Berlin Heidel-berg, 2009: 61-75.
[5] Ceberio J, Irurozki E, Mendiburu A, et al.A review on estimation of distribution algorithms in permutation based combinatorial optimization problems[J]. Progress in Artificial Intelligence (S2192-6352), 2012, 1(1): 103-117.
[6] Liu H, Gao L, Pan Q.A hybrid particle swarm optimization with estimation of distribution algorithm for solving permutation flowshop scheduling problem[J]. Expert Systems with Applications (S0957-4174), 2011, 38(4): 4348-4360.
[7] Tzeng Y R, Chen C L, Chen C L.A hybrid EDA with ACS for solving permutation flow shop scheduling[J]. The International Journal of Advanced Manufacturing Technology (S0268-3768), 2012, 60(9/12): 1139-1147.
[8] Chang P C, Huang W H, Wu J L, et al.A block mining and re-combination enhanced genetic algorithm for the permutation flowshop scheduling problem[J]. International Journal of Production Economics (S0925-5273), 2013, 141(1): 45-55.
[9] Chang P C, Chen M H.A block based estimation of distribution algorithm using bivariate model for scheduling problems[J]. Soft Computing (S1432-7643), 2014, 18(6): 1177-1188.
[10] Ruiz R, Maroto C, Alcaraz J.Two new robust genetic algorithms for the flowshop scheduling problem[J]. Omega (S0305-0483), 2006, 34(5): 461-476.
[11] Hsu C Y, Chang P C, Chen M H.A linkage mining in block-based evolutionary algorithm for permutation flowshop scheduling problem[J]. Computers & Industrial Engineering (S0360-8352), 2015, 83(C): 159-171.
[12] Tizhoosh H R.Opposition-Based Learning: A New Scheme for Machine Intelligence[C]// CIMCA/ IAWTIC. 2005: 695-701.
[13] McNicholas P D, Murphy T B, O’Regan M. Standardising the lift of an association rule[J]. Computational Statistics & Data Analysis(S0167-9473), 2008, 52(10): 4712-4721.
[14] Nawaz M, Enscore E E, Ham I.A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem[J]. Omega(S0305-0483), 1983, 11(1): 91-95.
[15] 刘延风, 刘三阳. 基于混合电磁算法求解置换流水车间调度问题[J]. 系统仿真学报, 2012, 24(3): 603-607.
Liu Yanfeng, Liu Sanyang.Hybrid Eletro-magnetism- based Algorithm for Permutation Flow Shop Scheduling[J]. Journal of System Simulatiom, 2012, 24(3): 603-607.
[16] Chen Y M, Chen M C, Chang P C, et al.Extended artificial chromosomes genetic algorithm for permutation flowshop scheduling problems[J]. Computers & Industrial Engineering (S0360-8352), 2012, 62(2): 536-545.
[17] 张先超, 周泓. 变参数量子进化算法及其在求解置换流水车间调度问题中的应用[J]. 计算机集成制造系统, 2016, 22(3): 774-781.
Zhang Xianchao, Zhou Hong.Variable paramenters quantum-inspired evolutionary algorithm and its application in permutation flow-shop scheduling problem[J]. Computer Integrated Manu- facturing Systems, 2016, 22(3): 774-781.
[18] Lian Z, Gu X, Jiao B.A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan[J]. Applied Mathematics and Computation (S0096-3003), 2006, 175(1): 773-785.
[19] Chang P C, Huang W H, Ting C J.A hybrid genetic-immune algorithm with improved lifespan and elite antigen for flow-shop scheduling problems[J]. International Journal of Production Research (S0020-7543), 2011, 49(17): 5207-5230.