Vol. 14 No. 1 (2010), Articles
Vol. 14 No. 1 (2010)

Combined Use of GRASP and Path-Relinking during Production Scheduling in order to Minimize Total Weighted Tardiness in a Machine

Articles
Published 2010-10-27
Carlos Alberto Vega-Mejía, MSc
Pontificia Universidad Javeriana
Juan Pablo Caballero-Villalobos, MSc
Pontificia Universidad Javeriana
PDF (Spanish)

Keywords

Production scheduling
GRASP (computer file)
times and movements

How to Cite

Combined Use of GRASP and Path-Relinking during Production Scheduling in order to Minimize Total Weighted Tardiness in a Machine. (2010). Ingenieria Y Universidad, 14(1). https://doi.org/10.11144/Javeriana.iyu14-1.ucgp
ACM ACS APA ABNT Chicago Harvard IEEE MLA Turabian Vancouver AMA

Download Citation

Endnote/Zotero/Mendeley (RIS) BibTeX
Almetrics
 
Dimensions
 

Google Scholar
 
Search GoogleScholar

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.

PDF (Spanish)

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.

This journal is registered under a Creative Commons Attribution 4.0 International Public License. Thus, this work may be reproduced, distributed, and publicly shared in digital format, as long as the names of the authors and Pontificia Universidad Javeriana are acknowledged. Others are allowed to quote, adapt, transform, auto-archive, republish, and create based on this material, for any purpose (even commercial ones), provided the authorship is duly acknowledged, a link to the original work is provided, and it is specified if changes have been made. Pontificia Universidad Javeriana does not hold the rights of published works and the authors are solely responsible for the contents of their works; they keep the moral, intellectual, privacy, and publicity rights.

Approving the intervention of the work (review, copy-editing, translation, layout) and the following outreach, are granted through an use license and not through an assignment of rights. This means the journal and Pontificia Universidad Javeriana cannot be held responsible for any ethical malpractice by the authors. As a consequence of the protection granted by the use license, the journal is not required to publish recantations or modify information already published, unless the errata stems from the editorial management process. Publishing contents in this journal does not generate royalties for contributors.