Published Oct 27, 2010



PLUMX
Almetrics
 
Dimensions
 

Google Scholar
 
Search GoogleScholar
Downloads


Carlos Alberto Vega-Mejía, MSc

Juan Pablo Caballero-Villalobos, MSc

##plugins.themes.bootstrap3.article.details##

Abstract

This paper shows the results of integrating two meta-heuristic techniques, GRASP and Path-Relinking, which have not been widely used to solve production-scheduling problems despite of their proved efficiency. These techniques were used to solve the problem of minimizing total weighted tardiness problem in a machine, 1 || Σ WjTj, and good results in short time were obtained. Experiment outcomes show that the use of Path-Relinking as a final step for GRASP can result in qualitysequence improvements. In order to use GRASP in the solution to this problem, a dynamic utility function for the jobs to process, bearing in mind its descriptive parameters, is proposed. Additionally, this work offers a clear implementation proposal for ventures of different sizes, so they are able to overcome this problem by using MS Excel, instead of specialized scheduling software.

Keywords

Programación de la producción, GRASP (programa para computador), tiempos y movimientosProduction scheduling, GRASP (computer file), times and movements

References
BOZEJKO, W.; GRABOWSKI, J. y WODECKI, M. Block approach–tabu search algorithm for single machine total weighted tardiness problem. Computers & Industrial Engineering, 2006, vol. 50, núms. 1-2, pp. 1-14.
BRUCKER, P. Scheduling algorithms. 5th ed. New York: Springer, 2007.
CONGRAM, R. K.; POTTS, C. N. y VAN DE VELDE, S. L. 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.
FELDMANN, M. y BISKUP, D. Single-machine scheduling for minimizing earliness and tardiness penalties by meta-heuristic approaches. Computers and Industrial Engineering, 2003, vol. 44, núm. 2, pp. 307-323.
FLESZAR, K.; OSMAN, I. H. e HINDI, K. S. A variable neighborhood search algorithm for the open vehicle routing problem. European Journal of Operational Research, 2008, vol. 195, núm. 3, pp. 803-809.
GLOVER, F. y KOCHENBERGER, G. A. Handbook of metaheuristics. Dordrecht: Kluwer Academic Publishers, 2003.
GRAHAM, R. L. et al. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 1979, vol. 5, pp. 287-326.
HANSEN, P. y MLADENOVIC, N. Variable neighborhood search: principles and applications. European Journal of Operational Research, 2001, vol. 130, núm. 3, pp. 449-467.
HANSEN, P.; MLADENOVIC, N. y MORENO PÉREZ, J. A. Variable neighborhood search. European Journal of Operational Research, 2008, vol. 191, núm. 3, pp. 593-595.
HINO, C. M.; RONCONI, D. P. y MENDES A. B. Minimizing earliness and tardiness penalties in a single-machine problem with a common due date. European Journal of Operational Research, 2005, vol. 160, núm. 1, pp. 190-201.
LIAO, C.-J. y CHENG, C.-C. A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date. Computers & Industrial Engineering, 2007, vol. 52, núm. 4, pp. 404-413.
MLADENOVIC, N. y HANSEN, P. Variable neighborhood search. Computers & Operations Research, 1997, vol. 24, núm. 11, pp. 1097-1100.
PINEDO, M. L. Scheduling, theory, algorithms, and systems. 3rd ed. New York: Springer, 2008.
SEN, T.; SULEK, J. M. y DILEEPAN, P. Static scheduling research to minimize weighted and unweighted tardiness: A state-of-the-art survey. International Journal of Production Economics, 2003, vol. 83, núm. 1, pp. 1-12.
WAN, G. y YEN, B. P. C. Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs. European Journal of Operational Research, 2009, vol. 195, núm. 1, pp. 89-97.
WANG, X. y TANG, L. A population–based variable neighborhood search for the single machine total weighted tardiness problem. Computers & Operations Research, 2009, vol, 36, núm. 6, pp. 2105-2110.
How to Cite
Vega-Mejía, C. A., & Caballero-Villalobos, J. P. (2010). Combined Use of GRASP and Path-Relinking during Production Scheduling in order to Minimize Total Weighted Tardiness in a Machine. Ingenieria Y Universidad, 14(1). https://doi.org/10.11144/Javeriana.iyu14-1.ucgp
Section
Articles