Algorithms for bicriteria minimization in the permutation flow shop scheduling problem

Ethel Mokotoff

doi:10.3934/jimo.2011.7.253

Article Contents

2011, Volume 7, Issue 1: 253-282. Doi: 10.3934/jimo.2011.7.253

This issue Previous Article New heuristics for solving the economic lot scheduling problem with reworks Next Article

Algorithms for bicriteria minimization in the permutation flow shop scheduling problem

Ethel Mokotoff^1,

1.
Departamento de Fundamentos de Economía, Universidad de Alcalá, Alcalá de Henares, Madrid, 28802

Received: July 31, 2009

Revised: October 31, 2010

Published: December 2010

Abstract Related Papers Cited by

Abstract

This paper presents two bi-objective simulated annealing procedures to deal with the classical permutation flow shop scheduling problem considering the makespan and the total completion time as criteria. The proposed methods are based on multi-objective simulated annealing techniques combined with constructive and heuristic algorithms. A computational experiment has been carried out and different metrics have been computed to check various attributes of each method. For all the tested instances a net set of potentially efficient schedules has been obtained and compared with previously published results. Results indicate that the proposed algorithms provide efficient solutions with little computational effort which can serve as input for interactive procedures.

Keywords:

Mathematics Subject Classification: Primary: 90B35; 90B50; 90C29; Secondary: 90C59.

Citation:

Related Papers

Cited by

References

[1]	J. Arroyo and V. Armentano, Genetic local search for multi-objective flowshop scheduling problems, Eur. J. Oper. Res., 167 (2005), 717-38.doi: 10.1016/j.ejor.2004.07.017.
[2]	T. P. Bagchi, "Multiobjective Scheduling by Genetic Algorithms," Kluwer Academic Publishers, Dordrecht, 1999.
[3]	P. C. Chang, S. H. Chen and C. H. Liu, Sub-population genetic algorithm with mining gene structures for multiobjective flowshop scheduling problems, Expert. Syst. Appl., 33 (2007), 762-77.doi: 10.1016/j.eswa.2006.06.019.
[4]	P. C. Chang, J. C. Hsieh and S. G. Lin, The development of gradual priority weighting approach for the multi-objective flowshop scheduling problem, Int. J. Prod. Econ., 79 (2002), 171-83.doi: 10.1016/S0925-5273(02)00141-X.
[5]	P. Czyzak and A. Jaszkiewicz, Pareto Simulated Annealing-a metaheuristic technique for multiple objective combinatorial optimization, J. Multicriteria Dec. Anal., 7 (1998), 34-47.doi: 10.1002/(SICI)1099-1360(199801)7:1<34::AID-MCDA161>3.0.CO;2-6.
[6]	R. L. Daniels and R. J. Chambers, Multiobjective flow-shop scheduling, Nav. Res. Log., 37 (1990), 981-995.doi: 10.1002/1520-6750(199012)37:6<981::AID-NAV3220370617>3.0.CO;2-H.
[7]	J. Dorn, M. Girsch, G. Skele and W. Slany, Comparison of iterative improvement techniques for schedule optimization, Eur. J. Oper. Res., 94 (1996), 349-361.doi: 10.1016/0377-2217(95)00162-X.
[8]	M. Ehrgott and X. Gandibleux, Multiobjective Combinatorial Optimization: Theory, Methodology, and Applications, in "Multiple Criteria Optimization: State of the Art Annotated Bibliographic Surveys" (eds. M. Ehrgott and X. Gandibleux), Kluwer Academic Publishers, Boston, (2002), 369-444.
[9]	V. A. Emelichev and V. A. Perepelista, On cardinality of the set of alternatives in discrete many-criterion problems, Discrete Math. Appl., 2 (1992), 461-471.doi: 10.1515/dma.1992.2.5.461.
[10]	J. M. Framinan, R. Leisten and R. Ruiz-Usano, Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation, Eur. J. Oper. Res., 141 (2002), 559-569.doi: 10.1016/S0377-2217(01)00278-8.
[11]	M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness," Freeman, San Francisco, 1979.
[12]	M. Geiger, On operators and search space topology in multi-objective flow shop scheduling, Eur. J. Oper. Res., 181 (2007), 195-206.doi: 10.1016/j.ejor.2006.06.010.
[13]	R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann. Discrete Math., 5 (1979), 287-326.doi: 10.1016/S0167-5060(08)70356-X.
[14]	J. N. D. Gupta, V. R. Neppalli and F. Werner, Minimizing total flow time in a two-machine flowshop problem with minimum makespan, Int. J. Prod. Econ., 69 (2001), 323-338.doi: 10.1016/S0925-5273(00)00039-6.
[15]	J. C. Ho and Y. L. Chang, A new heuristic for the n-job, m-machine flowshop problem, Eur. J. Oper. Res., 52 (1991), 194-202.doi: 10.1016/0377-2217(91)90080-F.
[16]	J. A. Hoogeveen, "Single-Machine Bicriteria Scheduling," Ph.D thesis, The Netherlands Technology University in Amsterdam, 1992.
[17]	G. Huang and A. Lim, Fragmental optimization on the 2-machine bicriteria flowshop scheduling problem, in "Proceedings of 15th IEEE International Conference on Tools with Artificial Intelligence," (1992), 33-75.
[18]	E. Ignall and L. E. Schrage, Application of the branch-and-bound technique to some flow-shop scheduling problems, Oper. Res., 13 (1965), 400-412.doi: 10.1287/opre.13.3.400.
[19]	H. Ishibuchi and T. Murata, A multi-objective genetic local search algorithm and its application to flowshop scheduling, IEEE T. Syst. Man. Cy. C., 28 (1998), 392-403.doi: 10.1109/5326.704576.
[20]	A. Jaszkiewicz, A comparative study of multiple-objective metaheuristics on the bi-objective set covering problem and the pareto memetic algorithm, Annals of Operations Research, 13 (2004), 135-158.doi: 10.1023/B:ANOR.0000039516.50069.5b.
[21]	S. M. Johnson, Optimal two- and three-stage production schedules with setup times included, Nav. Res. Log., 1 (1954), 61-68.doi: 10.1002/nav.3800010110.
[22]	D. F. Jones, S. K. Mirrazavi and M. Tamiz, Multi-objective meta-heuristics: An overview of the current state of the art, Eur. J. Oper. Res., 137 (2002), 1-9.doi: 10.1016/S0377-2217(01)00123-0.
[23]	S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), 671-680.doi: 10.1126/science.220.4598.671.
[24]	J. Knowles and D. Corne, On Metrics Comparing Nondominated Sets, in "Proceedings of the 2002 Congress on Evolutionary Computation Conference," IEEE Press, (2002), 711-716.
[25]	J. D. Landa-Silva, E. K. Burke and S. Petrovic, An introduction to multiobjective metaheuristics for scheduling and timetabling, Lect. Notes Econ. Math., 535 (2004), 91-129.doi: 10.1007/978-3-642-17144-4_4.
[26]	C. J. Liao, W. C. Yu and C. B. Joe, Bicriterion scheduling in the two-machine flowshop, J. Oper. Res. Soc., 48 (1997), 929-935.
[27]	G. B. McMahon, Optimal production schedules for flow shop, Can. Oper. Res. Soc. J., 7 (1969), 141-151.
[28]	G. Minella, R. Ruiz and M. Ciavotta, A review and evaluation of multi-objective algorithms for the flowshop scheduling problem, Informs. Journal on Computing, 20 (2007), 451-471.doi: 10.1287/ijoc.1070.0258.
[29]	E. Mokotoff, Multi-objective simulated annealing for permutation flow shop problems, in "Computational Intelligence in Flow Shop and Job Shop Scheduling" (ed. U. Chakraborty), Springer Verlag, (2009), 101-150.doi: 10.1007/978-3-642-02836-6_4.
[30]	T. Murata, H. Ishibuchi and H. Tanaka, Multi-objective genetic algorithm and its applications to flowshop scheduling, Comp. Ind. Eng., 30 (1996), 957-968.doi: 10.1016/0360-8352(96)00045-9.
[31]	A. Nagar, S. S. Heragu and J. Haddock, A branch and bound approach for a two machine flowshop scheduling problem, J. Oper. Res. Soc., 46 (1995), 721-734.
[32]	M. Nawaz, E. E. Jr Enscore and I. Ham, A heuristic algorithm for the m machine, n job flowshop sequencing problem, OMEGA-Int J. Manage S., 11 (1983), 91-95.doi: 10.1016/0305-0483(83)90088-9.
[33]	V. L. Neppalli, C. L. Chen and J. N. D. Gupta, Genetic algorithms for the two-stage bicriteria flowshop problem, Eur. J. Oper. Res., 95 (1996), 356-373.doi: 10.1016/0377-2217(95)00275-8.
[34]	S. Parthasarathy and C. Rajendran, An experimental evaluation of heuristics for scheduling in a real-life flowshop with sequence-dependent setup times of jobs, Int. J. Prod. Econ., 49 (1997), 255-263.doi: 10.1016/S0925-5273(97)00017-0.
[35]	T. Pasupathy, C. Rajendran and R. K. Suresh, 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 (2006), 804-815.doi: 10.1007/s00170-004-2249-6.
[36]	C. Rajendran, Two-stage flowshop scheduling problem with bicriteria, J. Oper. Res. Soc., 43 (1992), 879-884.
[37]	C. Rajendran, Heuristic algorithm for scheduling in a flowshop to minimize total flowtime, Int. J. Prod. Econ., 29 (1993), 65-73.doi: 10.1016/0925-5273(93)90024-F.
[38]	C. Rajendran, Heuristics for scheduling in flowshop with multiple objectives, Eur. J. Oper. Res., 82 (1995), 540-555.doi: 10.1016/0377-2217(93)E0212-G.
[39]	A. H. G. Rinnooy Kan, "Machine Scheduling problems: Classification, Complexity and Computations," Martinus Nijhoff, The Hague, 1976.
[40]	S. Sayin and S. Karabati, A bicriteria approach to the two-machine flow shop scheduling problem, Eur. J. Oper. Res., 113 (1999), 435-449.doi: 10.1016/S0377-2217(98)00009-5.
[41]	W. J. Selen and D. D. Hott, A mixed-integer goal-programming formulation of the standard flow-shop scheduling problem, J. Oper. Res. Soc., 12 (1986), 1121-1128.
[42]	P. Serafini, Simulated annealing for multiple objective optimization problems, in "Proceedings of the Tenth International Conference on Multiple Criteria Decision Making," Taipei, (1992), 87-96.
[43]	F. S. Sivrikaya-Serifoglu and G. Ulusoy, A bicriteria two machine permutation flowshop problem, Eur. J. Oper. Res., 107 (1998), 414-430.doi: 10.1016/S0377-2217(97)00338-X.
[44]	N. Srinivas and K. Deb, Multiobjective function optimization using nondominated sorting genetic algorithms, Evol. Comp., 2 (1995), 221-248.doi: 10.1162/evco.1994.2.3.221.
[45]	V. T'kindt and J. C. Billaut, "Multicriteria scheduling: Theory, Models and Algorithms," 2nd edition, Springer, Berlin, 2006.
[46]	V. T'kindt, J. N. D. Gupta and J. C. Billaut, Two machine flowshop scheduling problem with a secondary criterion, Comp. Oper. Res., 30 (2003), 505-526.doi: 10.1016/S0305-0548(02)00021-7.
[47]	V. T'kindt, N. Monmarche and F et al. Tercinet, An ant colony optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem, Eur. J. Oper. Res., 142 (2002), 250-257.doi: 10.1016/S0377-2217(02)00265-5.
[48]	E. Taillard, Some efficient heuristic methods for the flow shop sequencing problem, Eur. J. Oper. Res., 47 (1990), 67-74.doi: 10.1016/0377-2217(90)90090-X.
[49]	E. Taillard, Benchmark for basic scheduling problems, Eur. J. Oper. Res., 64 (1993), 278-285.doi: 10.1016/0377-2217(93)90182-M.
[50]	T. K. Varadharajan and C. Rajendran, A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs, Eur. J. Oper. Res., 167 (2005), 772-795.doi: 10.1016/j.ejor.2004.07.020.
[51]	J. M. Wilson, Alternative formulation of a flow shop scheduling problem, J. Oper. Res. Soc., 40 (1989), 395-399.
[52]	B. Yagmahan and M. M. Yenisey, Ant colony optimization for multi-objective flow shop scheduling problem, Comp. Ind. Eng., 54 (2008), 411-420.doi: 10.1016/j.cie.2007.08.003.
[53]	E. Zitzler, "Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications," Ph.D thesis, Swiss Federal Institute of Technology in Zurich, 1999.