Abstract
The academic approach of single-objective flowshop scheduling has been extended to multiple objectives to meet the requirements of realistic manufacturing systems. Many algorithms have been developed to search for optimal or near-optimal solutions due to the computational cost of determining exact solutions. This paper provides a particle swarm optimization-based multi-objective algorithm for flowshop scheduling. The proposed evolutionary algorithm searches the Pareto optimal solution for objectives by considering the makespan, mean flow time, and machine idle time. The algorithm was tested on benchmark problems to evaluate its performance. The results show that the modified particle swarm optimization algorithm performed better in terms of searching quality and efficiency than other traditional heuristics.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Campbell HG, Dudek RA, Smith ML (1970) A heuristic algorithm for the n-job m-machine sequencing problem. Manage Sci 16:B630–B637. doi:10.1287/mnsc.16.10.B630
Carlier J (1978) Ordonnancements à contraintes disjonctives. RAIRO Rech Oper. Oper Res 12:333–351
Chakravarthy K, Rajendran C (1999) A heuristic for scheduling in a flowshop with the bicriteria of makespan and maximum tardiness minimization. Prod Plann Contr 10:707–714. doi:10.1080/095372899232777
Eren T, Güner E (2007) The tricriteria flowshop scheduling problem. Int J Adv Manuf Technol 36:1210–1220. doi:10.1007/s00170-007-0931-1
Gupta JND, Stafford JEF (2006) Flowshop scheduling research after five decades. Eur J Oper Res 169:699–711. doi:10.1016/j.ejor.2005.02.001
Gangadharan R, Rajendran C (1993) Heuristic algorithms for scheduling in no-wait flow shop. Int J Prod Econ 32:285–290. doi:10.1016/0925-5273(93) 90042-J
Hejazi SR, Saghafian S (2005) Flowshop- scheduling problems with makespan criterion: a review. Int J Prod Res 43:2895–2929. doi:10.1080/0020754050056417
Heller J (1960) Some numerical experiments for an MxJ flow shop and its decision- theoretical aspects. Oper Res 8:178–184. doi:10.1287/opre.8.2.178
Jarboui B, Ibrahim S, Siarry P, Rebai A (2008) A combinational particle swarm optimisation for solving permutation flowshop problems. Comput Ind Eng 54:526–538. doi:10.1016/j.cie.2007.09.006
Kennedy J, Eberhart R (1995) Particle swarm optimization. Proc IEEE Int Conf Neural Netw 1995:1942–1948. doi:10.1109/ICNN.1995.488968
Knowles JD, Corne DW (1999) The Pareto archived evolution strategy: a new baseline algorithm for multi-objective optimization. In: Congress on Evolutionary Computation, Washington, DC, IEEE Service Center, 98–105
Laha D, Chakraborty UK (2008) An efficient heuristic approach to total flowtime minimization in permutation flowshop scheduling. Int J Adv Manuf Technol 38:1018–1025. doi:10.1007/s00170-007-1156-z
Laha D, Chakraborty UK (2009) A constructive heuristic for minimizing makespan in no-wait flow shop scheduling. Int J Adv Manuf Technol. doi:10.1007/s00170-008-1545-0
Lian Z, Gu X, Jiao B (2008) A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan. Chaos Solitons Fractals 35:851–861. doi:10.1016/j.chaos.2006.05.082
Liu B, Wang L, Jin YH (2007) An effective PSO-based memetic algorithm for flow shop scheduling. IEEE Trans Syst Man Cybern C 37:18–27. doi:10.1109/TSMCB.2006.883272
Liu J, Reeves CR (2001) Constructive and composite heuristic solutions to the P//∑Ci scheduling problem. Eur J Oper Res 132:439–452. doi:10.1016/S0377-2217(00) 00137-5
Nawaz M, Enscore JR, Ham I (1983) A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega 11:91–95. doi:10.1016/0305-0483(83) 90088-9
Pasupathy T, Rajendran C, Suresh RK (2006) A multi-objective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs. Int J Adv Manuf Technol 27:804–815. doi:10.1007/s00170-004-2249-6
Ponnambalam SG, Jagannathan H, Kataria M (2004) A TSP-GA multi-objective algorithm for flow-shop scheduling. Int J Adv Manuf Technol 23:909–915. doi:10.1007/s00170-003-1731-x
Rajendran C (1994) A no-wait flow shop scheduling heuristic to minimize makespan. J Oper Res Soc 45:472–478
Rajendran C, Ziegler H (2004) Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. Eur J Oper Res 155:426–438. doi:10.1016/S0377-2217(02) 00908-6
Rahimi-Vahed A, Mirghorbani S (2007) A multi-objective particle swarm for a flow shop scheduling problem. J Comb Optim 13:79–102. doi:10.1007/s10878-006-9015-7
Reeves CR (1995) A genetic algorithm for flowshop sequencing. Comput Oper Res 22:5–13. doi:10.1016/0305-0548(93) E0014-K
Ruiz R, Maroto C (2004) A comprehensive review and evaluation of permutation flowshop heuristics. Eur J Oper Res 165:479–494. doi:10.1016/j.ejor.2004.04.017
Sha DY, Hsu CY (2006) A hybrid particle swarm optimization for job shop scheduling problem. Comput Ind Eng 51:791–808. doi:10.1016/j.cie.2006.09.002
Sha DY, Hsu CY (2008) A new particle swarm optimization for the open shop scheduling problem. Comput Oper Res 35:3243–3261. doi:10.1016/j.cor.2007.02.019
Stützle T (1998) Applying iterated local search to the permutation flow shop problem. Tech Rep, AIDA-98-04, FG Intellektik, TU Darmstadt
Taillard E (1993) Benchmarks for basic scheduling problems. Eur I Oper Res 64:278–285. doi:10.1016/0377-2217(93) 90182-M
Tasgetiren MF, Liang YC, Sevkli M, Gencyilmaz G (2007) A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. Eur J Oper Res 177:1930–1947. doi:10.1016/j.ejor.2005.12.024
Yagmahan B, Yenisey MM (2008) Ant colony optimization for multi-objective flow shop scheduling problem. Comput Ind Eng 54:411–420. doi:10.1016/j.cie.2007.08.003
Zhang H, Li X, Li H, Huang F (2005) Particle swarm optimization-based schemes for resource-constrained project scheduling. Auto Const 14:393–404. doi:10.1016/j.autcon.2004.08.006
Zizter E, Laumanns M, Thiele L (2001) SPEA2: Improving the strength Pareto evolutionary algorithm. Computer Engineering and Networks Laboratory (TIK) – Report 103 Sept 2001
Author information
Authors and Affiliations
Corresponding author
Additional information
The English in this document has been checked by at least two professional editors, both native speakers of English. For a certificate, see: http://www.textcheck.com/cgi-bin/certificate.cgi?id=emRe2r
Rights and permissions
About this article
Cite this article
Sha, D.Y., Hung Lin, H. A particle swarm optimization for multi-objective flowshop scheduling. Int J Adv Manuf Technol 45, 749–758 (2009). https://doi.org/10.1007/s00170-009-1970-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-009-1970-6