Palabras clave
metaheurísticas
tardanza ponderada
GRASP
Cómo citar
Resumen
Este artículo presenta los resultados experimentales obtenidos de secuenciar trabajos en una máquina, a fin de minimizar la tardanza total ponderada mediante un algoritmo GRASP. Los resultados se compararon con los valores óptimos o mejores valores reportados hasta el momento para cada una de las instancias de OR-Library y se encontró una excelente relación entre la calidad de los resultados (93% de las instancias se solucionaron con una desviación máxima del 1% respecto a estos valores) y el esfuerzo computacional y de implementación requerido. El algoritmo se implementó usando macros en una hoja de cálculo. La fase de postoptimización se realizó mediante una estrategia de Búsqueda Local que utilizó reglas de dominancia que, aun cuando sencillas, permitieron mejorar sustancialmente la tardanza total ponderada de las secuencias obtenidas en la fase constructiva del algoritmo.
AIEX, R.; BINATO, S. y RESENDE, M. Parallel GRASP with path-relinking for jb shop scheduling. Parallel Computing in Numerical Optimization, 2003, vol. 29, núm. 4, pp. 393-430.
AKTURK, M. y YILDIRIM, M. A new lower bounding scheme for the total weightes tardiness problem. Computers and Operations Research ,1998, vol. 25, núm. 4, pp. 265-278.
ÁLVAREZ-VALDÉS, R.; PARRENO, F. y TAMARIT, J. Reactive GRASP for the strip-packing problem. Computers & Operations Research, 2008, vol. 33, núm. 8, pp.1065-1083.
ÁLVAREZ-VALDÉS, R. et al. GRASP and path relinking for project scheduling under partially renewable resources. European Journal of Operational Research, 2008, vol. 189, núm. 3, pp. 1153-1170.
BAKER, K. y BERTRAND, J. A dynamic priority rule for scheduling against due-dates. Journal of Operations Management, 1982, vol. 3, núm. 1, pp. 37-42.
BEASLEY, J. OR-Library. 2001 [web en línea]. <http://people.brunel.ac.uk/~mastjjb/jeb/orlib/wtinfo.html>. [Consulta: 10-07-2007].
BILGE, U.; KURTULAN, M. y KIRAC, F. A tabu search algorithm for the single machine total weighted tardiness problem. European Journal of Operations Research, 2007, vol. 176, núm. 3, pp. 1423-1435.
CARROLL, D. Heuristic sequencing of single and multiple components. PhD Dissertation. Boston, MA: Massachusetts Institute of Technology, 1965.
CHEN, B.; POTTS, C. y WOEGINGER, G. A review of machine scheduling: Complexity, algorithms and approximability. En Handbook of combinatorial optimization. Boston: Kluwer Academic Publishers, 1998, pp. 21-169.
CHENG, T. et al. Single machine scheduling to minimize total weighted tardiness. European Journal of Operations Research, 2005, vol. 165, núm. 2, pp. 423-443.
CONGRAM, R.; POTTS, C. y VAN DE VELDE, S. An iterated dynasearch algorithm for the single machine total weighted tardiness scheduling problem. Informs Journal on Computing, 2002, vol. 14, núm. 1, pp. 52-67.
CONWAY, R.; MAXWELL, W. y MILLER, L. Theory of scheduling. Reading, MA: Addison-Wesley, 1967.
CORBERAN, A.; MARTI, R. y SANCHIS, J. A GRASP heuristic for the mixed Chinese postman problem. European Journal of Operational Research, 2002, vol. 142, núm. 1, pp. 70-80.
CRAUWELS, H.; POTTS, C. y VAN WASSENHOVE, L. Local search heuristics for single machine total weighted tardiness problem. Informs Journal on Computing, 1998, vol. 10, núm. 3, pp. 341-350.
DELORME, X.; GANDIBLEUX, X. y RODRÍGUEZ, J. GRASP for set packing problems. European Journal of Operational Research, 2004, vol. 153, núm. 3, pp. 564-580.
EMMONS, H. One machine sequencing to minimize certain functions of Job tardiness. Operations Research, 1969, vol. 17, núm. 4, pp. 701-715.
GRAHAM, R. et al. Optimisation and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 1979, vol. 5, pp. 287-326.
HERNÁNDEZ-PÉREZ, H.; RODRÍGUEZ-MARTÍN, I. y SALAZAR-GONZÁLEZ, J. A hybrid GRASP/VND heuristic for the one-commodity pickup-and-delivery traveling salesman problem. Computers & Operations Research, 2009, vol. 36, núm. 5, pp. 1639-1645.
LAWLER, E. A pseudopolynomial algortihm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics, 1977, vol. 1, pp. 331-342.
LENSTRA, J. y RINNOOY KAN, A. Computational complexity of discrete optimization problems. Annals of Discrete Mathematics, 1979, vol. 4, pp. 121-140.
LENSTRA, J.; RINNOOY KAN, A. y BRUCKER, P. Complexity of machine scheduling problems. Annals of Discrete mathematics I, 1977, vol. 7, pp. 343-362.
MATSUO, H.; SUH, C. y SULLIVAN, R. A controlled search simulated annealing method for the single machine weighted tardiness problem. Annals of Operations Research, 1989, vol. 21, pp. 85-108.
PANWALKAR, S.; SMITH, M. y KOULAMAS, C. A heuristic for the single machine tardiness problem. European Journal of Operations Research, 1993, vol. 70, pp. 304-310.
POTTS, C. y VAN WASSENHOVE, L. A branch and bound algorithm for the total weighted tardiness problem. Operations Research, 1985, vol. 33, núm. 2, pp. 363-377.
POTTS, C. y VAN WASSENHOVE, L. Single machine tardiness sequencing heuristics. IIE Transactions, 1991, vol. 23, núm. 4, pp. 346-354.
RACHAMADUGU, R. A note in the weighted tardiness problem. Operations Research, 1987, vol. 35 núm. 3, pp. 450-452.
RACHAMADUGU, R. y MORTON, T. Myopic heuristics for the single machine weighted total tardiness problem. Working Paper 30-82-83. Pittsburgh, PA: Carnegie Mellon University, 1982.
RESENDE, M. y RIBEIRO, C. Greedy ramdomized adaptative search procedure. En Handbook of metaheuristics. Boston, MA: Kluwer Academic Publishers, 2003.
Resende, M.; Marti , R.; Gallego, M. y Duarte , A. GRASP and path relinking for the max-min diversity problem. Computers & Operations Research, 2010, vol. 37, núm. 3, pp. 498-508.
RIBEIRO, C.; MARTINS, S., y ROSSETI, I. Metaheuristics for optimization problems in computer communications. Computer communication, 2007, vol. 30, núm. 4, pp. 656-669.
RINNOOY KAN, A.; LAGEWEG, B. y LENSTRA, J. Minimizing total costs in one-machine scheduling. Operations Research, 1975, vol. 23, núm. 5, pp. 908-927.
VEGA MEJÍA, C. A. y CABALLERO-VILLALOBOS, J. P. Uso combinado de GRASP y Path- Relinking en la programación de producción para minimizar la tardanza total ponderada en una máquina. Ingeniería y Universidad, 2010, vol. 14, núm. 1, pp. 79-96.
Una vez aceptado un trabajo para publicación la revista podrá disponer de él en toda su extensión, tanto directamente como a través de intermediarios, ya sea de forma impresa o electrónica, para su publicación ya sea en medio impreso o en medio electrónico, en formatos electrónicos de almacenamiento, en sitios de la Internet propios o de cualquier otro editor. Este uso tiene como fin divulgar el trabajo en la comunidad científica y académica nacional e internacional y no persigue fines de lucro. Para ello el autor o los autores le otorgan el permiso correspondiente a la revista para dicha divulgación mediante autorización escrita.
Todos los articulos aceptados para publicación son sometidos a corrección de estilo. Por tanto el autor /los autores autorizan desde ya los cambios sufridos por el artículo en la corrección de estilo.
El autor o los autores conservarán los derechos morales y patrimoniales del artículo.