Computer Science ›› 2013, Vol. 40 ›› Issue (11): 1-7.

    Next Articles

Research on Permutation Flow-shop Scheduling Problem

LIU Ying,GU Wen-xiang and LI Xiang-tao   

  • Online:2018-11-16 Published:2018-11-16

Abstract: As the science and technology develop and the production scale expands constantly,the research on permutation flow-shop scheduling problem has been more and more attention by many scholars.So far,there are a lot of optimization algorithms in the fields,and they greatly increase the production efficiency.There are some literatures which are compared and reviewed,but not including the research of the latest solving methods and results.From a new perspective on the problems in classification,we detailed the comparison of new algorit hms,making scholars to have the latest and comprehensive understanding.

Key words: Scheduling,Permutation flow-shop,Meta-heuristics,Makespan,Tardiness

[1] Johnson S M.Optimal two-and three-stage production schedules with setup times included[M].Naval Research Logistics Quarterly,1954:61-68
[2] 高守玮.一类Flow shop 生产调度问题及其优化方法之分析与研究[D].上海:上海交通大学,2007
[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,2004,5(12):1243-1255
[4] Ruiz R,Maroto C.A Comprehensive Review and Evaluation of Permutation Flowshop Heuristics[J].European Journal of Operational Research,2005,5:479-494
[5] Gupta J N D,Stafford E F Jr.Flowshop Scheduling Research after Five Decades[J].European Journal of Operational Research,2006,9:699-711
[6] Kalczynski P J,Kamburowski J.On the NEH Heuristic for Mi-nimizing the Makespan in Permutation Flowshops[J].OMEGA:The International Journal of Management Sciences,2007,5:53-60
[7] Pan Q-K,Ruiz R.A Comprehensive Review and Evaluation of Permutation Flowshop Heuristics to Minimize Flowtime[J].Computer & Operations Research,2013,40(7):117-128
[8] Dong Xing-ye,Huang Hou-kuan,Chen Ping.An iterated localsearch algorithm for the permutation flowshop problem with Total Flowtime criterion [J].Computers & Operations Research,2009,36:1664-1669
[9] Kan R,A H G.Machine Scheduling Problems:Classification,Complexity and Computations 1976[M]∥Martinus Nijhoff,The Hague,The Netherlands,1976:180
[10] Pinedo M.Scheduling:Theory,Algorithms and Systems(second ed)[M].New Jersey:Prentice Hall,2002:1118-1122
[11] Baker K R.Introduction to Sequencing and Scheduling[M].John Wiley & Sons 1974,New York,1974:305
[12] Gupta J N D.A review of flowshop scheduling research[M]∥Ritzman L P,Krajewski L J,Berry W L,et al.,eds.Disaggregation Problems in Manufacturing and Service Organizations.Martinus Nijhoff,The Hague,1979:363-388
[13] Garey M R,Johnson,et al.The complexity of flowshop and jobshop scheduling[J].Mathematics of Operations Research,1976,1:117-129
[14] Palmer D S.Sequencing jobs through a multistage process in the minimum total time:A quick method of obtaining a near-optimum[J].Operational Research Quarterly,1965,6:101-107
[15] Dannenbring D G.An evaluation of flow shop sequencing heuristics[J].Management Science,1977,23(11):1174-1182
[16] Taillard E.Some efficient heuristic methods for the flowshop sequencing problems[J].European Journal of Operational Research,1990,7:65-74
[17] Framinan J M,Leisten R,Ruiz-Usano R.Efficient heuristics for flowshop sequencing with the objectives of Makespan and flowtime minimization[J].European Journal of Operational Research,2002,141:559-569
[18] Storn R,Price K.Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces[R].Technical Report TR-95-012.ICSI,1995
[19] Pan Q-K,Tasgetiren M F,Liang Y-C.A discrete differential evolution algorithm for the permutation flowshop scheduling problem[C]∥Proceedings of the genetic and evolutionary computation conference 2007(GECCO’07).London,England,UK,2007:126-33
[20] Qian B,Wang L.A hybrid differential evolution method for permutation flow-shop scheduling[J].The International Journal of Advanced Manufacturing Technology,2008,8:757-777
[21] Bean J.Genetic algorithms and random keys for sequencing and optimization[J].ORSA Journal on Computing,1994,6(2):154-160
[22] Deng G L,Gu X S.A hybrid discrete differential evolution algorithm for the no-idle permutation flow shop scheduling problem with Makespan criterion[J].Computers & Operations Research,2012,39:2152-2160
[23] 张长胜.求解规划、聚类和调度问题的混合粒子群算法研究[D].长春:吉林大学,2009
[24] Chen C-L,Vempati V S,Aljaber N.An application of genetic algorithms for flow shop problems[J].European Journal of Operational Research,1995,0:389-396
[25] Murata T,Ishibuchi H,Tanaka H.Genetic algorithms for flow shop scheduling problems[J].Computers and Industrial Engineering,1996,0:1061-1071
[26] Reeves C R,Yamada T.Genetic Algorithms,Path Relinking and the Flowshop Sequencing Problem[J].Evolutionary Computation Journal,1998,6(1):230-234
[27] Ponnambalam S G,Aravindan P,Chandrasekaran S.Construc-tive and improvement flow shop scheduling heuristics:An extensive evaluation.Production[J].Planning and Control,2001,12(4):335-344
[28] Nagano N S,Ruiz R.Luiz Antonio Nogueira Lorena,A constructive genetic algorithm for permutation flwoshop scheduling[J].Computers & Industrial Engineering,2008,55:195-207
[29] Wang L,Zheng D Z.An Effective Hybrid Heuristic for Flow Shop Scheduling [J].International Journal of Advanced Manufacturing Technology,2003,1(1):38-44
[30] Aldowaisan T,Allahverdi A.New heuristics for no-wait flow-shops to minimize Makespan[J].Computers and Operations Research,2003,30:1219-1231
[31] Ruiz R,Maroto C,Alcaraz J.New Genetic Algorithms for thePermutation Flowshop Scheduling Problem[C]∥Proceedings of The Fifth Metaheuristic International Conference.Kyoto,2003:63
[32] Ruiz R,Maroto C,Alcaraz J.Two New Robust Genetic Algorithms for the Flowshop Scheduling Problem[J].OMEGA,the International Journal of Management Science,2005,4:461-476
[33] Kennedy J,Eberhart R.Particle Swarm Optimization[C]∥Proceedings of the 1995IEEE International Conference on Neural Networks.1995:1942-1948
[34] Kuo I-H,Horng S-J,et al.An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model[J].Expert Systems with Applications,2009,6:7027-7032
[35] Lian Z,Gu X,Jiao B.A Similar Particle Swarm Optimization Algorithm for Permutation Flowshop Scheduling to Minimize Makespan[J].Applied mathematics and computation,2006,5(1):773-785
[36] Liu B,Wang L,Jin Y H.An Effective PSO-Based Memetic Algorithm for Flow Shop Scheduling[J].IEEE Transactions on Systems,Man and Cybernetics,Part B,2007,7(1):18-27
[37] Liao C J,Tseng C T,Luarn P.A Discrete Version of Particle Swarm Optimization for Flowshop Scheduling Problems[J].Computers and Operations Research,2007,4(10):3099-3111
[38] Stutzle T.An ant approach for the flow shop problem[A]∥Proceedings of the 6th European congress on intelligent techniques and soft computing [C].Aachen:Verlag Mainz,1998,3:1560-1564
[39] Rajendran C,Ziegler H.Ant-colony algorithms for permutation flowshop scheduling to minimize Makespan/Total Flowtime of jobs[J].European Journal of Operational Research,2004,155:426-438
[40] Ahmadizar F,Barzinpour F.A hybrid algorithm to minimizeMakespan for the permutation flow shop scheduling problem[J].International Journal of Computational Intelligence Systems,2010,3(6):853-861
[41] Ahmadizar F.A new ant colony algorithm for Makespan minimization in permutation flow shops[J].Computers & industrial engineering,2012(63):355-361
[42] Ruiz R,Stützle T.A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem [J].European Journal of Operational Research,2007,177(3):2033-2049
[43] 刘长平,叶春明.置换流水车间调度问题的萤火虫算法求解[J].工业工程与管理,2012,3(17):56-59
[44] Li Xiao-ping,Wang Qian,Wu Cheng.Efficient composite heuristics for Total Flowtime minimization in permutation flow shops [J].Omega,2009,7:155-164
[45] Zhang Yi,Li Xiao-ping,Wang Qian.Hybrid genetic algorithm for permutation flowshop scheduling problems with Total Flowtime minimization[J].European Journal of Operational Research,2009,196:869-876
[46] Tseng Lin-yu,Lin Ya-tai.A hybrid genetic local search algo-rithm for the permutation flowshop scheduling problem[J].European Journal of Operational Research,2009,8:84-92
[47] Dong Xing-ye,Chen Ping,Huang Hou-kuan,et al.A multi-restart iterated local search algorithm for the permutation flow shop problem minimizing total flow time[J].Computers & Operations research,2013,0:627-632
[48] Rajendran C,Ziegler G.Two ant-colony algorithms for minimizing Total Flowtime in permutation flowshops[J].Computers & Industrial Engineering,2005,8:789-797
[49] Tasgetiren M,Pan Q-K,Suganthan P,et al.A discrete artificial bee colony algorithm for the Total Flowtime minimization in permutation flow shops[J].Information Sciences,2011,181:3459-3475
[50] Pinedo M.Scheduling:theory,algorithms and systems(2ed)[M].Englewood Cliffs,NJ:Prentice-Hall,2002
[51] Gelders L F,Sambandam N.Four simple heuristics for scheduling a flowshop[J].International Journal of Production Research,1978,16:221-231
[52] Kim Y D.Heuristics for flow shop scheduling problems minimizing meantardiness[J].Journal of the Operational Research Socie-ty,1993,44:19-28
[53] Armentano V A,Ronconi D.Tabu search for total tardinessminimization inflowshop scheduling problems[J].Computers & Operations Research,1999,6:219-235
[54] Hasija S,Rajendran C.Scheduling in flowshops to minimize totaltardiness of jobs[J].International Journal of Production Research,2004,42:2289-2301
[55] Vallada E,et al.Minimising total tardiness in the m-machineflowshop problem:Areview and evaluation of heuristics and metaheuristics[J].Computers & Operations Research,2008,35:1350-1373
[56] Hasija S,Rajendran C.Scheduling in flowshops to minimize totaltardiness of jobs[J].International Journal of Production Research,2004,2(2):289-301
[57] Parthasarathy S,Rajendran C.Scheduling to minimize mean tardiness and weighted mean tardiness in flowshop and flowline-based manufacturing cell[J].Computers and Industrial Engineering,1998,34:531-46
[58] Onwubolu G,Davendra D.Scheduling flow shops using differential evolution algorithm[J].European Journal of Operational Research,2006,1:674-92
[59] Onwubolu G C,Mutingi M.Genetic algorithm for minimizingtardiness in flow-shop scheduling[J].Production Planning and Control,1999,0:462-71
[60] Framinan J M,Leisten R.Total tardiness minimization in permutation flow shops:a simple approach based on a variable greedy algorithm[J].International journal of production Research,2008,2:6479-6498
[61] Vallada E,Ruiz R.Genetic algorithms with path relinking forthe minimum tardiness permutation flowshop problem[J].Omega,2010,8:57-67

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!