A Tabu search Approach for the Weighted Tardiness with Sequence-Dependent Setups in one-machine Problem

• Beausoleil, Ricardo P. ^[1]
  1. [1] Centro de Matemática y Física Teórica
• Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 9, Nº. 1, 2002, págs. 35-46
• Idioma: inglés
• DOI: 10.15517/rmta.v9i1.208
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    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.

  • English

    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.

• Referencias bibliográficas
  • 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...
  • 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,...
  • 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...
  • Ramalhinho-Lourenço, H.; Zwijnenburg, M. (1998) “Combining the large-step optimization with tabu-search: application to the job-shop scheduling...
  • Emmons, H. (1969) “One-machine sequencing to minimize certain functions of job tardiness”, The Journal of the Operations Research Society...
  • Shwimer, J. (1972) “On the N-job, one-machine, sequence-independent scheduling problem with tardiness penalties: a branch-bound solution”,...
  • Morton, T.E.; Pentico, D.W. (1993) “Heuristic scheduling systems, with applications to production systems and project management”, Wiley Series...
  • Franca, P.M.; Mendes, A.; Moscato, P. (1999) “A memetic algorithm for the total tardiness single machine scheduling problem”, Working Paper,...
  • Tan, K.C.; Narasimhan, R (1997) “Minimizing tardiness on a single processor with sequence-dependent setup times: a simulated annealing approach”,...
  • Beausoleil, R. (2000) “Intensification and diversification strategies with tabu search: one-machine problem with tardiness objective”, in:...
  • Rubin, P.A.; Ragatz, G.L. (1995) “Scheduling in a sequence dependent setup environment with genetic search”, Computers Ops. Res. 22(1): 85–99.