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
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, dese...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Associação Brasileira de Engenharia de Produção (ABEPRO)
2012-12-01
|
| Series: | Production |
| Subjects: | |
| Online Access: | http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0103-65132012000400009 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849761650761007104 |
|---|---|
| author | Puca Huachi Vaz Penna Marcone Jamilson Freitas Souza Frederico Augusto de Cezar Almeida Gonçalves Luiz Satoru Ochi |
| author_facet | Puca Huachi Vaz Penna Marcone Jamilson Freitas Souza Frederico Augusto de Cezar Almeida Gonçalves Luiz Satoru Ochi |
| author_sort | Puca Huachi Vaz Penna |
| collection | DOAJ |
| description | 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.<br>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. |
| format | Article |
| id | doaj-art-ee4685eeda874a85a2bf5b8d144fce85 |
| institution | DOAJ |
| issn | 0103-6513 |
| language | English |
| publishDate | 2012-12-01 |
| publisher | Associação Brasileira de Engenharia de Produção (ABEPRO) |
| record_format | Article |
| series | Production |
| spelling | doaj-art-ee4685eeda874a85a2bf5b8d144fce852025-08-20T03:05:57ZengAssociação Brasileira de Engenharia de Produção (ABEPRO)Production0103-65132012-12-01224766777Uma 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-machinePuca Huachi Vaz PennaMarcone Jamilson Freitas SouzaFrederico Augusto de Cezar Almeida GonçalvesLuiz Satoru OchiEste 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.<br>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.http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0103-65132012000400009Sequenciamento em uma máquinaGRASPBusca tabuDescida em vizinhança variávelReconexão por caminhosSingle-MachineGRASPTabu searchVariable neighborhood descentPath relinking |
| spellingShingle | Puca Huachi Vaz Penna Marcone Jamilson Freitas Souza Frederico Augusto de Cezar Almeida Gonçalves Luiz Satoru Ochi 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 Production Sequenciamento em uma máquina GRASP Busca tabu Descida em vizinhança variável Reconexão por caminhos Single-Machine GRASP Tabu search Variable neighborhood descent Path relinking |
| title | 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 |
| title_full | 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 |
| title_fullStr | 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 |
| title_full_unstemmed | 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 |
| title_short | 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 |
| title_sort | uma heuristica hibrida para minimizar custos com antecipacao e atraso do sequenciamento da producao em uma maquina a hybrid heuristic algorithm for job scheduling problem on a single machine |
| topic | Sequenciamento em uma máquina GRASP Busca tabu Descida em vizinhança variável Reconexão por caminhos Single-Machine GRASP Tabu search Variable neighborhood descent Path relinking |
| url | http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0103-65132012000400009 |
| work_keys_str_mv | AT pucahuachivazpenna umaheuristicahibridaparaminimizarcustoscomantecipacaoeatrasodosequenciamentodaproducaoemumamaquinaahybridheuristicalgorithmforjobschedulingproblemonasinglemachine AT marconejamilsonfreitassouza umaheuristicahibridaparaminimizarcustoscomantecipacaoeatrasodosequenciamentodaproducaoemumamaquinaahybridheuristicalgorithmforjobschedulingproblemonasinglemachine AT fredericoaugustodecezaralmeidagoncalves umaheuristicahibridaparaminimizarcustoscomantecipacaoeatrasodosequenciamentodaproducaoemumamaquinaahybridheuristicalgorithmforjobschedulingproblemonasinglemachine AT luizsatoruochi umaheuristicahibridaparaminimizarcustoscomantecipacaoeatrasodosequenciamentodaproducaoemumamaquinaahybridheuristicalgorithmforjobschedulingproblemonasinglemachine |