Computer Science ›› 2015, Vol. 42 ›› Issue (9): 220-225.doi: 10.11896/j.issn.1002-137X.2015.09.042

Previous Articles     Next Articles

Hybrid Multi-objective Algorithm for Solving Flexible Job Shop Scheduling Problem

ZUO Yi, GONG Mao-guo, ZENG Jiu-lin and JIAO Li-cheng   

  • Online:2018-11-14 Published:2018-11-14

Abstract: The flexible job shop scheduling problem is one of the most important optimization problems in the field of production scheduling,due to its complexity and practical applications in real life.Most studies focus on only one objective—the makespan that is the total time required to complete all jobs.However,a single objective may be insufficient for real applications.Therefore,a new hybrid multi-objective algorithm was proposed for solving the flexible job shop scheduling problem(FJSP) with three objectives,including the makespan,total workload,and critical workload.Effective chromosome representation and genetic operators are introduced.The nondominated neighbor immune algorithm is used to search for Pareto optimal solutions.To improve the search performance,three different local search strategies were designed and combined in the multi-objective algorithm.The computational results on several data sets show that the proposed algorithm outperforms other representative algorithms in general.In addition,the experiments validate the effectiveness of local search strategies.

Key words: Flexible job shop scheduling problem,Multi-objective,Local search,Nondominated neighbor immune algorithm

[1] 刘莹,谷文祥,李向涛.置换流水线车间调度问题的研究[J].计算机科学,2013,40(11):1-7 Liu Y,Gu W X,Li X T.Research on permutation flow-shop scheduling problem [J].Computer Science,2013,40(11):1-7
[2] Garey M R,Johnson D S,Sethi R.The complexity of flowshop and job-shop scheduling [J].Mathematics of Operations Research,1976,3(1):117-129
[3] Brandimarte P.Routing and scheduling in a flexible job shop by tabu search [J].Annals of Operations Research,1993,1(3):157-183
[4] Hurink E,Jurisch B,Thole M.Tabu search for the job shopscheduling problem with multi-purpose machine [J].Operations Research Spectrum,1994,15(4):205-215
[5] Mastrolilli M,Gambardella L M.Effective neighborhood func-tions for the flexible job shop problem [J].Journal of Scheduling,2000,3(1):3-20
[6] Gao J,Sun L,Gen M.A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems [J].Computers & Operation Research,2008,35(9):2892-2907
[7] Pezzella F,Morganti G,Ciaschetti G.A genetic algorithm for theflexible job-shop scheduling problem [J].Computers & Operation Research,2008,35(10):3202-3212
[8] Hmida B A,Haouari M,Huguet M J,et al.Discrepancy search for the flexible job shop scheduling problem [J].Computers & Operation Research,2010,37(12):2192-2201
[9] Yuan Y,Xu H,Yang J.A hybrid harmony search algorithm for the flexible job shop scheduling problem [J].Applied Soft Computing,2013,13(7):3259-3272
[10] Yuan Y,Xu H.Multiobjective Flexible Job Shop Scheduling Using Memetic Algorithms [J].IEEE Transactions on Automation Science and Engineering,2013,12(1):336-353
[11] Xia W,Wu Z.An effective hybrid optimization approach formulti-objective flexible job-shop scheduling problems [J].Computers & Industrial Engineering,2005,48(2):409-425
[12] Zhang G,Shao X,Li P,et al.An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem [J].Computers & Industrial Engineering,2009,56(4):1309-1318
[13] Xing L,Chen Y,Yang K.An efficient search method for multi-objective flexible job shop scheduling problems [J].Journal of Intelligent Manufacturing,2009,20(3):283-293
[14] Kacem I,Hammadi S,Borne P.Pareto-optimality approach for flexible job-shop scheduling problems [J].Hybridization of evolutionary algorithms and fuzzy logic Mathematics and Compu-ters in Simulation,2002,60(3):245-276
[15] Wang X,Gao L,Zhang C,et al.A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem [J].The International Journal of Advanced Manufacturing Technology,2010,51(5):757-767
[16] Li J,Pan Q,Xie S.An effective shuffled frog-leaping algorithm for multi-objective flexible job shop scheduling problems [J].Applied Mathematics and Computation,2012,218(18):9353-9371
[17] Chiang T,Lin H.Flexible job shop scheduling using a multiobjective memetic algorithm [M]∥ Advanced Intelligent Computing Theories and Applications.With Aspects of Artificial Intelligence.Springer Berlin Heidelberg.2012:49-56
[18] Chiang T,Lin H.A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling [J].International Journal of Production Economics,2013,141(1):87-98
[19] Gong M G,Jiao L C,Du H,et al.Multi-objective immune algorithm with nondominated neighbor-based selection [J].Evolutionary Computation,2008,16(2):225-255
[20] Cheng R.A tutorial survey of job-shop scheduling problems using genetic algorithms,part I:Representation [J].Computers & Industrial Engineering,1996,30(4):983-997
[21] Balas E.Machine scheduling via disjunctive graphs:an implicit enumeration algorithm [J].Operations Research,1969,17(6):941-957
[22] Zitzler E,Thiele E,Laumanns M,et al.Performance assessment of multiobjective optimizers:An analysis and review [J].IEEE Transactions on Evolutionary Computation,2003,7(2):117-132

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!