Research Article
Metaheuristics for a job scheduling problem with smoothing costs relevant for the car industry
Jean Respen,
Nicolas Zufferey,
Edoardo Amaldi,
Jean Respen
Geneva School of Economics and Management, GSEM - University of Geneva, Geneva, Switzerland
Search for more papers by this authorCorresponding Author
Nicolas Zufferey
Geneva School of Economics and Management, GSEM - University of Geneva, Geneva, Switzerland
Correspondence to: N. Zufferey; e-mail: [email protected]Search for more papers by this authorEdoardo Amaldi
Dipartimento di Elettronica, Informazione e Bioingegneria, Politecnico di Milano, Milano, Italy
Search for more papers by this authorJean Respen,
Nicolas Zufferey,
Edoardo Amaldi,
Jean Respen
Geneva School of Economics and Management, GSEM - University of Geneva, Geneva, Switzerland
Search for more papers by this authorCorresponding Author
Nicolas Zufferey
Geneva School of Economics and Management, GSEM - University of Geneva, Geneva, Switzerland
Correspondence to: N. Zufferey; e-mail: [email protected]Search for more papers by this authorEdoardo Amaldi
Dipartimento di Elettronica, Informazione e Bioingegneria, Politecnico di Milano, Milano, Italy
Search for more papers by this authorAbstract
We study a new multiobjective job scheduling problem on nonidentical machines with applications in the car industry, inspired by the problem proposed by the car manufacturer Renault in the ROADEF 2005 Challenge. Makespan, smoothing costs and setup costs are minimized following a lexicographic order, where smoothing costs are used to balance resource utilization. We first describe a mixed integer linear programming (MILP) formulation and a network interpretation as a variant of the well-known vehicle routing problem. We then propose and compare several solution methods, ranging from greedy procedures to a tabu search and an adaptive memory algorithm. For small instances (with up to 40 jobs) whose MILP formulation can be solved to optimality, tabu search provides remarkably good solutions. The adaptive memory algorithm, using tabu search as an intensification procedure, turns out to yield the best results for large instances. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 67(3), 246–261 2016
REFERENCES
- A. Allahverdi, C.T. Ng, T.C.E. Cheng, and M. Kovalyov, A survey of scheduling problems with setup times or costs, Eur J Oper Res 187 (2008), 985–1032.
- A. Anglani, A. Grieco, E. Guerriero, and R. Musmanno, Robust scheduling of parallel machines with sequence-dependent set-up costs, Eur J Oper Res 161 (2005), 704–720.
-
P. Baptiste and C. Le Pape, Scheduling a single machine to minimize a regular objective function under setup constraints, Discr Optim 2 (2005), 83–99.
10.1016/j.disopt.2004.12.003 Google Scholar
- J. Bautista, J. Pereira, and B. Adenso-Daz, A GRASP approach for the extended car sequencing problem, J Scheduling 11 (2008), 3–16.
- C. Becker and A. Scholl, A survey on problems and methods in generalized assembly line balancing, Eur J Oper Res 168 (2006), 694–715.
- M. Chica, Ó. Cordón, S. Damas, and J. Bautista, Multiobjective constructive heuristics for the 1/3 variant of the time and space assembly line balancing problem: ACO and random greedy search, Inf Sci 180 (2010), 3465–3487.
- M. Ciavotta, P. Detti, C. Meloni, and M. Pranzo, A bi-objective coordination setup problem in a two-stage production system, Eur J Oper Res 189 (2008), 734–745.
- J.-F. Cordeau, M. Gendreau, G. Laporte, J.-Y. Potvin, and F. Semet, A guide to vehicle routing heuristics, J Oper Res Soc 53 (2002), 512–522.
- J.-F. Cordeau, G. Laporte, and F. Pasin, Iterated tabu search for the car sequencing problem, Eur J Oper Res 191 (2008), 945–956.
-
M. Dorigo and T. Stützle, “ The ant colony optimization metaheuristic: algorithms, applications, and advances,” Handbook of metaheuristics, Springer, New York, Vol. 57, 2003, pp. 251–285.
10.1007/0-306-48056-5_9 Google Scholar
- M. Ehrgott, “ Multicriteria optimization,” Lecture Notes in Economics and Mathematical Systems, Springer-Verlag Berlin Heidelberg, Vol. 491, Springer, 2005.
- M. Ehrgott and X. Gandibleux, A survey and annotated bibliography of multiobjective combinatorial optimization, OR Spectrum 22 (2000), 425–460.
- B. Estellon, F. Gardi, and K. Nouioua, Two local search approaches for solving real-life car sequencing problems, Eur J Oper Res 191 (2008), 928–944.
- T.A. Feo and M.G. Resende, Greedy randomized adaptive search procedures, J Glob Optim 6 (1995), 109–133.
- B. Gacias, C. Artigues, and P. Lopez, Parallel machine scheduling with precedence constraints and setup times, Comput Oper Res 37 (2010), 2141–2151.
- P. Galinier, A. Hertz, and N. Zufferey, An adaptive memory algorithm for the graph coloring problem, Discr Appl Math 156 (2008), 267–279.
- M. Garey and D.S. Johnson, Computer and intractability: A guide to the theory of NP-completeness, Freeman, San Francisco, 1979.
-
M. Gendreau, G. Laporte, and J.-Y. Potvin, “ Metaheuristics for the VRP,” The vehicle routing problem, P. Toth and D. Vigo (Editors), SIAM monographs on discrete mathematics and applications, Philadelphia, 2002, pp. 129–154.
10.1137/1.9780898718515.ch6 Google Scholar
- M. Gendreau and J.-Y. Potvin, Handbook of metaheuristics. International series in operations research & management science, Springer US, Springer, 2010.
- M. Gendreau and J.-Y. Potvin, “ Tabu search,” Handbook of metaheuristics, international series in operations research & management science, M. Gendreau and J.-Y. Potvin (Editors), Springer, Springer US, 2010, pp. 41–59.
-
M. Gendreau, J.-Y. Potvin, O. Bräumlaysy, G. Hasle, and A. Løkketangen, “ Metaheuristics for the vehicle routing problem and its extensions: A categorized bibliography,” The vehicle routing problem: Latest advances and new challenges, volume 43 of operations research/computer science interfaces series, Springer, 2008, pp. 143–169.
10.1007/978-0-387-77778-8_7 Google Scholar
-
F. Glover, Tabu search—Part I, ORSA J Comput 1 (1989), 190–205.
10.1287/ijoc.1.3.190 Google Scholar
- F. Glover, D. Klingman, and N. Phillips, Netform modeling and applications, Interfaces 20 (1990), 7–27.
- F. Glover, C. McMillan, and D. Klingman, The NETFORM concept: A more effective model form and solution procedure for large scale nonlinear problems, Proceedings of the 1977 annual conference, ACM, 1977, pp. 283–289.
- B.L. Golden, S. Raghavan, and E.A. Wasil, The vehicle routing problem: latest advances and new challenges, Springer US, Springer US, Vol. 43, Springer, 2008.
- A. Hertz, D. Schindl, and N. Zufferey, A solution method for a car fleet management problem with maintenance constraints, J Heuristics 15 (2009), 425–450.
- 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.
- G. Laporte, Fifty years of vehicle routing, Transport Sci 43 (2009), 408–416.
- T. Loukil, J. Teghem, and D. Tuyttens, Solving multi-objective production scheduling problems using metaheuristics, Eur J Oper Res 161 (2005), 42–61.
- L. Luyet, S. Varone, and N. Zufferey, An Ant algorithm for the Steiner tree problem in graphs, Lect Notes Comput Sci 4448 (2007), 42–51.
- G. Moslehi and M. Mahnam, A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search, Int J Prod Econ 129 (2011), 14–22.
- M. Nawaz, E. E. Enscore, and I. Ham, A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, Omega 11 (1983), 91–95.
- M. Pinedo, Scheduling: Theory, algorithms, and systems, 3rd edition. Prentice Hall, 2008.
- M.G.C. Resende and C.C. Ribeiro, “ Greedy randomized adaptive search procedures: Advances, hybridizations, and applications,” Handbook of metaheuristics, volume 146 of international series in operations research & management science, Springer US, 2010, pp. 283–319.
- J. Respen, N. Zufferey, and E. Amaldi, Heuristics for a multi-machine multi-objective job scheduling problem with smoothing costs, 1st IEEE International Conference on Logistics Operations Management, Le Havre, France, 2012, 2012.
- C.C. Ribeiro, D. Aloise, T.F. Noronha, C. Rocha, and S. Urrutia, A hybrid heuristic for a multi-objective real-life car sequencing problem with painting and assembly line constraints, Eur J Oper Res 191 (2008), 981–992.
-
Y. Rochat and E. Taillard, Probabilistic diversification and intensification in local search for vehicle routing, J Heuristics 1 (1995), 147–167.
10.1007/BF02430370 Google Scholar
- D. Schindl and N. Zufferey, Solution methods for fuel supply of trains, Inf Syst Oper Res 51 (2013), 22–29.
- H.D. Sherali and P.J. Driscoll, On tightening the relaxations of Miller-Tucker-Zemlin formulations for asymmetric traveling salesman problems, Oper Res 50 (2002), 656–669.
- C. Solnon, V.D. Cung, A. Nguyen, and C. Artigues, The car sequencing problem: Overview of state-of-the-art methods and industrial case-study of the ROADEF 2005 challenge problem, Eur J Oper Res 191 (2008), 912–927.
- S. Webster, P.D. Jog, and A. Gupta, A genetic algorithm for scheduling job families on a single machine with arbitrary earliness/tardiness penalties and an unrestricted common due date, Int J Prod Res 36 (1998), 2543–2551.
- N. Zufferey, Metaheuristics: Some principles for an efficient design, Comput Technol Appl 3 (2012), 446–462.
- N. Zufferey, Optimization by ant algorithms: Possible roles for an individual ant, Optim Lett 6 (2012), 963–973.
- N. Zufferey, M. Studer, and E.A. Silver, Tabu search for a car sequencing problem, Proceedings of the 19th International Florida Artificial Intelligence Research Society Conference, FLAIRS 2006, May 11–13, Melbourne (Florida), USA, 2006, pp. 457–462.
