Scheduling to Minimize the Sum of Weighted Total Flow Time and Makespan in a Permutation Flow Shop with Setup Time

Abstract:

The Permutation Flow shop Scheduling Problem is a typical combinational optimization problem and has been proved to be strongly NP-hard. This paper deals with B-GRASP algorithm meta-heuristic in finding the solution and in analyzing the best the optimal schedule, thus minimizing the bi-objectives such as weighted makespan and total flow time. The proposed approach is evaluated using benchmark problems taken from Taillard and compared with simulated annealing algorithm. Computational experiments indicate that the proposed B-GRASP algorithm is a feasible and effective approach for the multiobjective problem.

• Periodical: Applied Mechanics and Materials (Volumes 766-767)
• Pages: 989-994
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.766-767.989
• Online since: June 2015
• Authors: M. Saravanan, S. Joseph Dominic Vijayakumar*, R. Srinivasan, S. Paul Singarayar
• Keywords: B-GRASP Approach, Flow Time, Makespan, Permutation Flowshop

References

[1] K. C. Ying, S.W. Lin, Multi-heuristic desirability ant colony system heuristic for non- permutation flow shop scheduling problems, International Journal of Advanced Manufacturing Technology, 33 (2007) 793-802.

DOI: 10.1007/s00170-006-0492-8

[2] M.S. Nagano, R. Ruiz and L.A.N. Lorena, A Constructive Genetic Algorithm for permutation flow shop scheduling in Computers & Industrial Engineering, 55 (2008) 195-207.

DOI: 10.1016/j.cie.2007.11.018

[3] M.R. Garey, D.S. Johnson and R. Sethi, The Complexity of flow shop and job shop scheduling, Mathematics of Operations Research, 1 (1976) 117–129.

[4] B. Jarboui, S. Ibrahim, P. Siarry and A. Rebai, A combinatorial particle swarm optimization for solving permutation flow shop problems, Computers & Industrial Engineering, 54 (2008) 526- 538.

DOI: 10.1016/j.cie.2007.09.006

[5] S.M. Johnson, Optimal two-and three-stage production schedules, Naval Research Logistics Quarterly 1(1954) 61-68.

DOI: 10.1002/nav.3800010110

[6] B. Yagmahan, MM. Yenisey, A multi-objective ant colony system algorithm for flow shop scheduling problem. Expert System Applications 37: 1361–1368, (2010).

DOI: 10.1016/j.eswa.2009.06.105

[7] J. Behnamian, S.M.T. Fatemi Ghomi and M. Zandieh, A multi-phase covering Pareto-optimal front method to multi-objective scheduling in a realistic hybrid flow shop using a hybrid meta-heuristic, Expert Systems with Applications, 36 (2009).

DOI: 10.1016/j.eswa.2009.02.080

[8] C.S. Sung, J.I. Min, Theory and methodology scheduling in a two machine flow shop with batch processing machine(s) for earliness measure under a common due date, European Journal of Operational Research, 131(2001) 95-106.

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

[9] C. Rajendran, Theory and methodology heuristics for scheduling in flow shop with multiple objectives,. European Journal of Operation Research, 82 (1995)540 −555.

DOI: 10.1016/0377-2217(93)e0212-g

[10] B. Yagmahan, M.M. Yenisey, Ant colony optimization for multi-objective flow shop scheduling problem, Computers and Industrial Engineering, 54 (2008) 411-420.

DOI: 10.1016/j.cie.2007.08.003

[11] J.M. Framinan, R. Leisten and R. Ruiz-Usano, Comparison of heuristics for flow time minimization in permutation flow shops, Computers & Operations Research, 32(2005)1237–1254.

DOI: 10.1016/j.cor.2003.11.002

[12] R. Ruiz, C. Maroto, A comprehensive review and evaluation of permutation flow shop heuristics, European Journal of Operational Research, 165 (2005) 479-494.

DOI: 10.1016/j.ejor.2004.04.017

[13] Shih-Wei Lin, Kuo-Ching Ying, Minimizing makespan and total flowtime in permutation flowshops by a bi-objective multi-start simulated-annealing algorithm Original Research Article Computers & Operations Research, Volume 40, Issue 6, 1625-1647, (2013).

DOI: 10.1016/j.cor.2011.08.009

[14] T.A. Feo, M.G.C. Resende, Greedy randomized adaptive search procedures, Journal of Global Optimization, 6 (1995)109–133.

DOI: 10.1007/bf01096763

[15] S. Binato, W.J. Hery, D.M. Loewenstern and M.G.C. Resende, A GRASP for job shop scheduling Technical Report, AT&T Labs Research, (2000).

DOI: 10.1007/978-1-4615-1507-4_3

[16] T.A. Feo, M.G.C. Resende, A probabilistic heuristic for a computationally difficult set covering problem, Operation Research Letters, 8 (1989) 67-71.

DOI: 10.1016/0167-6377(89)90002-3

[17] P. Festa, M.G.C. Resende, GRASP: An annotated bibliography, In C.C. Ribeiro and p. Hansen, editors, Essays and Surveys in meta-heuristics, Kluwer Academic Publishers, 2002, 325-367.

DOI: 10.1007/978-1-4615-1507-4_15

[18] S. Kirkpatrik, Optimization by simulated annealing, Science 220(1983) 671–680.

[19] E. Taillard, Benchmark for basic scheduling problems, European Journal of Operational Research, 64 (1993) 278-285.

DOI: 10.1016/0377-2217(93)90182-m