Keywords
scheduling problems
weighted tardiness
sequence depend- setups
Búsqueda Tabú
problemas de calendarización
retardo ponderado
puestas a punto que dependen de la sucesión
How to Cite
Abstract
In this paper, a Tabu Search Approach for the weighted tardiness single machine problem with sequence-dependent setups is proposed. The main contribution is the balance obtained between intensification and diversification strategies. The strategy of combine large step optimization, frequency-based memory, intensification by decomposition supplementing this with an additional intensification using path relinking produce good solutions with a low computational cost. Our Tabu Search approach is compared with a re-start method that employs the all-pairs neighborhood. Results of computational experiments are reported for a set of randomly generated test problems.
References
M. Laguna and R. Martí (1997) “Grasp and path relinking for 2-layer straight line crossing minimization”, University of Colorado at Boulder.
McNaughton, R. (1959) “Scheduling with deadlines and loss functions”, Management Science 6(1): 1–12.
Held, M.; Karp, R.M. (1962) “A dynamic programming approach to sequencing problems”, Journal of the Society for Industrial and Applied Mathematics 10(1): 196–210.
Lawler, E. (1964) “On scheduling problems with deferral costs”, Management Science 11(2): 280–288.
Glover, F. (1986) “Future paths for integer programming and links to artificial intelligence”, Computers and Ops. Res. 5: 533–549.
Glover, F.; Taillard, E.; de Werra, D. (1993) “A user’s guide to tabu search”, Ann. Oper. Res. 41: 3–28.
Glover, F.; Laguna, M. (1993) “Modern heuristic techniques for combinatorial problems”, published in the Halsted Press, John Wiley & Sons, Inc., chapter 3: 70–147.
Glover, F. (1995) Tabu Search Fundamentals and Uses.
Hansen, P. (1986) “The steepest ascent mildest descent heuristic for combinatorial programming”, Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy.
Ramalhinho-Lourenço, H.; Zwijnenburg, M. (1998) “Combining the large-step optimization with tabu-search: application to the job-shop scheduling problem”, in: Meta-Heuristics: Theory and Applications, Kluwer Academic Publishers, Ch 14: 219–235.
Emmons, H. (1969) “One-machine sequencing to minimize certain functions of job tardiness”, The Journal of the Operations Research Society of America 17(4): 701–715.
Shwimer, J. (1972) “On the N-job, one-machine, sequence-independent scheduling problem with tardiness penalties: a branch-bound solution”, Management Science 18(6), B-301.
Morton, T.E.; Pentico, D.W. (1993) “Heuristic scheduling systems, with applications to production systems and project management”, Wiley Series in Engineering and Technology Management.
Franca, P.M.; Mendes, A.; Moscato, P. (1999) “A memetic algorithm for the total tardiness single machine scheduling problem”, Working Paper, Universidade Estadual de Campinas.
Tan, K.C.; Narasimhan, R (1997) “Minimizing tardiness on a single processor with sequence-dependent setup times: a simulated annealing approach”, OMEGA, International Journal of Management Science 2516: 619–634.
Beausoleil, R. (2000) “Intensification and diversification strategies with tabu search: one-machine problem with tardiness objective”, in: O. Cairo, L.E. Sucar & F.J. Cantú (Eds.) Lectures Notes on Artificial Intelligence 1793, Springer-Verlag: 52–62.
Rubin, P.A.; Ragatz, G.L. (1995) “Scheduling in a sequence dependent setup environment with genetic search”, Computers Ops. Res. 22(1): 85–99.