A Particle Swarm Optimization Approach for the Earliness-Tardiness No-Wait Flowshop Scheduling Problem
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.
[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.
[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.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:55164", author = "Sedighe Arabameri and Nasser Salmasi", title = "A Particle Swarm Optimization Approach for the Earliness-Tardiness No-Wait Flowshop Scheduling Problem", 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", volume = "6", number = "2", pages = "433-9", }
