AUTHORS: Lin Wang, Jianhua Qu, Yucheng Jia

Download as PDF

ABSTRACT: Permutation Flow Shop Scheduling Problem (PFSP) is a complex combinatorial optimization problem with strong engineering background. To solve the PFSP with makespan criterions, an immune particle swarm optimization (IPSO) algorithm was proposed. The initial solution of the algorithm is generated by the famous heuristic NEH algorithm, it was used to initialize the particle of global extreme values. Then we add a Dynamic Disturbance Term (DDT) in the velocity updating formulation of the particle, it used to prevent optimizing course from trapping the local minimum. Density and Immune Selection mechanism of Immune algorithm (IA) are used in the iterative process to select the optimal particle through the choice probability equation. The vaccination and memory operation to guide the global optimization process. At last, computational results show that the IPSO algorithm is effective robust and has a high performance.

KEYWORDS: Permutation Flow Shop Scheduling, Particle Swarm Optimization Algorithm, Immune Algorithm, Makespan

REFERENCES:

[1]Yun JING,Shiwei HE,Zhiqiang TIan,Qi SONG,Quantum Immune Clonal Algorithm for NOIdle Flow Shop Scheduling Problem.Systerm Simulation,Technology&application.No.14,2009,pp. 209-212.

[2]J. K. Lenstra, A. H. G. R. Kan, and P. Brucker, “Complexity of machine scheduling problems,” Annals of Discrete Mathematics, No. 1,1997, pp. 343–362, .

[3]ChaochaoWu,.XingshengGu.,A Genetic Algorithm for Flow shop Scheduling with Fuzzy processing Time and Due Date

[J],proceedings of 5th World congress on control and Automation,June,2004:pp.2983-2942.

[4]HE Long-min,SUN Shi-jie,A hybrid two-stage flexible flowshop scheduling problem with m identical parallel machines and a burn-in processor separately

[J].Joutnal of Shanghai University(EnglishEdition),Vol02,No.28,2007,pp.33 -38.

[5]Chuyang, Wang.Fast Iterated Local Search Algorithm with High Order Neighborhood for Nowait Flowshop Scheduling Problem

[A]. Proceedings of the 2014 Chinese Control and Decision Conference (CCDC),2014,pp.4461-4465.

[6]CUI Zhe, GU Xing-sheng, Hybrid Discrete Harmony Search Algorithm for Flow Shop Scheduling with Limited Buffers

[J].Journal of Donghua University (English Edition)vol04,No.30,2014,pp.165-170.

[7]Yu Xue,Yi Zhuang,Tianquan Ni. Self-adaptive learning based discrete differential evolution algorithm for sloving CJWTA problem

[ J].Journal of systerms Enigeering and Electronics.Vol02,No.15,2014,:59-68.

[8]Wenbin Gu,Dunbing Tang,Lei Zheng. Solving Job-Shop Scheduling Problem Based on Improved Adaptive Particle Swarm Optimization Algorithm

[J].Transactions of Nanjing University of Aeronautics and Astronautics, Vol.31,No.5,2014,pp.:559-567.

[9]Gao YE , Xue RUI, An Improved Simulated Annealing Algorithm for TSP

[A].Proceeding of 2013 5th IEEE International Conference On Broadband Network & Multimedia technology

[C].2013.

[10]Jianping Dou ,Jun Li .A discrete Particle Swarm Algorithm foe Makespan Minimization in the Permutation Flowsshop Scheduling Problem

[J],proc IEEE international conference on evolutionary computation,2013,pp.69-73.

[11]Zhang peng, Wang ling. Improved Fruit Fly Optimization Algorithm for Solving Lot-Streaming Flow-Shop Scheduling Problem

[J].Journal of Donghua University (English Edition),Vol31,No.02,2014,pp.165-170.

[12]Eberhart R C.Kennedy J.A New Optimizier Using Particle Swarm Theory

[C].Processing of the sixth International Symposium on Micro Machine and Human Science, Micro Machine and Human Science, Nagoya Japan,1995,pp.39-43.

[13]Jianjun Qi,Bo Guo,Hontao Lei,Tao Zhang.Solving resource availability cost problem in project scheduling by pseudo particle swarm optimization

[J].Journal of Systems Engineering and Electronics,Vol25,No.01,2014,pp.69-76.

[14]Hai-bo Tang, Chun-ming YE.Permutation Flow Shop Scheduling Algorithm based on a Hybrid Particle Swarm Optimization

[A].Proceedings of 2010 IEEE the 17th International Conference on Industrial Engineering and Engineering Management

[C].2010.

[15]M.Tasgetiren, M.Sevkli,Y.C.Liang and G.Gencyilmaz, “Paricle swarm optimization algorithm for permutation flow shop sequencing problem.”Ant Colony Optimization and Swarm Intelligence,2004,pp.366-385..

[16]LIIU Bo,WANGLing,JINYIhui.An Effective Hybrid PSO-based Algorithm for Flow Shop Scheduling to Minimize Makespan

[J].Chaos,solitions&fractals,Vol35,No5,2 008,pp.851-861.

[17]WANG Xiaopeng,TANG Lixin.An Improves Particle Swarm Optimization Algorithm for Permutation Flowshop Scheduling Problem with Total Flowtime Criterion

[J],Lecture Notes in Computer Science,6145,2010,pp.144-151.

[18]Bao Z,Watanabe T.Mixed constrained image filter design using particle swarm optimization

[J].Artificial Life and Robotics,Vol15,No.32010,pp.363-368.

[19]Wang Zhongjie ,Zhao Mingming, Hu Miao .Study of the Immune Simulated Annealing Algorithm and Dual-resource Job Shop Order Scheduling

[A].Proceedings of the 2013 Chinese Control and Decision Conference (CCDC):2376- 2380.

[20]TASGETIREN,M F.,SEVKLI M,LIANG Y C,etal. Particle Swarm Optimization Algorithm for Single Machine Total Weighted Tardiness Problem

[C].Proceedings of IEEE Congress on Evolutionary Computation, Washington, D,C., USA: IEEE, 2.2014,pp. 1412-1419.

[21]Carlier J,Pinson.An algorithm for solving the job shop problem,Management Science,36(2),1989,pp.164-176.

[22]E.Taillard.”Benchmarks for basic scheduling problems”, European Journal of Operational Research,vol.47.1989,pp.67-74.

[23]GAO Shou-wei,LIN Chen,ZHANG Weidong.,An Enhanced NEH Method in Solving Permutation Flow Shop Problem

[J].Journal of Shanghai Jiaotong University(Science),Vol.E- 12,No.1,2007,47-52.

[24]Jun-hua Duan,Min Zhang.A Genetic Algorithm for Permutation Flowshop Scheduling With Total Flowtime Criterion

[C].Proceeding of the 2011 Chinese Control and Decision Conference(CCDC),Vol23No.05,2011,pp.1541- 1544.