Uma heurística híbrida para minimizar custos com antecipação e atraso do sequenciamento da produção em uma máquina
A hybrid heuristic algorithm for job scheduling problem on a single-machine
Penna, Puca Huachi V.; Souza, Marcone Jamilson F.; Gonçalves, Frederico Augusto de C. A.; Ochi, Luiz Satoru
http://dx.doi.org/10.1590/S0103-65132012005000020
Prod, vol.22, n4, p.766-777, 2012
Resumo
Este trabalho tem seu foco no problema de sequenciamento em uma máquina com penalidades por antecipação e atraso da produção. São considerados tempos de preparação da máquina dependentes da sequência de produção, bem como a existência de janelas de entrega distintas. Para resolução do problema, desenvolveu-se um algoritmo heurístico de 3 fases, nomeado GTSPR. A primeira fase baseada em GRASP é descida em vizinhança variável para a geração da solução inicial, a segunda fase baseada em busca tabu para refinamento da solução, e por fim a reconexão por caminhos como estratégia de pós-otimização, na terceira fase. Para cada sequência gerada pela heurística é utilizado um algoritmo de tempo polinomial para determinar a data ótima de início de processamento de cada tarefa. Os resultados computacionais mostraram que o algoritmo GTSPR supera outros algoritmos da literatura, tanto com relação à qualidade da solução final quanto em relação à variabilidade dessas soluções.
Palavras-chave
Sequenciamento em uma máquina. GRASP. Busca tabu. Descida em vizinhança variável. Reconexão por caminhos.
Abstract
This paper deals with the single-machine scheduling problem with earliness and tardiness penalties. Sequence dependent setup times and distinct due windows are considered. In order to solve this problem, a three-phase heuristic approach, the so-called GTSPR, was developed. The first phase is based on GRASP and Variable Neighborhood Descent to generate an initial solution; the second phase is based on Tabu Search for solution refining, finally, Path Relinking is used as a mechanism of post-optimization. For each job sequence generated by the heuristic, an optimal timing algorithm is used to determine the completion time for each job in the job sequence. Computational experiments carried out show that GTSPR outperforms the previous algorithms found in the related literature, regarding the quality of the final solution and the average gap.
Keywords
Single-Machine. GRASP. Tabu search. Variable neighborhood descent. Path relinking.
References
ALLAHVERDI, A.; GUPTA, J. N. D.; ALDOWAISAN, T. A review of scheduling research involving setup considerations. OMEGA, v. 27, p. 219-239, 1999. http://dx.doi.org/10.1016/S0305-0483(98)00042-5
ALLAHVERDI, A. et al. A survey of scheduling problems with setup times or costs. European Journal of Operational Research, v. 187, n. 3, p. 985-1032, 2008. http://dx.doi.org/10.1016/j.ejor.2006.06.060
BAKER, K. R.; SCUDDER, G. D. Sequencing with Earliness and Tardiness Penalties: A Review. Operations Research, v. 38, p. 22-36, 1990. http://dx.doi.org/10.1287/opre.38.1.22
BILGE, U.; KURTULAN, M.; KIRAC, F. A tabu search algorithm for the single machine total weighted tardiness problem. European Journal of Operational Research, v. 176, p. 1423-1435, 2007. http://dx.doi.org/10.1016/j.ejor.2005.10.030
COLEMAN, B. J. A simple model for optimizing the single machine early/tardy problem with sequence-dependent setups. Production and Operation Management, v. 1, n. 2, p. 225-228, 1992. http://dx.doi.org/10.1111/j.1937-5956.1992.tb00354.x
DONGARRA, J. J. Performance of various computers using standard linear equations software. Computer Science Department, University of Tennessee, 2010. Technical Report CS-89-85.
DU, J.; LEUNG, J. Y. T. Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research, v. 15, p. 483-495, 1990. http://dx.doi.org/10.1287/moor.15.3.483
FEO, T. A.; RESENDE, M. G. C. Greedy randomized adaptive search procedures. Journal of Global Optimization, v. 6, p. 109-133, 1995. http://dx.doi.org/10.1007/BF01096763
FRANÇA FILHO, M. F. GRASP e Busca Tabu aplicados a problemas de programação de tarefas em máquinas paralelas. 2007. Tese (Doutorado em Engenharia de Sistemas)-Universidade Estadual de Campinas, Campinas, 2007.
GLOVER, F. Future paths for Integer Programming and links to Artificial Intelligence. Computers and Operations Research, v. 5, p. 553-549, 1986.
GLOVER, F. Tabu search and adaptive memory programming - Advances, applications and challenges. In: BARR, R. S.; HELGASON, R. V.; KENNINGTON, J. L. (Eds.). Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research. Kluwer Academic Publishers, 1996. p. 1-75.
GLOVER, F.; KOCHENBERGER, G. Handbook of Metaheuristics. Kluwer Academic Publishers, 2003.
GOMES JUNIOR, A. C. Problema de sequenciamento de uma máquina com penalidades por antecipação e atraso da produção: modelagem e resolução. 2007. Dissertação (Mestrado em Engenharia de Produção)-Universidade Federal de Minas Gerais, Belo Horizonte, 2007.
GOMES JUNIOR, A. C.; CARVALHO, C. R. V.; MUNHOZ, P. L. A.; SOUZA, M. J. F. Um método heurístico híbrido para a resolução do problema de sequenciamento em uma máquina com penalidades por antecipação e atraso da produção. In: SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL - SBPO, 39.; 2007, Fortaleza. Anais... Fortaleza, 2007. p. 1649-1660.
GORDON, V.; PROTH, J.; CHU, C. A survey of the state-of-the-art of common due date assignment and scheduling research. European Journal of Operational Research, v. 139, p. 1-25, 2002. http://dx.doi.org/10.1016/S0377-2217(01)00181-3
GUPTA, S. R.; SMITH, J. S. Algorithms for single machine total tardiness scheduling with sequence dependent setups, European Journal of Operational Research, v. 175, p. 722-739, 2006. http://dx.doi.org/10.1016/j.ejor.2005.05.018
HALLAH, R. M. Minimizing total earliness and tardiness on a single machine using a hybrid heuristic, Computers and Operations Research, v. 34, p. 3126-3142, 2007. http://dx.doi.org/10.1016/j.cor.2005.11.021
JAMES, R. J. W. Using tabu search to solve the common due date early/tardy machine scheduling problem. Computers and Operations Research, v. 24, n. 3, p. 199-208, 1997. http://dx.doi.org/10.1016/S0305-0548(96)00052-4
LEE, C. Y.; CHOI, J. Y. A Genetic Algorithm for Job Sequencing Problems with Distinct Due Dates and General Early-Tardy Penalty Weights. Computers and Operations Research, v. 22, p. 857-869, 1995. http://dx.doi.org/10.1016/0305-0548(94)00073-H
LIAW, C. F. A Branch-and-Bound Algorithm for the Single Machine Earliness and Tardiness Scheduling Problem. Computers and Operations Research, v. 26, p. 679-693, 1999. http://dx.doi.org/10.1016/S0305-0548(98)00081-1
MLADENOVIC, N.; HANSEN, P. Variable Neighborhood Search, Computers and Operations Research, v. 24, p. 1097-1100, 1997. http://dx.doi.org/10.1016/S0305-0548(97)00031-2
PANWALKAR, S. S.; DUDEK, R. A.; SMITH, M. L. Sequencing research and the industrial scheduling problem. In: ELMAGHRABY, S. E. (Eds.). Symposium on the Theory of Scheduling and its Applications. Springer: Berlin, 1973. p. 29-38.
PRAIS, M.; RIBEIRO, C. C. An application to a matrix decomposition problem in tdma traffic assignment. INFORMS - Journal on Computing, v. 12, p. 164-176, 2000. http://dx.doi.org/10.1287/ijoc.12.3.164.12639
RABADI, G.; MOLLAGHASEMI, M.; ANAGNOSTOPOULOS, G. C. A Branch-and-Bound Algorithm for the Early/Tardy Machine Scheduling Problem with a Common due-date and Sequence-Dependent Setup Time. Computers and Operations Research, v. 31, p. 1727-1751, 2004. http://dx.doi.org/10.1016/S0305-0548(03)00117-5
RIBEIRO, F. F.; DE SOUZA, S. R.; SOUZA, M. J. F. An adaptive genetic algorithm for solving the single machine scheduling problem with earliness and tardiness penalties. In: IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN AND CYBERNETICS - IEE SMC, 2009, San Antonio. Proceedings... San Antonio, 2009. p. 698-703.
WAN, G.; YEN, B. P. C. Tabu Search for Single Machine Scheduling with Distinct Due Windows and Weighted Earliness/Tardiness Penalties. European Journal of Operational Research, v. 142, p. 271-281, 2002. http://dx.doi.org/10.1016/S0377-2217(01)00302-2
ALLAHVERDI, A. et al. A survey of scheduling problems with setup times or costs. European Journal of Operational Research, v. 187, n. 3, p. 985-1032, 2008. http://dx.doi.org/10.1016/j.ejor.2006.06.060
BAKER, K. R.; SCUDDER, G. D. Sequencing with Earliness and Tardiness Penalties: A Review. Operations Research, v. 38, p. 22-36, 1990. http://dx.doi.org/10.1287/opre.38.1.22
BILGE, U.; KURTULAN, M.; KIRAC, F. A tabu search algorithm for the single machine total weighted tardiness problem. European Journal of Operational Research, v. 176, p. 1423-1435, 2007. http://dx.doi.org/10.1016/j.ejor.2005.10.030
COLEMAN, B. J. A simple model for optimizing the single machine early/tardy problem with sequence-dependent setups. Production and Operation Management, v. 1, n. 2, p. 225-228, 1992. http://dx.doi.org/10.1111/j.1937-5956.1992.tb00354.x
DONGARRA, J. J. Performance of various computers using standard linear equations software. Computer Science Department, University of Tennessee, 2010. Technical Report CS-89-85.
DU, J.; LEUNG, J. Y. T. Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research, v. 15, p. 483-495, 1990. http://dx.doi.org/10.1287/moor.15.3.483
FEO, T. A.; RESENDE, M. G. C. Greedy randomized adaptive search procedures. Journal of Global Optimization, v. 6, p. 109-133, 1995. http://dx.doi.org/10.1007/BF01096763
FRANÇA FILHO, M. F. GRASP e Busca Tabu aplicados a problemas de programação de tarefas em máquinas paralelas. 2007. Tese (Doutorado em Engenharia de Sistemas)-Universidade Estadual de Campinas, Campinas, 2007.
GLOVER, F. Future paths for Integer Programming and links to Artificial Intelligence. Computers and Operations Research, v. 5, p. 553-549, 1986.
GLOVER, F. Tabu search and adaptive memory programming - Advances, applications and challenges. In: BARR, R. S.; HELGASON, R. V.; KENNINGTON, J. L. (Eds.). Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research. Kluwer Academic Publishers, 1996. p. 1-75.
GLOVER, F.; KOCHENBERGER, G. Handbook of Metaheuristics. Kluwer Academic Publishers, 2003.
GOMES JUNIOR, A. C. Problema de sequenciamento de uma máquina com penalidades por antecipação e atraso da produção: modelagem e resolução. 2007. Dissertação (Mestrado em Engenharia de Produção)-Universidade Federal de Minas Gerais, Belo Horizonte, 2007.
GOMES JUNIOR, A. C.; CARVALHO, C. R. V.; MUNHOZ, P. L. A.; SOUZA, M. J. F. Um método heurístico híbrido para a resolução do problema de sequenciamento em uma máquina com penalidades por antecipação e atraso da produção. In: SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL - SBPO, 39.; 2007, Fortaleza. Anais... Fortaleza, 2007. p. 1649-1660.
GORDON, V.; PROTH, J.; CHU, C. A survey of the state-of-the-art of common due date assignment and scheduling research. European Journal of Operational Research, v. 139, p. 1-25, 2002. http://dx.doi.org/10.1016/S0377-2217(01)00181-3
GUPTA, S. R.; SMITH, J. S. Algorithms for single machine total tardiness scheduling with sequence dependent setups, European Journal of Operational Research, v. 175, p. 722-739, 2006. http://dx.doi.org/10.1016/j.ejor.2005.05.018
HALLAH, R. M. Minimizing total earliness and tardiness on a single machine using a hybrid heuristic, Computers and Operations Research, v. 34, p. 3126-3142, 2007. http://dx.doi.org/10.1016/j.cor.2005.11.021
JAMES, R. J. W. Using tabu search to solve the common due date early/tardy machine scheduling problem. Computers and Operations Research, v. 24, n. 3, p. 199-208, 1997. http://dx.doi.org/10.1016/S0305-0548(96)00052-4
LEE, C. Y.; CHOI, J. Y. A Genetic Algorithm for Job Sequencing Problems with Distinct Due Dates and General Early-Tardy Penalty Weights. Computers and Operations Research, v. 22, p. 857-869, 1995. http://dx.doi.org/10.1016/0305-0548(94)00073-H
LIAW, C. F. A Branch-and-Bound Algorithm for the Single Machine Earliness and Tardiness Scheduling Problem. Computers and Operations Research, v. 26, p. 679-693, 1999. http://dx.doi.org/10.1016/S0305-0548(98)00081-1
MLADENOVIC, N.; HANSEN, P. Variable Neighborhood Search, Computers and Operations Research, v. 24, p. 1097-1100, 1997. http://dx.doi.org/10.1016/S0305-0548(97)00031-2
PANWALKAR, S. S.; DUDEK, R. A.; SMITH, M. L. Sequencing research and the industrial scheduling problem. In: ELMAGHRABY, S. E. (Eds.). Symposium on the Theory of Scheduling and its Applications. Springer: Berlin, 1973. p. 29-38.
PRAIS, M.; RIBEIRO, C. C. An application to a matrix decomposition problem in tdma traffic assignment. INFORMS - Journal on Computing, v. 12, p. 164-176, 2000. http://dx.doi.org/10.1287/ijoc.12.3.164.12639
RABADI, G.; MOLLAGHASEMI, M.; ANAGNOSTOPOULOS, G. C. A Branch-and-Bound Algorithm for the Early/Tardy Machine Scheduling Problem with a Common due-date and Sequence-Dependent Setup Time. Computers and Operations Research, v. 31, p. 1727-1751, 2004. http://dx.doi.org/10.1016/S0305-0548(03)00117-5
RIBEIRO, F. F.; DE SOUZA, S. R.; SOUZA, M. J. F. An adaptive genetic algorithm for solving the single machine scheduling problem with earliness and tardiness penalties. In: IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN AND CYBERNETICS - IEE SMC, 2009, San Antonio. Proceedings... San Antonio, 2009. p. 698-703.
WAN, G.; YEN, B. P. C. Tabu Search for Single Machine Scheduling with Distinct Due Windows and Weighted Earliness/Tardiness Penalties. European Journal of Operational Research, v. 142, p. 271-281, 2002. http://dx.doi.org/10.1016/S0377-2217(01)00302-2
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email