Combined Use of GRASP and Path-Relinking during Production Scheduling in order to Minimize Total Weighted Tardiness in a Machine
##plugins.themes.bootstrap3.article.details##
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.
Production scheduling, GRASP (computer file), times and movementsProgramación de la producción, GRASP (programa para computador), tiempos y movimientos
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.