Discrete Particle Swarm Optimization Algorithm for Lot-Streaming No-Wait Flow Shop Scheduling Problem

Abstract:

This paper proposed discrete particle swarm optimization(DPSO) algorithm to solve lot-streaming no-wait flow shop scheduling problem(LNFSP) with the objective of the maximum completion time. The natural encoding scheme based on job permutation and newly-designed methods were adopted to produce new individuals . After the DPSO-based exploration, a efficient fast local search based on swap neighborhood structure is used to enhance the exploitation capability. Simulation results show the effectiveness of the proposed algorithms.

• Periodical: Advanced Materials Research (Volumes 538-541)
• Pages: 863-868
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.538-541.863
• Online since: June 2012
• Authors: Lin Yang, Yu Xia Pan
• Keywords: Local Search, Lot-Streaming No-Wait Flow Shop Scheduling Problem, Particle Swarm Optimization Algorithm

References

[1] Rajendran C. A no-wait flow shop scheduling heuristic to minimize makespan. Journal of the Operational Research Society 1994;45:472-8.

DOI: 10.2307/2584218

[2] Hall NG, Sriskandarayah C. A survey of machine scheduling problems with blocking and no-wait in process. Operations Research 1996;44:510-25.

DOI: 10.1287/opre.44.3.510

[3] Grabowski J, Pempera J. Sequencing of jobs in some production system. European Journal of Operational Research 2003;125:535-50.

DOI: 10.1016/s0377-2217(99)00224-6

[4] Raaymakers W, Hoogeveen J. Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing. European Journal of Operational Research 2000;126:131-51.

DOI: 10.1016/s0377-2217(99)00285-4

[5] Subodha Kumar, Tapan P. Bagchi, C. Sriskandarajah, Lot streaming and scheduling heuristics for m-machine no-wait flowshops[J], Computers & Industrial Engineering 38 (2000) 149-172.

DOI: 10.1016/s0360-8352(00)00035-8

[6] Hamilton Emmons, Kamlesh Mathur，Lot sizing in a no-wait flow shop[J], Operations Research Letters, Volume 17, Issue 4, May 1995, Pages 159-164.

DOI: 10.1016/0167-6377(95)00008-8

[7] Tasgetiren M F, Liang Y C, Sevkli M, Gencyilmaz G. A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem[J], European Journal of Operational Research, 2007, 177(3): 1930-1947.

DOI: 10.1016/j.ejor.2005.12.024

[8] Liu Bo, Wang Ling, Jin Yihui. An effective PSO-Based memetic algorithm for flow shop scheduling[J], IEEE transactions on systems, man and cybernetics, 2007, 37(1):18-27.

DOI: 10.1109/tsmcb.2006.883272

[9] Pan Q K, Tasgetiren M F, Liang Y C. A Discrete Particle Swarm Optimization Algorithm for the No-Wait Flowshop Scheduling Problem with Makespan Criterion[A]. Proceedings of the International Workshop on UK Planning and Scheduling Special Interest Group[C], London: City University, 2005, 31-41.

DOI: 10.1007/978-1-84628-663-6_2

[10] Pan Q K, Tasgetiren M F, Liang Y C. Minimizing Total Earliness and Tardiness Penalties with a Common Due Date on a Single-Machine the

DOI: 10.1109/scis.2007.367701

[11] Pan Q K, Tasgetiren M F, Liang Y C. A Discrete Particle Swarm Optimization Algorithm for Single Machine Total Earliness and Tardiness Problem with a Common Due Date[A]. Proceedings of the 2006 Congress on Evolutionary Computation[C], Canada: Vancouver, 2006, 3281-3288.

DOI: 10.1109/cec.2006.1688726

[12] Shahriar Farahmand Rad, Rubén Ruiz, Naser Boroojerdian, Newhigh performing heuristics for minimizing makespan inpermutation flowshops[J], The International Journal of Management Science, Omega 37 (2009) 331 – 345.

DOI: 10.1016/j.omega.2007.02.002

[13] Pan QK, Tasgetiren MF, Liang YC (2006) Minimizing total earliness and tardiness penalties with a common due date on a single-machine using a discrete particle swarm optimization algorithm. LNCS 4150:460–467

DOI: 10.1007/11839088_46

[14] Pan QK, Tasgetiren MF, Liang YC (2005) A discrete particle swarm

[15] optimization algorithm for the no-wait flowshop scheduling problem with makespan criterion, in Proceedings of the international workshop on UK planning and scheduling special interest group, UK PLANSIG2005. City University, London, pp: 31–41

[16] Q K PAN, M F Tasgetiren, Yun-Chia Liang. A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem[J] computer&operation research, 2 April 2007, 2807-2839.

DOI: 10.1016/j.cor.2006.12.030

[17] Marimulthu S, Ponnambalam SG, Jawahar N. Evolutionary algorithms for scheduling m-machine flow shop with lot streaming[J]. Robotics and Computer-Integrated Manufacturing 2008; 24:125-139.

DOI: 10.1016/j.rcim.2006.06.007

[18] Marimulthu S, Ponnambalam SG, Jawahar N. Threshold accepting and ant-colony optimization algorithm for scheduling m-machine flow shop with lot streaming[J]. Journal of Material Processing Technology 2009; 209:1026-1041.

DOI: 10.1016/j.jmatprotec.2008.03.013