Greedy randomized adaptive search procedure (GRASP): A valuable alternative for minimizing machine total weighted tardiness
Published
Mar 15, 2011
Almetrics
Dimensions
Google Scholar
Juan Pablo Caballero-Villalobos, MSc
Jorge Andrés Alvarado-Valencia, PhD
http://orcid.org/0000-0001-8331-2031
http://orcid.org/0000-0001-8331-2031
##plugins.themes.bootstrap3.article.details##
Abstract
A GRASP algorithm was implemented in a common spreadsheet for single machine scheduling total weighted tardiness problem, and was tested with OR-Library instances. Results were compared with optimum or best known schedules for each instance, yielding less than 1% of difference in 93% of the cases, which results in an excellent tradeoff among results quality, computational effort and implementation easiness. Local search was performed on the post-optimization phase, based on dominancy rules, which yielded even better results with little implementation effort.
Keywords
Production programming, metaheuristics, weighted tardiness problema, GRASPProgramación de la producción, metaheurísticas, tardanza ponderada, GRASP
References
ABDUL-RAZAQ, T.; POTTS, C. y VAN WASSENHOVE, L. A survey of algorithms for the single machine total weighted tardiness scheduling problem. Discrete Applied Mathematics, 1990, vol. 26, núms. 2-3, pp. 235-253.
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].. [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.
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].
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.
How to Cite
Caballero-Villalobos, J. P., & Alvarado-Valencia, J. A. (2011). Greedy randomized adaptive search procedure (GRASP): A valuable alternative for minimizing machine total weighted tardiness. Ingenieria Y Universidad, 14(2), 275. https://doi.org/10.11144/Javeriana.iyu14-2.gras
Section
Articles