A Particle Swarm Optimization Approach for the Earliness-Tardiness No-Wait Flowshop Scheduling Problem

Authors: Sedighe Arabameri, Nasser Salmasi

Abstract:

In this researcha particle swarm optimization (PSO) algorithm is proposedfor no-wait flowshopsequence dependent setuptime scheduling problem with weighted earliness-tardiness penalties as the criterion (
|, |Σ   " ).The smallestposition value (SPV) rule is applied to convert the continuous value of position vector of particles in PSO to job permutations.A timing algorithm is generated to find the optimal schedule and calculate the objective function value of a given sequence in PSO algorithm. Twodifferent neighborhood structures are applied to improve the solution quality of PSO algorithm.The first one is based on variable neighborhood search (VNS) and the second one is a simple one with invariable structure. In order to compare the performance of two neighborhood structures, random test problems are generated and solved by both neighborhood approaches.Computational results show that the VNS algorithmhas better performance than the other one especially for the large sized problems.

Keywords: minimization of summation of weighed earliness and tardiness, no-wait flowshop scheduling, particle swarm optimization, sequence dependent setup times

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1062228

References:

[1] N.G.Hall, C. Sriskandarajah,A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process. Operations Research 44 (1996) 510-525.
[2] M. Pinedo,Scheduling theory, algorithms, and systems. 3rd ed., Englewood Cliffs, NJ: Prentice-Hall; 2008, pp. 13-78.
[3] H. Rock, The three-machine no-wait flowshop problem is NP-complete. Journal of the Association for Computing Machinery 31(1984) 336-345.
[4] R. Gangadharan, C. Rajendran, Heuristic algorithms for scheduling in the no-wait flowshop. International Journal of Production Economics 32 (1993) 285-290.
[5] C. Rajendran, A no-wait flowshop scheduling heuristic to minimize makespan. Journal of the Operational Research Society 45 (1994) 472- 478.
[6] P. Dileepan, A note on minimizing maximum lateness in a two-machine no-wait flowshop. Computers & Operations Research 31 (2004) 2111- 2115.
[7] X. Wang, T.C.E. Cheng, Aheuristic approach for two-machine no-wait flowshopscheduling with due dates and class setups. Computers & Operations Research 33 (2006) 1326-1344.
[8] A. Allahverdi, T. Aldowaisan, No-wait flowshops with bi-criteria of makespanand maximum lateness. European Journal of Operational Research 152 (2004) 132-147.
[9] C. Wang, X. Li and Q. Wang, Acceleratedtabusearchfor no-wait flowshopschedulingproblem. EuropeanJournalofOperationalResearch206(2010) 64-72.
[10] Q.K. Pan, L. Wang and B. Qian, Anoveldifferentialevolutionalgorithmforbi-criteriano-waitflowshop. Computers&OperationsResearch36 (2009) 2498-2511.
[11] B. Liu, L. Wang and Y.H. Jin, Aneffectivehybridparticleswarmoptimizationfornowaitflowshopscheduling. IntJAdvManufTechnol(2007)31:1001-1011.
[12] Q.K. Pan, L. Wang, Tasgetiren, M.F. Ahybriddiscreteparticleswarmoptimizationalgorithmforthenowaitflowshopschedulingproblemwithmakespancriterion. IntJAdvManufTechnol(2008)38:337-347.
[13] Q.K. Pan, M.F. Tasgetiren, Y.C. Liang, A discrete particle swarm optimization algorithm for the no-waitflowshop scheduling problem. Computers & Operations Research 35 (2008) 2807 - 2839.
[14] Q.K. Pan, L. Wang, B.Qian, Anovelmultiobjectiveparticleswarmoptimizationalgorithmfornowaitflowshopschedulingproblems. JEM 989- IMechE2008Proc.IMechEVol.222PartB:J.EngineeringManufacture.
[15] M.F. Tasgetiren, M. Sevkli, Y.C. Liang and G. Cencylmaz,Particle Swarm Optimization Algorithm forSingle Machine Total Weighted TardinessProblem. Proceeding of the 2004 congress on evolutionary computation(CEC2004), Portland, 2004; 1412-9.
[16] M.F. Tasgetiren, Y.C. Liang, M. Sevkli and G. Cencylmaz, Particle Swarm Optimization Algorithm for Makespan and Maximum LatenessMinimization in Permutation Flowshop Sequencing Problem.
[17] RC. Eberhart,J. Kennedy, A new optimizer using particle swarm theory. Proceedings of the sixth international symposium on micro machineand human science, Nagoya, Japan; 1995. p. 39-43.
[18] W. Szwarc, S.K. Mukhopadhyay, Optimal Timing Schedules in Earliness-Tardiness Single Machine Sequencing. Naval Research Logistics (1995) 42:1109-1114.
[19] N. Salmasi, R. Logendran and M.R. Skandari,Total flow time minimization in a flowshop sequence dependent group scheduling problem. Computers & Operations Research 37 (2010) 199 -212.
[20] R.J. Ross, Taguchi techniques for quality engineering, McGraw-Hill, New York;1989
[21] R. Poli, K. Kennedy and T. Blackwell, Particle swarm optimizationAn overview. Swarm Intell (2007) 1: 33-57.