Evaluación de funciones de utilidad de GRASP en la programación de producción para minimizar la tardanza total ponderada en una máquina

Evaluation Of Utility Functions For Minimization Of Total Weighted Tardiness In Machine Scheduling Using Grasp

  • Angela Maria Nino Navarrete Pontificia Universidad Javeriana
  • Juan Pablo Caballero Villalobos Pontificia Universidad Javeriana
Palabras clave: Función de utilidad, GRASP, programación de la producción, tardanza total ponderada. (es_ES)

Resumen (es_ES)

Este artículo aborda la minimización de la tardanza total ponderada en un entorno de producción (1|| wj Tj ) que es conocido en complejidad como de tipo NP-hard. El enfoque de solución propuesto utiliza la metaheurística Greedy Randomized Adaptive Search Procedure (GRASP), la cual es reconocida por la correlación existente entre la calidad de las soluciones y la capacidad discriminante de la función de utilidad empleada en su fase constructiva. Este trabajo propone y analiza tres diferentes funciones de utilidad para este problema en particular. El desempeño de estas funciones se evaluó mediante un estudio estadístico que evidenció diferencias significativas en los valores medios de tardanza total ponderada, explicadas por el factor función de utilidad. La fase experimental se desarrolló usando instancias de la librería OR-LIBRARY y permitió obtener soluciones competitivas en calidad con respecto a los mejores valores conocidos para las instancias de este problema. Este trabajo ilustra la potencialidad de uso de métodos GRASP implementados en una hoja de cálculo normal para hallar soluciones a problemas de programación de la producción.

Resumen (en_US)

This paper considers the total weighted tardiness minimization in a single machineenvironment (1|| wj Tj ) a scheduling problem which has been proved to be NP-Hard. The solution approach uses the Greedy Randomized Adaptive Search Procedure (GRASP) meta-heuristic known for the quality of the solutions it can generate and the selective ability of its utility function during the construction phase. This work proposes and analyses three different utility functions for the problem in question. A statistical study showed significant differences between the mean values obtained from the proposed utility functions. The computational experiments were carried out using problems instances found in the OR-LIBRARY, and the outcome of these experiments were competitive solutions compared to the best known values of the instances involved. This work also shows the ease of developing GRASP methods for solving scheduling problems in a simple spreadsheet software such as MS Excel.

Descargas

La descarga de datos todavía no está disponible.

Referencias

K. Baker, J. Hayya. "Priority dispatching with operation due dates". Journal of Operations Mangement 2, 167­175. 1992.

U. Bilge, M. Kurtulan, F. Kiraç. "A tabu search algorithm for the single machine total weighted tardiness problem". European Journal of Operational Research, 176, 1423­35. 2007.

W. Bozejko, J. Grabowski, M. Wodecki. "Block Approach Tabu Search algorithm for single machine total weighted tardiness problem". Computers and Industrial Engineering 50, 1­14. 2006.

R. Britto, G. Mejía, J. P. Caballero-Villalobos. "Programación de la producción en sistemas de manufactura tipo taller con el algoritmo combinado cuello de botella móvil y búsqueda Tabú". Ingeniería y Universidad, volumen 11, No 2, 203 ­ 224. 2007.

T. C. E. Cheng, C. T. Ng, J. J. Yuan, Z. H. Liu. "Single machine scheduling to minimize total weighted tardiness". European Journal of Operational Research, 165, 423­443. 2005.

F. Chou. "An experienced learning genetic algorithm to solve the single machine total weighted tardiness scheduling problem". Expert Systems with Applications, 36, 3857­3865. 2009

R. K. Congram, C.N. Potts, S. L. Van de Velde. "An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem". Informs Journal on Computing, 14(1), 52­67. 2002.

A. Croes. "A method for solving traveling-salesman problems". Operations Research, 5, 791-812. 1958.

L. M. A. Drummond, L. S. Vianna, M. B. Silva, L. S. Ochi. "Distribution parallel metaheuristics based on GRASP and VNS for solving the traveling purchaser problem". In Proceedings of the 9th International Conference on Parallel and Distributed System, pp. 257­263. 2002.

M. L. Fisher. "A dual algorithm for the one machine scheduling problem". Mathematical Programming, 11, 229­252. 1976.

F. Glover, G. Kochenberger. "Handbook of Metaheuristics. Kluwer Academic Publishers". 2003.

R. L. Graham, E. L. Lawler, J. K. Lenstra, A.H.G. Rinnooy Kan. "Optimization and approximation in deterministic sequencing and scheduling: A survey". Annals of Discrete Mathematics, 5, 287-326. 1979.

A. Grosso, C. Della, R. Tadei. "An enhanced dynasearch neighborhood for single-machine total weighted tardiness scheduling problem". Operations Research Letters, 32, 68­72. 2004.

O. Holthaus, C. Rajendran. "A fast ant-colony algorithm for single-machine scheduling to minimize the sum of weighted tardiness of jobs". Journal of the Operational Research Society, 56, 947­53. 2005.

F. Jin, S. Song, C. Wua. "A simulated annealing algorithm for single machine scheduling problems with family setups". Computers and Operations Research, 36, 2133 ­ 2138. 2009.

E.L. Lawler. "Efficient implementation of dynamic programming algorithms for sequencing problems". Technical report, BW-106. Amsterdam: Centre for Mathematics and Computer Science. 1979.

F. Jolai, M. Rabbani, S. Amalnick, A. Dabaghi, M. Dehghan, Y. Parast. "Genetic algorithm for bi-criteria single machine scheduling problem of minimizing maximum earliness and number of tardy jobs". Applied Mathematics and Computation, 194, 552­560. 2007.

C. Liao, C. Cheng. "A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date". Computers and Industrial Engineering 52, 404-413. 2007.

C. Liao, H. Juan. "An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups". Computers and Operations Research 34. 2007.

T. E. Morton, R. M. Rachamadugu, A. Vepsalainen. "Accurate myopic heuristic for tardiness scheduling". Working paper No. 36-83-84. Pitsburgh: Carnegie-Mellon University. 1984.

M. Pinedo. "Scheduling Theory, Algorithms and Systems". Third edition. New Jersey. Prentice Hall. 2008.

A. H. G. Rinnooy Kan, B. J. Lageweg, J. K. Lenstra. "Minimizing total costs in one-machine scheduling". Operations Research, 25, 908­927. 1975.

R. Rios-Mercado, J. Bard. "Heuristics for the flow line problem with setup costs". European Journal of Operational Research 110, 76­98. 1998.

T. Sen, J. M. Sulek, P. Dileepan. "Static scheduling research to minimize weighted and unweighted tardiness: a state-of-the-art survey". International Journal of Production Economics, 83, 1­ 12. 2003.

M. Tasgetiren, Q. Pan, Y. Liang. "A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times". Computers and Operations Research, 36, 1900 ­ 1915. 2009.

C.A. Vega-Mejía, J.P. Caballero-Villalobos. "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, volumen 14, número 1, 79 ­ 96. 2010.

C. Voudouris, Tsang. "Guided Local Search. Handbook of Metaheuristics". Capítulo 7. Kluwer Academic Publishers. 2003.

G. Wan, B.P.C. Yen, "Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs". European Journal of Operational Research 195, 89­97. 2002.

X. Wang, L. Tang. "A population based variable neighborhood search for the single machine total weighted tardiness problem". Computers and Operations Research 36, 2105-2110. 2009.

Cómo citar
Nino Navarrete, A. M., & Caballero Villalobos, J. P. (2008). Evaluación de funciones de utilidad de GRASP en la programación de producción para minimizar la tardanza total ponderada en una máquina. Ingeniería, 14(2), 51-58. https://doi.org/10.14483/23448393.2379
Publicado: 2008-11-30
Sección
Ciencia, investigación, academia y desarrollo

Artículos más leídos del mismo autor/a