Palabras clave
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
Cómo citar
Resumen
En este artículo, se propone un enfoque basado en Búsqueda Tabú para el problema de una sola máquina, con retardo ponderado, con puestas a punto que dependen de la sucesión. La principal contribución es el balance obtenido entre las estrategias de intensificación y diversificación. La estrategia de combinar amplios pasos de optimización, memoria basada en la frecuencia, intensificación por descomposición con una intensificación adicional que usa religamen de caminos, produce buenas soluciones con un costo computacional bajo. Nuestro enfoque de Búsqueda Tabú es comparado con el método de inicio múltiple que emplea el vecindario de todos los pares. Se reportan resultados de experimentos computacionales para un conjunto de problemas test generados aleatoriamente.
Citas
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.