|
|
|
|
 |
|
|
« Revista Investigação Operacional
|
| Artigo |
|
|
|
|
|
Branch-and-Bound para o problema de Jpb-Shop: Novas regras de ramificação,
Volume nº 18
|
|
Helena Ramalhinho Lourenço
Centro de Investigação Operacional, DEIO, Faculdade de Ciências da Universidade de Lisboa
1700 Lisboa
Portugal
Abstract: The job-shop scheduling problem consists in scheduling a set of jobs on a set of machines, in order to minimize the makespan. In this paper, we develop and implement a variation of a branch-and-bound method for solving the job-shop scheduling problem, presented by Brucker, Jurisch and Sievers [1994]. The modifications refer to the lower bound method and to the branching scheme. The lower bound is obtained by solving an one-machine scheduling problem with lags. A relaxation of this problem can be solved in polynomial time by the early-late algorithm, developed by Lourenÿo [1993]. We studied some branching rules that can be adapted to this new lower bound method, in away that the sucessive partition of feasible solutions set gives good lags. We present some computational results in order to compare the different versions of the branch-and-bound method.
Resumo: O problema de job-shop consiste num conjunto de tarefas a ser processadas por um conjunto de máquinas, com objectivo de encontrar uma sequência de tarefas em cada máquina que minimize a data global de conclusão. Neste trabalho, desenvolve-se e implementa-se uma variante do método de branch-and-bound para o problema de job-shop proposto por Brucker, Jurisch e Sievers [1994]. As alterações aqui apresentadas dizem respeito ao método de limite inferior e à regra de ramificação. O limite inferior é obtido com base na resolução do problema de sequenciamento numa única máquina com intervalos de tempo. Uma relaxação deste problema pode ser resolvida em tempo polinomial utilizando o algoritmo early-late, desenvolvido por Lourenço [1993]. Construímos, então, regras de ramificação que se adaptam a este novo método de limite inferior, tendo em conta que a partição sucessiva do conjunto de soluções admissíveis deve ser feita de modo a criar bons intervalos. Apresentamos diversos resultados computacionais, com o objectivo de comparar as diferentes versões do método de branch-and-bound.
Keywords: Job-shop, branch-and-bound, branching scheme.
|
|
|
|
|
|
|
|
