ads:
UNIVERSIDADE FEDERAL FLUMINENSE
CENTRO TECNOLÓGICO
CURSO DE MESTRADO EM ENGENHARIA DE PRODUÇÃO
GERSON GARCIA DOS SANTOS
EXPERIMENTOS COM FORMULAÇÕES DE PROGRAMAÇÃO INTEIRA PARA O
PROBLEMA DO PERMUTATION FLOWSHOP
NITERÓI
2008
id137937 pdfMachine by Broadgun Software - a great PDF writer! - a great PDF creator! - http://www.pdfmachine.com http://www.broadgun.com
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
GERSON GARCIA DOS SANTOS
EXPERIMENTOS COM FORMULAÇÕES DE PROGRAMAÇÃO INTEIRA PARA
O PROBLEMA DO PERMUTATION FLOWSHOP
Dissertação apresentada ao Curso de Mestrado em
Engenharia de Produção da Universidade Federal
Fluminense, como requisito parcial para obtenção
do Grau de Mestre. Área de Concentração:
Sistemas, Apoio à Decisão e Logística.
Orientador: Prof. EDUARDO UCHOA BARBOZA, DSc.
Niterói
2008
ads:
GERSON GARCIA DOS SANTOS
EXPERIMENTOS COM FORMULAÇÕES DE PROGRAMAÇÃO INTEIRA PARA
O PROBLEMA DO PERMUTATION FLOWSHOP
Dissertação apresentada ao Curso de Mestrado em
Engenharia de Produção da Universidade Federal
Fluminense, como requisito parcial para obtenção
do Grau de Mestre. Área de Concentração:
Sistemas, Apoio à Decisão e Logística.
Aprovada em março de 2008.
BANCA EXAMINADORA
____________________________________________________________
Prof. Eduardo Uchoa Barboza, DSc. – Orientador
Universidade Federal Fluminense
______________________________________________________________
Prof. Artur Alves Pessoa, DSc.
Universidade Federal Fluminense
_____________________________________________________________
Prof. Marcus Vinicius Soledade Poggi de Aragão, PhD.
Pontifícia Universidade Católica do Rio de Janeiro
Niter
ói
2008
AGRADECIMENTOS
A Deus, que permitiu que eu tivesse a oportunidade de estudar, e aos guias
espirituais que me ajudaram nas horas mais difíceis.
Ao professor Eduardo Uchoa Barboza por ter acreditado em mim e pela efetiva
orientação nesse trabalho.
Ao professor Artur Alves Pessoa pelas boas idéias que foram estudadas e
aplicadas.
À minha mãe, Caroline e Michely, pela paciência e por terem suportado os
períodos de ausência necessários durante o mestrado.
RESUMO
O problema do Permutation Flowshop é um dos mais clássicos na área de
escalonamento, tendo sido intensamente pesquisado desde anos 50. Este trabalho traz duas
contribuições para o estudo desse problema no contexto de programação inteira. A primeira é
uma avaliação experimental do efeito de algumas regras de branch propostas (baseadas em
uma regra anteriormente proposta por Potts nos anos 80) no desempenho de um algoritmo de
branch-and-bound sobre a clássica formulação de Wilson. A segunda é a avaliação de uma
nova formulação que garantidamente fornece limites inferiores melhores que a formulação de
Wilson.
Palavras-chave: Programação Inteira. Permutation flowshop. Escalonamento. Regra de
Branch. Formulações.
ABSTRACT
The Permutation Flowshop problem is one of the most well-known problems in the
field of scheduling and has been intensely explored since the 1950s. The present work brings
two contributions for the study of this problem in the context of integer programming. The
first is an experimental evaluation of the effect of some branch rules (inspired in Potts’ rule
proposed in the 1980s) in the performance of a branch-and-bound algorithm over the classic
Wilson’s formulation. The second contribution is the analysis of a new formulation whose
linear relaxation yields better lower bounds than the Wilson’s formulation does.
Keywords: Integer Programming. Permutation flowshop. Scheduling. Branch rule.
Formulations.
SUMÁRIO
1 INTRODUÇÃO, p. 8
1.1 ENUNCIADO DO PROBLEMA, p. 8
1.2 PROGRAMAÇÃO INTEIRA, p. 14
1.3 OBJETIVOS DO TRABALHO, p. 19
2 RESULTADOS BÁSICOS SOBRE O PROBLEMA DO FLOWSHOP, p. 20
3 REVISÃO BIBLIOGRÁFICA, p. 30
3.1 HEURÍSTICAS, p. 30
3.2 MÉTODOS EXATOS, p. 30
4 ESTUDO DE REGRAS DE BRANCH PARA A FORMULAÇÃO DE WILSON, p. 32
4.1 FORMULAÇÃO DE WILSON, p. 32
4.2 BRANCH SOBRE VARIÁVEIS ISOLADAS, p. 34
4.3 BRANCH SOBRE CONJUNTOS DE VARIÁVEIS (SOS), p. 45
5 FORMULAÇÃO DE FLUXOS, p. 54
6 CONCLUSÃO, p. 63
7 REFERÊNCIAS, p. 65
1 INTRODUÇÃO
1.1 ENUNCIADO DO PROBLEMA
Na atividade de planejamento da produção em indústrias e nas empresas prestadoras
de serviços várias vezes é necessário resolver problemas de escalonamento (scheduling).
Tipicamente temos situações em que algumas tarefas têm que ser executadas e para tal
dispomos de um número limitado de agentes, que podem ser máquinas ou pessoas.
Por exemplo, uma linha de montagem de uma indústria automobilística é composta de
máquinas que realizam determinadas funções em seqüência: montagem do chassi, soldagem,
pintura, etc. Nesse caso, uma tarefa poderia ser a montagem de um automóvel específico, que
precisa passar por todas as máquinas e sempre em uma seqüência pré-determinada (a
soldagem sempre precisa ser feita antes da pintura). A determinação da ordem em que os
automóveis devem passar pela linha de montagem é um problema de escalonamento.
Um outro exemplo seria o de uma agência bancária, em que, em vez de máquinas
temos funcionários trabalhando em suas mesas. As tarefas neste caso são os clientes que
chegam e que devem ser atendidos. Se um cliente em particular estiver interessado em
adquirir um seguro residencial e também um plano de previdência ele deverá ser atendido
pelos funcionários especializados em cada um desses produtos, em qualquer ordem, mas não
ao mesmo tempo.
Portanto, as características de cada indústria é que definirão se o processamento das
tarefas deverá ser feito em paralelo ou em seqüência, com uma ordem pré-determinada ou
não. Um outro ponto a ser considerado é qual indicador se quer melhorar para obter mais
eficiência. No caso do banco este indicador poderia ser o tempo máximo que um cliente
espera na fila antes de ser atendido. No caso da indústria automobilística a empresa poderia
9
estar interessada em reduzir ao máximo o tempo total necessário para um lote de automóveis
ficar pronto.
Existem duas abordagens principais para o tratamento de problemas de
escalonamento: a estocástica e a determinística. Quando se considera o problema de
escalonamento como um problema determinístico, os tempos de processamento das tarefas
nas máquinas são considerados como previamente conhecidos; nos problemas estocásticos, os
tempos de processamento das tarefas nas máquinas são variáveis aleatórias. No presente
trabalho utilizaremos somente a abordagem determinística.
Seguindo a convenção encontrada na literatura, os agentes que executam as tarefas
serão sempre referidos de forma abstrata como “máquinas”, mesmo quando eles são pessoas
ou outras entidades (PINEDO, 2002). É comum utilizarmos os diagramas de Gantt para
representar o escalonamento de execução de tarefas em máquinas. Nesse tipo de diagrama,
cada tarefa é representada por uma barra horizontal, cujo comprimento é proporcional à
duração da tarefa. A duração de uma tarefa pode ser medida em qualquer unidade de tempo.
Na figura abaixo vemos um diagrama de Gantt para um escalonamento de quatro tarefas em
um ambiente de apenas uma máquina.
Figura 1: Diagrama de Gantt representando um possível escalonamento de quatro tarefas em uma máquina.
Na figura acima, a tarefa 1 inicia seu processamento na máquina no tempo 0 (zero) e
termina no tempo 4. Imediatamente depois a máquina começa a processar a tarefa 2 e
continua o processamento dessa tarefa até o tempo 7. Depois disso, a máquina fica uma
unidade de tempo ociosa. Esse tempo ocioso é representado pelo intervalo (gap) entre o fim
da tarefa 2 e o início da tarefa 3. Após o término do processamento da tarefa 3 existe outro
período de ociosidade, de 3 unidades de tempo. Depois desse período, a tarefa 4 inicia o seu
processamento até o tempo 19, quando a máquina termina o processamento das tarefas.
10
Devido à grande variedade de problemas de escalonamento que são estudados, foi
proposta (GRAHAM et al., 1979 e LAGEWEG et al., 1981) uma nomenclatura para esses
problemas que utiliza a seguinte notação:
||
Onde:
: Define o ambiente de máquinas, por exemplo, o número “1” indica uma única
máquina, a letra “P” indica um número indeterminado de máquinas idênticas executando em
paralelo, etc.
: política de escalonamento, por exemplo, a palavra “no-wait” indica que nenhuma
tarefa pode esperar para trocar de máquina. Esse campo pode ser omitido caso não exista
nenhuma política especial.
: objetivo a ser minimizado.
O objetivo no problema que será tratado neste trabalho é minimizar o tempo no qual a
última tarefa deixa o sistema. Este tempo é chamado de makespan e é representado no campo
como
max
C .
Utilizaremos alguns dados de entrada para ilustrar alguns exemplos mais complexos
de ambientes de máquinas. Na matriz abaixo o elemento na i-ésima linha e na j-ésima coluna
contém o tempo necessário para se executar a tarefa j na máquina i:
3524
1234
2453
4321
No ambiente de open shop cada tarefa precisa ser executada nas várias máquinas
disponíveis, seguindo uma ordem que não precisa ser igual às das outras tarefas e que não é
pré-determinada. O símbolo usado no campo
para indicar um problema do open shop com
m máquinas é
Om
. Um problema de open shop com um número indeterminado de máquinas
é indicado por O. A figura a seguir é um diagrama de Gantt representando um escalonamento
11
para o problema de open shop com os dados de entrada citados anteriormente. O valor de
max
C
está marcado pela linha tracejada vertical.
Figura 2: Ambiente
open shop.
Um outro ambiente complexo de máquinas é o job shop. No job shop cada tarefa
precisa ser executada em todas as máquinas, seguindo sua própria ordem, que é pré-
estabelecida. O símbolo para o campo
no caso do problema do job shop com m máquinas é
Jm
. Na figura seguinte podemos ver um exemplo de escalonamento para o um problema de
job shop. Neste exemplo estamos definindo as seguintes ordens de execução nas máquinas
para cada tarefa:
Tarefas 1 e 3: seqüência de máquinas 1,2,3,4
Tarefas 2 e 4: seqüência de máquinas 4,3,2,1
Figura 3: Ambiente
job shop.
12
Um importante caso particular do job shop é o ambiente de flow shop, que ocorre
quando as seqüências de execução nas máquinas são idênticas para todas as tarefas. Nesse
caso, sem perda de generalidade, podemos assumir que a seqüência começa na máquina 1, vai
depois para a máquina 2, até a máquina m. O símbolo usado no campo
para um ambiente
flow shop com m máquinas é
Fm
, quando o m é fixo. Quando o problema tem um número
indeterminado de máquinas o símbolo utilizado é F. A figura seguinte ilustra um
escalonamento para um problema de flow shop.
Figura 4: Ambiente flow shop.
Quando, em um problema de flow shop, é acrescentada a restrição adicional de que as
máquinas executem as tarefas na mesma ordem temos um problema de permutation flow
shop. O símbolo usado no campo
no caso do problema de permutation flow shop é
Fm
,
como no flow shop genérico e o campo
é preenchido com o símbolo
prmu
. Com essa
restrição, a solução do problema restringe-se a encontrar uma permutação das tarefas. Na
figura seguinte podemos ver uma solução para um problema de permutation flow shop.
13
Figura 5: Permutation flow shop.
Usando a notação de três campos, o problema a ser pesquisado neste trabalho é o
max
|| CprmuF
m
Os dados do problema são:
quantidade de tarefas, n
quantidade de máquinas, m
duração da tarefa j ao ser executada na máquina i,
ji
p
,
Uma permutação de tarefas em um problema
max
|| CprmuF
m
é uma seqüência de
tarefas
n
jjj ,...,,
21
onde a tarefa que ocupa a k-ésima posição é representada por
k
j .
O tempo
k
ji
S
,
é o tempo de início (start) da tarefa que ocupa a k-ésima posição na
máquina i.
O tempo
k
ji
C
,
, que é o tempo de completação da tarefa
k
j
na máquina i pode ser
definido recursivamente como:
mipC
i
l
jlji
,...,1)1(
1
,,
11
nkpC
k
l
jj
lk
,...,1)2(
1
,1,1
nkmipCCC
kkkk
jijijiji
,...,2;,...,2),max()3(
,,,1,
1
14
As equações (1) dizem que a tarefa que ocupa a primeira posição pode começar a ser
executada na máquina i imediatamente após esta tarefa terminar a execução na máquina i-1.
As equações (2) estabelecem que a tarefa que ocupa a k-ésima posição pode começar
a ser executada na primeira máquina assim que terminar a execução da tarefa que ocupa a
(k-1)-ésima na mesma máquina.
As equações (3) dizem que o início da execução da tarefa que ocupa a posição
k
j na
máquina i está limitada ou pelo término da execução desta mesma tarefa na máquina i-1 ou
pelo término da execução da tarefa que ocupa a posição
1k
j na mesma máquina i.
O tempo
k
ji
C
,
pode também ser expresso como:
kkk
jijiji
pSC
,,,
.
1.2 PROGRAMAÇÃO INTEIRA
Para modelar e resolver o problema do Permutation Flow Shop utilizaremos a técnica
da Programação Inteira (PI). A programação inteira é uma técnica de otimização semelhante à
Programação Linear (PL), com a diferença de que, em PI, as variáveis são restritas a assumir
valores inteiros.
Eis a forma geral de um problema de PL:
xc
T
min
Sujeito a:
0
x
bAx
Onde c, x são vetores pertencentes a
n
R
,
m
Rb e A é uma matriz
n
m
. A função
xcxf
T
)( é chamada função-objetivo.
Um problema de Programa
ção Inteira tem a seguinte forma geral:
xc
T
min
15
Sujeito a:
n
Z
x
x
bAx
0
Onde
n
Z
é o conjunto de vetores n-dimensionais cujos elementos pertencem a Z, o
conjunto dos números inteiros. Neste trabalho utilizaremos a sigla PL para representar tanto a
técnica de programação linear quanto um problema de programação linear específico. Do
mesmo modo, a sigla PI servirá como abreviação da técnica de programação inteira e para se
referir a um problema de programação inteira específico.
A região viável de um PL é um poliedro. Um poliedro é uma região no espaço n-
dimensional delimitada por um número finito de hiperplanos, ou seja todo poliedro P pode ser
descrito na forma
bAxRxP
n
| .
Como conseqüência dessa definição podemos dizer que todo poliedro é a região viável
de um problema de programação linear.
A técnica de PL já foi bastante explorada e já existem diversos softwares no mercado
que implementam algoritmos que resolvem problemas de PL. A maioria dos softwares de PL
utiliza o algoritmo Simplex, criado em 1947 por G. Dantzig.
O algoritmo Simplex encontra uma solução ótima que necessariamente está em um
vértice desse poliedro, como na figura seguinte.
Figura 6: Região viável de um PL.
16
A região viável de um PI é o conjunto enumerável de pontos inteiros no espaço n-
dimensional delimitado pelas faces do poliedro do PL correspondente. Quando, dado um
problema de programação inteira (PI), retiramos desse problema a restrição de integralidade
temos como resultado um outro problema que é chamado relaxação linear do PI original. Este
problema resultante é, por construção, um problema de programação linear (PL).
Uma tentativa ingênua para encontrar a solução ótima do PI seria resolver a relaxação
linear pelo método Simplex e simplesmente arredondar a solução encontrada. Esta tentativa é
falha e pode levar a pontos que estão muito distantes da solução ótima do PI, como ilustra a
figura seguinte.
Figura 7: Região viável de um PI.
Sempre que modelamos um problema de PI estamos na verdade, escrevendo uma
formulação para o PI em questão. Se
n
ZX
for o conjunto de pontos viáveis de um PI,
então o poliedro P é uma formulação para X se e somente se
n
Z
P
X
.
Para todo PI existe uma formulação que, se resolvida como um PL, resultará na
solução ótima do PI. Essa formulação é chamada formulação ótima e é o fecho convexo dos
pontos viáveis do PI. Na figura seguinte o poliedro delimitado pelos eixos coordenados e
pelos segmentos tracejados é a formulação ótima do PI do exemplo da figura anterior.
Podemos ver que a solução ótima do PI agora é um ponto extremo do poliedro correspondente
à formulação ótima do PI. Entretanto, na maioria dos casos essa formulação ótima teórica não
17
é conhecida. Nesses casos, é necessário se trabalhar com formulações que apenas aproximam
a formulação ótima.
Figura 8: Formulação ótima de um PI.
Mesmo sem uma formulação ótima, dependendo da função objetivo, pode ocorrer que
a solução do PL resultante da relaxação linear deste PI seja inteira e portanto também seja a
solução do PI. Se isso não ocorrer, precisamos utilizar algoritmos mais sofisticados para
encontrar a solução exata para o PI original.
Para resolver problemas de programação inteira utilizaremos algoritmos que resolvem
vários subproblemas lineares. Particularmente, serão utilizados os algoritmos branch-and-
bound e o branch-and-cut.
O branch-and-bound resolve primeiramente a relaxação linear do PI original. Se a
solução desta relaxação for uma solução inteira, então o algoritmo pára. Caso contrário, ele
escolhe uma variável com valor fracionário para fazer o branch e resolve dois subproblemas:
um com essa variável fixada em um limite inferior (lower bound) e outro com ela fixada em
um limite superior (upper bound).
Na próxima figura vemos o fluxograma do algoritmo branch-and-bound.
18
Figura 9: Algoritmo de branch-and-bound.
Um modo intuitivo de representar a execução do algoritmo branch-and-bound é
através de uma árvore de subproblemas. Nessa árvore, sempre que é feito um branch, são
incluídos dois nós, um para cada subproblema adicionado. Os nós referentes aos
subproblemas S1 e S2 são inseridos como filhos do nó correspondente ao subproblema S
sobre o qual foi realizado o branch.
Uma maneira de acelerar a resolução de um PI é através da adição de planos de corte
ao conjunto de inequações do problema. Um plano de corte é uma inequação que não faz com
que nenhum ponto viável do PI se torne inviável. O objetivo da adição de um plano de corte é
“cortar” o poliedro correspondente à relaxação linear utilizada, ou seja, a inequação não deve
ser satisfeita pela solução fracionária atual. Em outras palavras, os planos de corte servem
para reforçar a formulação utilizada, deixando-a mais próxima da formulação ótima.
O algoritmo branch-and-cut procede de forma semelhante ao branch-and-bound. A
diferença é que o branch-and-cut pode adicionar alguns planos de corte antes de fazer o
branch, como ilustra a figura seguinte.
19
Figura 10: Branch-and-cut
1.3 OBJETIVOS DO TRABALHO
Esse trabalho tem os seguintes objetivos:
- Propor e analisar algumas regras de branch sobre uma formulação clássica de
programação inteira para o problema do Permutation Flow Shop. Essas regras
serão comparadas entre si e com a regra default do software CPLEX,
- Propor uma nova formulação de programação inteira para esse problema e a
comparar, em termos de tempo e qualidade do limite inferior obtido, com a
formulação clássica.
Todos os testes ser
ão realizados sobre o software CPLEX (resolvedor geral de
programação linear e inteira, desenvolvido pela empresa ILOG). O CPLEX será utilizado
através de uma Application Programming Interface (API) fornecida com a ferramenta e um
programa desenvolvido em C#.Net que invocará essa API.
2 RESULTADOS BÁSICOS SOBRE O PROBLEMA DO FLOWSHOP
O problema do Permutation Flowshop para duas máquinas pode ser resolvido com um
algoritmo polinomial. Este algoritmo é conhecido como algoritmo de Johnson (JOHNSON,
1954) e é descrito a seguir.
Figura 11: Algoritmo de Johnson.
Para ilustrar o algoritmo de Johnson consideraremos uma instância com 4 tarefas e 2
máquinas cujos tempos de processamento estão na matriz a seguir:
21
5324
2143
A figura seguinte mostra a execução passo-a-passo do algoritmo para estes dados de
entrada. As colunas já “visitadas” estão sombreadas.
Figura 12: Exemplo de execução do algoritmo de Johnson.
O gráfico de Gantt correspondente a esse exemplo é o da figura seguinte.
22
Figura 13: Exemplo de execução do algoritmo de Johnson – gráfico de Gantt.
Após a execução do algoritmo de Johnson, a seqüência de tarefas (L1, L2) gerada tem
as seguintes propriedades. Para cada tarefa j:
jj
jj
jj
ppseLjouLj
ppseLj
ppseLj
,2,1
,2,1
,2,1
)2()1(
2
1
Além disso, as tarefas em L1 estão em ordem crescente de tempo de processamento na
primeira máquina e as tarefas em L2 estão em ordem decrescente de tempo de processamento
na segunda máquina. Diremos que qualquer escalonamento que puder ser dividido em listas
(L1, L2) com essas propriedades é um escalonamento Johnson.
Para a prova do seguinte teorema, suporemos sem perda de generalidade que não
existem dois tempos de processamento iguais na matriz que define uma instância do flowshop
(sempre é possível aplicar pequenas perturbações à instância para que isso se verifique).
Nessas condições, uma única solução será um escalonamento Johnson e essa solução
S deve
ser exatamente a gerada pelo algoritmo de Johnson.
Teorema 1: O algoritmo de Johnson sempre gera um escalonamento ótimo para o
problema
max2
|| CprmuF .
Prova:
Suponhamos que existe um escalonamento ótimo S
0
que não é Johnson. Neste
escalonamento ótimo existem duas tarefas adjacentes j e k, onde j é seguido por k, tal que uma
das três condições a seguir é satisfeita:
23
(i) A tarefa j pertence à lista L2 e a tarefa k pertence à lista L1
(ii) As tarefas j e k pertencem à lista L1 e
kj
pp
,1,1
(iii) As tarefas j e k pertencem à lista L2 e
kj
pp
,2,2
Procederemos na prova examinando o que ocorre quando trocamos as tarefas j e k, o
que gera um novo escalonamento. Digamos que neste escalonamento existam as tarefas l e m
(se for preciso, l e m podem ser tarefas artificiais com tempos nulos) tais que um trecho do
escalonamento seja a seqüência l,j,k,m. Após a troca entre a tarefa j e a tarefa k o mesmo
trecho fica l,k,j,m.
O tempo de completação da tarefa j na máquina i é denotado por
ji
C
,
e o tempo de
completação da tarefa j na máquina i, após trocarmos de posição as tarefas j e k, é denotado
por
´
, ji
C
. O tempo em que a máquina 2 fica disponível para a tarefa m antes da troca das
tarefas é igual ao tempo de completação da tarefa k na máquina 2, ou seja, igual a
k
C
,2
. Ao
efetuarmos a troca das tarefas j e k, o tempo no qual a máquina 2 fica disponível para a tarefa
m é igual ao tempo de completação da tarefa j na máquina 2, ou seja, igual a
´
,2 j
C
.
Utilizando a definição recursiva de
ji
C
,
que fizemos anteriormente temos:
),,max(
),,max(
),,max(
),,max(
),),max(max(
),max(
3
,2,1,1,1
2
,2,2,1,1
1
,2,2,2
,2,1,1,2,2,1,1,2,2,2
,2,1,1,2,2,1,2,2,2
,2,1,1,2,1,2,2
,2,1,1,2,1,2
,2,1,2,2
kkjlkjjlkjl
kkjkjjlkjl
kkjkjjkjl
kkjjjjl
kkjjjl
kkjk
pppCpppCppC
ppCpppCppC
ppCppCppC
ppCpCpC
ppCpCC
pCCC
enquanto
),,max(
),),max(max(
),),max(max(
),max(
3
,2,1,1,1
2
,2,2,1,1
1
,2,2,2
,2,1,1,1,2,1,1,2
,2,1,1,1,2
´
,1,2
,2
´
,1
´
,2
´
,2
jjkljkkljkl
jjklkkll
jjklkkl
jjkj
pppCpppCppC
pppCppCC
pppCpCC
pCCC
24
Se a condição (i) for verdadeira, então
jj
pp
,1,2
e
kk
pp
,2,1
. Com isso, o primeiro
termo dentro da função max expressão de
k
C
,2
é igual ao primeiro termo dentro da função
max da expressão de
´
,2 j
C
. Mas o segundo termo da função max na expressão de
´
,2 j
C
é
menor que o terceiro termo da função max na expressão de
k
C
,2
e o terceiro termo na função
max da expressão de
´
,2 j
C
é menor que o segundo termo da função max da expressão de
k
C
,2
.
Portanto,
kj
CC
,2
´
,2
, o que implica que a máquina 2 estará disponível para a tarefa m no
escalonamento resultante da troca das tarefas em um tempo menor do que no escalonamento
existente antes da troca.
Se a condição (ii) for verdadeira, então
jj
pp
,2,1
,
kk
pp
,2,1
e
kj
pp
,1,1
. Com isso,
o segundo e o terceiro termos na função max da expressão de
´
,2 j
C
são menores que o
segundo termo da função max da expressão de
k
C
,2
. Portanto
kj
CC
,2
´
,2
.
Se a condição (iii) for verdadeira, então
jj
pp
,1,2
,
kk
pp
,1,2
e
kj
pp
,2,2
. Com
isso, o segundo e o terceiro termos na função max da expressão de
´
,2 j
C
são menores que o
terceiro termo da função max da expressão de
k
C
,2
. Portanto,
kj
CC
,2
´
,2
.
Se qualquer uma das condições for verdadeira, então a troca das posições das tarefas
gera um novo escalonamento cujo makespan é menor ou igual ao makespan antes da troca.
Dado o escalonamento inicial S
0
podemos aplicar sucessivamente as trocas entre duas
posições das tarefas, construindo uma seqüência de escalonamentos como a mostrada abaixo:
SSSS
210
,
onde o escalonamento
S é Johnson e portanto teria sido o gerado pelo algoritmo de Johnson.
Ou seja, a solução
S deve ser uma solução ótima.
Para finalizar a prova, é preciso mostrar que existe uma seqüência de trocas que seja
finita, isto é, que não existe a possibilidade de se ficar ciclando sobre as mesmas soluções sem
que se chegue em
S . Para tal basta começar realizando trocas sobre a condição (i), até que
todas as tarefas em L1 precedam todas as tarefas em L2. Só quando a condição (i) for
satisfeita se deve fazer trocas sobre as condições (ii) ou (iii) para ordenar adequadamente as
tarefas dentro de L1 e de L2. Resultados conhecidos em teoria da ordenação (KNUTH, 1973)
garantem a convergência dessas duas etapas em O(n
2
) trocas.
25
Uma propriedade interessante do problema
max
|| CF
m
, é a que afirma que sempre é
possível encontrar uma solução ótima deste problema no qual não haja mudança na seqüência
de execução das tarefas entre as máquinas 1 e 2 e entre as máquinas m-1 e m. Esta
propriedade é formalizada no teorema enunciado a seguir.
Teorema 2: Em um problema
max
|| CF
m
sempre é possível encontrar um escalonamento
ótimo no qual não é necessária troca na seqüência de execução das tarefas entre
as máquinas 1 e 2 e entre as máquinas m-1 e m.
Prova: Provaremos somente a afirmação envolvendo as máquinas 1 e 2.
Suponhamos que exista uma instância do
max
|| CF
m
em cuja solução ótima exista uma
troca na seqüência de execução das tarefas nas máquinas entre a máquina 1 e a máquina 2. Se
isso for verdade, então existe um trecho da seqüência de tarefas k,...,j na máquina 1 e um
trecho j,...,k na máquina 2. A figura seguinte ilustra essa situação.
Figura 14: Troca na ordem das tarefas entre as máquinas 1 e 2.
Dada essa solução, construiremos um novo escalonamento da seguinte forma:
1
– Fixe a seqüência e os tempos de execução das tarefas na máquina 2;
2 – Troque a ordem das tarefas j e k na máquina 1.
26
Depois de fazer isso, temos as seguintes condições:
(i) a tarefa j continua terminando na máquina 1 antes de iniciar na máquina 2, pois ela
foi “adiantada”.
(ii) a tarefa k termina exatamente no tempo em que a tarefa j terminava antes da troca,
pois não há intervalos na máquina 1.
A figura seguinte mostra como fica o escalonamento depois dessa troca.
Figura 15: Mesma ordem das tarefas entre as máquinas 1 e 2.
Vemos que o trecho na máquina 1 cujos extremos são as tarefas j e k permanece com a
mesma largura T e com os mesmos tempos de início e término. Portanto, todas as tarefas que
estão neste trecho antes da troca continuam nesse trecho depois da troca. Com isso, o
escalonamento permanece viável.
Se repetirmos essa troca para cada par de tarefas que estejam em ordem diferente nas
máquinas 1 e 2 teremos, no final, um escalonamento que continua sendo ótimo e no qual a
ordem de execução das tarefas nas máquinas 1 e 2 é a mesma.
Um resultado imediato do Teorema 2 é o de que o valor da solução ótima de um
problema de flowshop com 3 máquinas independe de este problema admitir mudança na
ordem de execução das tarefas entre as máquinas ou não. Isso porque existe uma solução
ótima em que não há mudança de ordem de execução de tarefas entre a máquina 1 e a
27
máquina 2 e entre a máquina 2 e a máquina 3. Consequentemente, não precisa haver troca de
ordem das tarefas entre a máquina 1 e a máquina 3. Naturalmente o mesmo é válido para
problemas de flowshop com 2 máquinas (logo o algoritmo de Johnson também é ótimo para o
max2
|| CF
).
A partir de m=4, existem instâncias para as quais é possível encontrar soluções ótimas
com valores diferentes para os problemas
max
|| CF
m
e
max
|| CprmuF
m
. Um exemplo de
instância em que isso ocorre é a de tempos
332
133
141
411
.
A figura abaixo mostra a solução ótima quando consideramos o permutation flow shop
para estes dados de entrada.
Figura 16: Solu
ção ótima para o exemplo de permutation flow shop.
A solu
ção ótima para este problema quando não exigimos que a ordem de execução
das tarefas seja a mesma em todas as máquinas é mostrada na figura seguinte. O makespan
ótimo para o
max
|| CF
m
é menor que o do
max
|| CprmuF
m
nesse caso.
28
Figura 17: Solução ótima para o exemplo de flow shop.
A dificuldade de resolução de problemas
max
|| CF
m
é o fato de esses problemas serem
NP-difíceis para
3
m
, como mostra o teorema enunciado a seguir.
Teorema 3: O problema
max3
|| CF é fortemente NP-difícil.
Para provar o teorema 3 utilizaremos a seguinte definição de um problema
sabidamente fortemente NP-difícil (GAREY; JOHNSON, 1979):
Definição 1: O problema 3-partição é definido como:
Seja um conjunto A de 3t números inteiros
t
aaa
321
,...,, tais que
tba
t
i
i
3
1
e
ti
b
a
b
i
3,...,1;
2
4
A pergunta é: “Podemos particionar o conjunto A em t subconjuntos disjuntos
t
AAA ,...,,
21
tais que para
ti
1
temos
ba
i
Aa
?”.
29
Prova: Transformaremos uma instância geral do problema de 3-partição de 3t
números em uma instância do
max3
|| CF
com n=4t+1 tarefas tendo as seguintes durações:
.3,...,1,0,,0
,0,,2
,1,...,1,2,,2
,2,,0
,3,2,1
,3,2,1
,3,2,1
0,30,20,1
tjpapp
pbpbp
tjbpbpbp
bpbpp
jtjjtjt
ttt
jjj
Seja z=(2t+1)b. Um makespan de valor z pode ser obtido se as primeiras t+1 tarefas
são escalonadas seguindo a seqüência 0,1,...,t. Estas tarefas deixam t espaçamentos entre
tarefas na máquina 2, cada espaçamento de tamanho igual a b. As tarefas t+1, t+2, ...,t+3t
precisam ser escalonadas entre as primeiras t+1 tarefas, de modo que ocupem os
espaçamentos que existem na máquina 2. A única forma de fazer isso é agrupar as tarefas t+1,
t+2, ...,t+3t em t grupos de 3 tarefas cada, onde a soma das durações de cada grupo é igual
a b. A figura seguinte ilustra o flow shop criado.
Figura 18: Relação entre o
max3
|| CF
e o 3-partition.
Um makespan de valor z pode ser obtido se e somente se o problema 3-partição tem
solução.
A equival
ência entre os problemas
max3
||CF e
max3
|| CprmuF mostrada
anteriormente, faz com que o Teorema 3 também implique que o problema de permutation
flowshop também é NP-difícil para
3
m
.
3 REVISÃO BIBLIOGRÁFICA
3.1 HEURÍSTICAS
As heurísticas utilizadas são, em grande parte, construtivas, ou seja, em que a
seqüência é construída a cada passo. Exemplos populares de heurísticas construtivas são
apresentadas em Campbell (1970), em Palmer (1965) e em Dannenbring (1977). Gupta (1971)
explora a relação entre o escalonamento e a ordenação para encontrar uma solução
aproximada para o permutation flowshop. Röck e Schmidt (1982) utilizaram a técnica de
agregação de máquinas para aplicar uma heurística baseada na regra de Johnson.
3.2 MÉTODOS EXATOS
Held e Karp (1962) utilizaram programação dinâmica para encontrar soluções exatas
do flow shop. Ignall e Shrage (1965) propuseram os primeiros limites combinatórios para
cálculo de limite inferiores para serem utilizados em um algoritmo de branch-and-bound.
Lageweg et al. (1978) apresentaram a estrutura geral dos algoritmos de branch-and-bound
para a resolução do permutation flowshop. Vários outros autores, incluindo Lomnicki (1965),
Brown e Lomnicki (1966), McMahon e Burton (1967), Potts (1980), Grabowski (1980),
Carlier e Rebaï (1996) e Ladhari e Haouari (2005), construíram algoritmos desse tipo. Esse
último, que é o mais eficiente conhecido atualmente, baseia-se em limites inferiores
conseguidos através da resolução de uma relaxação do problema sobre pares de máquinas. O
algoritmo implementado por Ladhari e Haouari conseguiu resolver todas as instâncias de
Taillard 20x5 (20 tarefas e 5 máquinas), 20x10 e 50x5 em tempos razoáveis. No entanto, um
aspecto que chama a atenção é a grande quantidade de nós gerados para alguns problemas
31
(40535661 nós para um dos problemas 20x10, por exemplo). Esse algoritmo consegue
resolver muitas instâncias 100x5 e até algumas de 200x5 e 100x10. Entretanto ele não resolve
as instâncias 20x20 de Taillard e nem as 50x20, que até hoje permanecem em aberto.
Muitas formulações de PI para o Permutation Flowshop (ver Tseng et al., 2005) já
foram propostas. Entretanto, até hoje nenhum algoritmo de branch-and-bound sobre essas
formulações se mostrou superior aos algoritmos de branch-and-bound combinatórios.
Alguns autores dedicaram-se a fazer comparações entre métodos de resolução do
problema do flowshop. Entre esses destacam-se os trabalhos de Ashour (1970), que comparou
alguns dos primeiros métodos de resolução desse problema.
4 ESTUDO DE REGRAS DE BRANCH PARA A FORMULAÇÃO DE WILSON
4.1 FORMULAÇÃO DE WILSON
Modelaremos o problema do permutation flow shop como o PI da forma proposta em
Wilson (1989) (que na verdade é um pequeno melhoramento do modelo proposto em Wagner
(1959)). Para esta formulação são definidas as seguintes variáveis:
k
i
s
: (start) tempo de início da tarefa que ocupa a k-ésima posição na máquina i.
k
i
c
: (completion) tempo de término da tarefa que ocupa a k-ésima posição na máquina i.
k
i
t
: duração da tarefa que ocupa a k-ésima posição na máquina i.
k
j
x
: variável binária que assume o valor 1 quando a tarefa j ocupa a k-ésima posição e assume
o valor zero caso contrário.
Todas as variáveis são inteiras.
As constantes
ji
p
,
são dados de entrada do problema e representam a duração da
tarefa j na i-ésima máquina. Estas constantes são números inteiros não negativos.
A formulação de Wilson é a que segue:
33
njminkZtcsx
s
minkcs
minkcs
minktsc
minkxpt
nkx
njx
asujeito
c
k
i
k
i
k
i
j
k
k
i
k
i
k
i
k
i
k
i
k
i
k
i
n
j
k
jji
k
i
n
j
k
j
n
k
k
j
n
m
,...,1,...,1,...,1,,,
06
,...,2,...,15
,...,1,...,24
,...,1,...,13
,...,1,...,12
,..,11
,...,11
1
:
min
1
1
1
1
1
,
1
1
As restrições (1) são chamadas restrições de atribuição (assignment). Elas definem que
uma tarefa pode estar em uma e somente uma posição e que uma posição pode ser ocupada
por uma e somente uma tarefa. As restrições (2) definem a duração da tarefa que ocupa a
k-ésima posição na máquina i como sendo igual à duração da k-ésima tarefa na máquina i se
ela ocupar a k-ésima posição.
As restrições (3) simplesmente definem as variáveis s e c. As restrições (4) informam
que, para cada máquina, a tarefa que ocupa a k-ésima posição só pode começar a ser
executada quando a tarefa que ocupa a (k-1)-ésima posição terminar. As restrições (5) dizem
que uma tarefa que ocupa a posição k só pode começar a ser executada na máquina i quando
esta mesma tarefa terminar na máquina (i-1). A restrição (6) força o escalonamento a começar
no tempo zero.
Algumas instâncias de problemas podem gerar relaxações lineares bem ruins quando
se usa a formulação de Wilson. Por exemplo, a instância 2 X 2
13
13
leva à relaxação linear em cuja solução as variáveis de assignment valem
}2,1{}2,1{5,0 kjx
k
j
com função objetivo de 6, enquanto o ótimo inteiro é 7.
34
4.2 BRANCH SOBRE VARIÁVEIS ISOLADAS
Ignall e Shrage (1965) e por Lomnicki (1965) propuseram a mesma regra de branch
em seus algoritmos para o Permutation Flowshop. Essa regra consiste em, a cada branch,
fixar uma tarefa em uma determinada posição e, então, gerar todas as permutações utilizando
as posições não-fixadas. A regra proposta por eles primeiro fixa a primeira posição, depois a
segunda, a terceira, etc. Um exemplo de execução dessa regra está mostrada na figura
seguinte.
Figura 19: Exemplo de execução da regra de Ignall, Shrage e Lomnicki.
Uma melhoria dessa a regra para escolha de variáveis de branch foi feita por Potts
(1980) (essa regra posteriormente foi usada por Carlier e Rebaï (1996) e Ladhari e Haouari
(2005)). Nenhum desses autores utiliza programação inteira para resolver os sub-problemas e
sim limites combinatórios para cortar sub-problemas da árvore de branch. Um exemplo de
árvore de branch pela regra de Potts é apresentado na figura seguinte.
35
Figura 20: Exemplo de execução da regra de branch de Potts.
Em cada nó da figura um quadrado cinza representa uma posição fixada. O número
dentro do quadrado é o número da posição que foi atribuída à posição. Em cada nó o
algoritmo calcula um limite inferior do makespan para as possíveis permutações. Se esse
limite inferior for maior que o melhor limite superior conhecido, então o nó correspondente a
esse makespan é cortado da árvore. A estratégia para selecionar o nó que será explorado
primeiro é simplesmente escolher, a cada nível da árvore, aquele com o menor limite inferior.
Para a decisão de qual posição fixar em cada nível da árvore são escolhidas, alternadamente,
as primeiras e as últimas posições. Assim, primeiro é escolhida a posição 1, em seguida a
posição n, depois a posição 2, e então a posição n-1 e assim por diante.
A primeira técnica adotada nesse trabalho consiste em estabelecer um critério
semelhante ao de Potts na escolha da variável de branch em cada nó da árvore de branch.
Entretanto, como estaremos trabalhando com um branch-and-bound baseado na formulação
de Wilson, a regra de branch conta com os valores das variáveis fracionárias em cada sub-
problema para tomar sua decisão. Além disso, nesse contexto que a resolução de cada sub-
problema exige um problema de programação linear, ter uma árvore de branch n-ária (cada
sub-problema pode ter até n-1 filhos) seria muito caro. Seria melhor ter uma regra que
pudesse usar a mesma idéia de Potts em uma árvore binária.
O algoritmo de escolha da variável de branch é o seguinte:
36
Figura 21: Regra de escolha da variável de branch – regra 1.
Doravante chamaremos essa regra de “regra 1”.
É importante notar que o algoritmo descrito na figura acima deve ser executado cada
vez que um problema é escolhido da lista de problemas não-resolvidos e solucionado. O
problema previamente escolhido é referenciado como “nó atual”. Como, para cada nó da
árvore de branch só podem existir, no máximo, dois nós-filhos, a árvore de branch, nesse
caso, será uma árvore binária.
O algoritmo escolhe, dentre as variáveis x de valor fracionário, aquelas
correspondentes à primeira posição que tenha o maior valor. Se nenhuma variável na primeira
posição for fracionária, então ele testa as variáveis correspondentes à última posição. O
algoritmo segue testando as variáveis da segunda posição, da posição k-1, e assim por diante.
As variáveis escolhidas pelo algoritmo para serem fixadas são escolhidas, dessa forma, “de
fora para dentro” do escalonamento. Por esse motivo, somente as variáveis x são consideradas
na regra 1, já que essas variáveis são suficientes para estabelecer as posições de cada tarefa.
Foram feitas algumas rodadas de resolução de instâncias do permutation flow shop
com as formulações de Wilson com e sem regra de branch. As instâncias foram resolvidas em
um computador personal computer (PC) com processador Intel Core Duo de 2 Ghz e 2 Gb de
memória RAM.
37
As instâncias escolhidas foram as fornecidas por Éric Taillard, utilizadas como
exemplos em vários trabalhos acadêmicos. As instâncias contêm tempos de duração das
tarefas nas máquinas gerados aleatoriamente e que, posteriormente são selecionadas de forma
a tornar o problema o mais difícil possível de ser resolvido.
Utilizaremos a notação Tai_xx_yy_zzz para identificar o problema de Taillard que
estivermos usando como exemplo, onde xx é o número de tarefas, yy é o número de máquinas
e zzz é o número do problema, já que Taillard fornece um conjunto de 10 problemas para
cada par de número de tarefas e número de máquinas. Os limites superiores e inferiores
conhecidos dos problemas são também fornecidos por Taillard e são os da tabela seguinte.
Problema LB UB
tai20_5_001 1278
1278
tai20_5_002 1359
1359
tai20_5_003 1081
1081
tai20_5_004 1293
1293
tai20_5_005 1235
1235
tai20_5_006 1195
1195
tai20_5_007 1234
1234
tai20_5_008 1206
1206
tai20_5_009 1230
1230
tai20_5_010 1108
1108
tai20_10_001
1582
1582
tai20_10_002
1659
1659
tai20_10_003
1496
1496
tai20_10_004
1377
1377
tai20_10_005
1419
1419
tai20_10_006
1397
1397
tai20_10_007
1484
1484
tai20_10_008
1538
1538
tai20_10_009
1593
1593
tai20_10_010
1591
1591
tai20_20_001
2297
2297
tai20_20_002
2099
2099
tai20_20_003
2326
2326
tai20_20_004
2223
2223
tai20_20_005
2291
2291
tai20_20_006
2226
2226
tai20_20_007
2273
2273
tai20_20_008
2200
2200
tai20_20_009
2237
2237
tai20_20_010
2178
2178
tai50_5_001 2724
2724
tai50_5_002 2834
2834
tai50_5_003 2621
2621
tai50_5_004 2751
2751
tai50_5_005 2863
2863
tai50_5_006 2829
2829
38
Problema LB UB
tai50_5_007 2725
2725
tai50_5_008 2683
2683
tai50_5_009 2552
2552
tai50_5_010 2782
2782
tai50_10_001
2991
2991
tai50_10_002
2867
2867
tai50_10_003
2839
2839
tai50_10_004
3063
3063
tai50_10_005
2976
2976
tai50_10_006
3006
3006
tai50_10_007
3093
3093
tai50_10_008
3037
3037
tai50_10_009
2897
2897
tai50_10_010
3065
3065
tai50_20_001
3771
3850
tai50_20_002
3668
3704
tai50_20_003
3591
3640
tai50_20_004
3635
3720
tai50_20_005
3553
3610
tai50_20_006
3667
3681
tai50_20_007
3672
3704
tai50_20_008
3627
3691
tai50_20_009
3645
3743
tai50_20_010
3696
3756
Tabela 1: Limites inferiores e superiores para as instâncias de Taillard utilizadas.
Na tabela anterior UB (upper bound) significa limite superior e LB (lower bound),
limite inferior. Quando o valor do limite superior está em negrito isso significa que ele é igual
ao limite inferior e que, portanto, esse valor é ótimo. Alguns desses problemas não serão
utilizados em todos os experimentos feitos nesse trabalho, por questões de performance.
Para testar a regra de branch implementada foram utilizadas somente as instâncias de
20 tarefas. Para cada problema foi fornecido como limite superior o valor 01,0
UB , onde
UB é o valor do limite superior para o problema sendo resolvido. Apesar de não ser possível
obter a solução dos problemas com esse limite superior porque esse limite superior torna os
problemas inviáveis, diremos que um problema foi “resolvido” quando detectamos que ele é
inviável. O uso desses limites serviu para eliminar a aleatoriedade nos testes devido ao fato da
heurística presente no CPLEX encontrar ou não soluções de boa qualidade rapidamente.
A tabela seguinte mostra os resultados conseguidos sem utilizar nenhuma regra de
branch explícita. Foi estabelecido um limite máximo de 500 branches para a resolução de
cada instância.
39
Problema Resolvido Tempo
N
úmero de
Iterações
Profundidade
máxima Média Down Média Up
tai20_5_001 Não 16,78
500
52
0,62
1,57
tai20_5_002 Não 7,75
500
70
0,08
0,13
tai20_5_003 Não 7,48
500
60
0,34
0,53
tai20_5_004 Não 8,8
500
66
1,62
1,13
tai20_5_005 Não 10,06
500
87
0,29
0,86
tai20_5_006 Não 24,03
500
53
0,09
0,18
tai20_5_007 Sim 0,08
0
0
0
0
tai20_5_008 Não 9,56
500
58
0,37
0,32
tai20_5_009 Não 14,86
500
44
0,87
1,71
tai20_5_010 Não 17,47
500
92
0,53
1,86
tai20_10_001 Não 61,55
500
143
0,69
9,46
tai20_10_002 Não 89,97
500
113
0,83
9,28
tai20_10_003 Não 54,61
500
62
0,99
4,26
tai20_10_004 Não 53,59
500
63
1,12
4,28
tai20_10_005 Não 58,66
500
110
1,16
4,2
tai20_10_006 Não 85,33
500
101
2,13
1,72
tai20_10_007 Não 31,2
500
82
1,42
14,86
tai20_10_008 Não 72,53
500
107
0,82
20,8
tai20_10_009 Não 59,5
500
57
3,1
4,93
tai20_10_010 Não 51,22
500
108
0,95
12,03
tai20_20_001 Não 183,41
500
264
0,92
19,79
tai20_20_002 Não 278,92
500
162
1,59
30,96
tai20_20_003 Não 279,13
500
265
1,61
24,14
tai20_20_004 Não 193,2
500
189
1,39
22,7
tai20_20_005 Não 345,58
500
145
2,03
23,23
tai20_20_006 Não 215,05
500
232
1,21
29,96
tai20_20_007 Não 236,86
500
223
1,33
13
tai20_20_008 Não 193,89
500
162
1,58
16,57
tai20_20_009 Não 204,19
500
199
1,82
24,38
tai20_20_010 Não 306
500
185
1,45
17,77
Médias: 118,47
1,1
10,55
Tabela 2: Resultados da resolução do permutation flow shop com a formulação de Wilson com a regra de branch
default do CPLEX.
A coluna “resolvido” informa se o problema foi resolvido ou não, ou seja, se o
CPLEX detectou que o problema é inviável, A coluna “Tempo” é o tempo total, em segundos,
que a resolução da instância demorou. A coluna “número de iterações” mostra o número de
branches feitos. Quando o número de branches é igual a zero isso significa que a relaxação
linear do problema já detectou a inviabilidade do problema, não tendo sido necessário fazer
nenhum branch. A coluna “profundidade máxima” informa a profundidade do nó mais
profundo na árvore de branch que foi resolvido.
As colunas
“média down” e “média up” representam estatísticas que medem a melhora
de cada tipo de branch. Quando uma variável fracionária é escolhida para fazer um branch
40
dizemos que ela é a variável de branch. Se o branch é feito limitando essa variável pelo seu
teto (
jj
xx
~
) então ela o branch é chamado de branch “up”. Ao contrário, se a variável de
branch estiver sendo limitada pelo seu chão (
jj
xx
~
), então esse branch é chamado de
branch “down”. Cada vez que um nó é resolvido, o que é resolvido na verdade é a relaxação
linear correspondente àquele nó. Para cada nó resolvido, então, sabemos o valor da função-
objetivo da relaxação linear correspondente e podemos calcular uma média do acréscimo da
função objetivo de cada nó para seus filhos. O algoritmo da figura seguinte mostra como essas
médias são calculadas.
Figura 22: Cálculo da média do acréscimo da função objetivo nos branches.
No algoritmo acima, a fun
ção “valor” retorna o valor da função-objetivo da relaxação
linear relacionada a um nó da árvore de branch. No final da execução da função principal do
algoritmo a variável acrescimoUp conterá o valor médio do acréscimo dos branches up e a
variável acrescimoDown conterá o valor médio do acréscimo dos branches down. São esses
valores que são mostrados nas colunas “média down” e “média up” da tabela anterior. Na
41
última linha da tabela são mostradas médias dos valores das respectivas colunas. Podemos
observar que os branches estão bastante desequilibrados, com o branch up melhorando, em
média, o valor da função-objetivo em 10,55 e o branch down melhorando em apenas 1,1. Para
entender por que isso ocorre precisamos nos lembrar da formulação de Wilson,
principalmente de parte das equações de assignment que fixam o somatório dos valores das
variáveis x de uma posição k do escalonamento:
nkx
n
j
k
j
,..,11
1
.
Como todas as variáveis são inteiras, os únicos valores que as variáveis x podem
assumir são 0 e 1 (nesse caso dizemos que essas variáveis são binárias). Já que não
estabelecemos nenhuma regra de branch explícita, o CPLEX pode escolher as variáveis x em
um determinado branch. Se for escolhida a variável
k
j
x
, para algum j e algum k, por exemplo,
o branch down fixará essa variável em zero, o que permite que qualquer variável
l
k
x
, para
jl
assuma o valor 1. No entanto, quando é feito o branch up nessa mesma variável
k
j
x
,
essa variável é fixada no valor 1. Com isso, todas as outras variáveis
l
k
x
, para jl
são
forçadas a assumir o valor 0. Por isso, o branch up é muito mais forte, mais restritivo que o
branch down e isso explica a maior média de aumento do valor da função-objetivo do branch
up.
Uma discrepância tão grande entre as duas médias de aumento dos branches é muito
ruim, pois significa que a árvore de branch está muito desbalanceada e que,
conseqüentemente, há uma grande quantidade de nós que têm que ser resolvidos.
A tabela seguinte mostra os resultados da rodada utilizando a regra default do CPLEX
com limite de 5000 branches. Os problemas de Taillard de 50 tarefas e 5 máquinas também
foram resolvidos.
42
Problema Resolvido
Tempo
N
úmero de
Iterações
Profundidade
máxima Média Down Média Up
tai20_5_001 Não 165,17
5000
67
0,82
1,66
tai20_5_002 Não 117,3
5000
83
0,16
0,41
tai20_5_003 Não 94,03
5000
73
0,55
0,59
tai20_5_004 Não 81,05
5000
72
1,69
1,11
tai20_5_005 Não 143,19
5000
87
0,68
0,99
tai20_5_006 Não 266,11
5000
57
0,09
0,2
tai20_5_007 Sim 0,08
0
0
0
0
tai20_5_008 Não 161,2
5000
76
0,42
0,41
tai20_5_009 Não 165,64
5000
60
0,75
1,92
tai20_5_010 Não 185,02
5000
92
0,81
2,08
tai20_10_001
Não 3307,79
5000
153
0,82
9,18
tai20_10_002
Não 3834,68
5000
165
1,1
8,45
tai20_10_003
Não 2437,89
5000
83
1,2
4,04
tai20_10_004
Não 2996,16
5000
96
0,81
3,97
tai20_10_005
Não 2716,95
5000
128
1,07
1,46
tai20_10_006
Não 2715,61
5000
121
2
1,18
tai20_10_007
Não 1453,74
5000
96
1,93
9,24
tai20_10_008
Não 3293,65
5000
150
1,4
11,81
tai20_10_009
Não 1713,82
5000
107
3,4
2,75
tai20_10_010
Não 2477,84
5000
134
1,26
11,9
tai20_20_001
Não 10342,61
5000
264
1,2
18,74
tai20_20_002
Não 13687,03
5000
229
1,55
21,32
tai20_20_003
Não 12479,57
5000
265
1,41
21,98
tai20_20_004
Não 9088,59
5000
238
1,11
24,53
tai20_20_005
Não 17433,8
5000
189
2,19
17,55
tai20_20_006
Não 4078,64
5000
235
1,02
18,93
tai20_20_007
Não 1988,95
5000
223
1,38
12,99
tai20_20_008
Não 1602,48
5000
214
1,32
15,6
tai20_20_009
Não 1617,7
5000
230
1,42
18,61
tai20_20_010
Não 2350,86
5000
185
1,61
15,82
tai50_5_001 Sim 0,59
0
0
0
0
tai50_5_002 Sim 11,92
6
4
0,1
3,65
tai50_5_003 Não 1988,63
5000
139
0,22
1,1
tai50_5_004 Não 1266,44
5000
158
0,08
0,26
tai50_5_005 Não 1007,33
5000
165
0
0
tai50_5_006 Sim 10,38
4
4
0,67
1,79
tai50_5_007 Não 2318,42
5000
181
0,19
0,71
tai50_5_008 Sim 0,61
0
0
0
0
tai50_5_009 Não 2605,34
5000
152
0,17
0,47
tai50_5_010 Sim 0,52
0
0
0
0
Médias
124,38
0,92
6,69
Tabela 3: Resultados da resolução do permutation flow shop com a formulação de Wilson com a regra de
branch default do CPLEX com limite de 5000 branches.
A tabela a seguir mostra os resultados conseguidos utilizando a regra 1:
43
Problema Resolvido Tempo
N
úmero de
Iterações
Profundidade
máxima Média Down Média Up
tai20_5_001 Sim 7,78
109
24
1,81
2,77
tai20_5_002 Não 32,66
500
33
0,28
0,38
tai20_5_003 Sim 4,06
49
12
0,53
1
tai20_5_004 Sim 2,92
31
10
3,56
2,39
tai20_5_005 Não 15,55
500
34
1,36
2,41
tai20_5_006 Sim 5,78
63
17
0,02
0,12
tai20_5_007 Sim 0,08
0
0
0
0
tai20_5_008 Sim 3,98
59
16
0,96
2
tai20_5_009 Não 29,41
500
44
0,12
0,73
tai20_5_010 Sim 2,66
14
6
5,49
4,02
tai20_10_001 Não 95,73
500
37
5,68
13,78
tai20_10_002 Não 110,56
500
30
4,34
13,76
tai20_10_003 Não 71,16
500
32
2,64
6,67
tai20_10_004 Não 92,58
500
39
2,43
5,62
tai20_10_005 Não 101,8
500
29
5,1
10,66
tai20_10_006 Não 106,33
500
28
4,32
11,25
tai20_10_007 Não 49,09
500
43
5,47
14,03
tai20_10_008 Não 115,95
500
33
6,01
22,49
tai20_10_009 Não 73,63
500
32
5,29
6,15
tai20_10_010 Não 98
500
32
7,44
19,22
tai20_20_001 Não 253,23
500
62
7,62
29,4
tai20_20_002 Não 283,8
500
39
9,62
36,26
tai20_20_003 Não 242,11
500
56
8,32
35,07
tai20_20_004 Não 159,09
500
52
9,16
33,12
tai20_20_005 Não 301,11
500
51
6,25
42,51
tai20_20_006 Não 296,67
500
52
8,21
35,79
tai20_20_007 Não 273,95
500
55
7,08
29,32
tai20_20_008 Não 191,45
500
42
10,14
25,1
tai20_20_009 Não 234,03
500
58
9,04
31,33
tai20_20_010 Não 284,61
500
55
6,56
30,48
Médias 35,1
4,83
15,59
Tabela 4: Resultados da execução da regra 1 com máximo de 500 branches.
Podemos verificar que os valores médios do aumento da função-objetivo aumentaram,
em relação à execução sem nenhuma regra de branch. Além disso, a profundidade média
diminuiu de 118,47 para 42,85, o que também é uma medida da eficiência da regra 1. Dos
problemas que não conseguíamos detectar inviabilidade, agora temos 6 que, com a utilização
da regra 1, podemos detectar que são inviáveis (o problema Tai20_5_007 já tinha sido
resolvido sem a regra de branch, porque não precisou de nenhum branch para ser resolvido,
logo não houve avanço com esse problema).
Apesar desses avan
ços, esse branch ainda é bastante desbalanceado, pois a média entre
o aumento do lado up ainda é mais de três vezes maior do que a média do aumento do lado
down. Foi feita uma nova rodada de execução desses mesmos problemas e dos problemas de
44
50 tarefas e 5 máquinas, dessa vez com limite máximo de 5000 branches. O resultado é
mostrado na tabela abaixo:
Problema Resolvido
Tempo
N
úmero de
Iterações
Profundidade
máxima Média Down
Média Up
tai20_5_001 Sim 13
109
24
1,81
2,77
tai20_5_002 Não 398,19
5000
54
0,21
0,28
tai20_5_003 Sim 6,73
49
12
0,53
1
tai20_5_004 Sim 5,02
31
10
3,56
2,39
tai20_5_005 Não 250,36
5000
47
1,42
2,79
tai20_5_006 Sim 9,64
63
17
0,02
0,12
tai20_5_007 Sim 0,11
0
0
0
0
tai20_5_008 Sim 6,89
59
16
0,96
2
tai20_5_009 Sim 90,27
1153
44
0,05
0,38
tai20_5_010 Sim 4,47
14
6
5,49
4,02
tai20_10_001
Não 786,14
5000
66
2,83
8,12
tai20_10_002
Não 1973,8
5000
43
3,49
11,89
tai20_10_003
Não 1252,42
5000
48
3,07
6,84
tai20_10_004
Não 1124,52
5000
66
1,54
4,14
tai20_10_005
Não 1398,72
5000
57
1,88
4,45
tai20_10_006
Não 1445,88
5000
64
2,06
5,26
tai20_10_007
Não 881,75
5000
54
5,22
12,44
tai20_10_008
Não 2136,83
5000
36
5,23
18,63
tai20_10_009
Não 1189,92
5000
48
2,94
3,85
tai20_10_010
Não 1613,64
5000
42
5,78
16,96
tai20_20_001
Não 5473,77
5000
62
8,04
30,05
tai20_20_002
Não 5801,58
5000
55
8,1
33,27
tai20_20_003
Não 6021,11
5000
75
7,94
33,52
tai20_20_004
Não 4388,38
5000
57
7,95
32,61
tai20_20_005
Não 6827,8
5000
65
6,3
35,21
tai20_20_006
Não 5604,75
5000
54
7,44
30,84
tai20_20_007
Não 6030,27
5000
68
7,13
32,62
tai20_20_008
Não 4722,13
5000
51
8,66
25,05
tai20_20_009
Não 6201,66
5000
58
8,32
33,18
tai20_20_010
Não 5482,22
5000
55
7,32
30,73
tai50_5_001 Sim 0,59
0
0
0
0
tai50_5_002 Sim 25,34
8
5
0
0
tai50_5_003 Sim 112,39
54
15
0,89
1,86
tai50_5_004 Sim 79,72
60
19
0,22
1,04
tai50_5_005 Sim 1653,92
1211
70
0,05
0,21
tai50_5_006 Sim 48,31
24
16
0,2
0,33
tai50_5_007 Sim 54,05
13
7
3
4,38
tai50_5_008 Sim 0,61
0
0
0
0
tai50_5_009 Sim 137,72
98
28
0,47
3,5
tai50_5_010 Sim 0,53
0
0
0
0
Médias 37,85
3,25
10,92
Tabela 5: Resultados da execução da regra 1 com máximo de 5000 branches.
45
Nessa tabela observamos que o aumento do branch up reduziu-se um pouco, mas ainda
continua, em média, mais de três vezes maior que o aumento do branch down. Isso pode ser
devido ao fato de que, à medida que o algoritmo avança, somente as posições mais centrais do
escalonamento estão não-fixadas. Nessa situação parece que ocorre um menor aumento do
limite inferior da função objetivo por fixação.
4.3 BRANCH SOBRE CONJUNTOS DE VARIÁVEIS (SOS)
Com o objetivo de balancear a árvore de branch utilizaremos a técnica de special
ordered sets (SOS). Um SOS tipo 1, que é o tipo utilizado nesse trabalho, é um conjunto de
variáveis em que no máximo uma variável pode assumir um valor diferente de zero. A regra
utilizada consiste em, a cada nó da árvore de branch, fixar várias variáveis binárias ao invés
de somente uma. Essa regra, que chamaremos de regra 2, está ilustrada no algoritmo da figura
seguinte.
Figura 23: Algoritmo de branch utilizando SOS – regra 2.
46
A fixação de variáveis
0
left
L
ou
0
right
L
significa que estamos fixando todas as
variáveis da lista em zero.
O algoritmo tenta equilibrar o somatório dos valores das variáveis das duas listas e
distribui as variáveis com zeradas de forma a fazer com que as duas listas tenham o mesmo
tamanho.
Foram feitas algumas rodadas de execução para testar essa regra, com os resultados
mostrados na tabela seguinte.
Problema Resolvido
Tempo
N
úmero de
Iterações
Profundidade
máxima Média Left
Média Right
tai20_5_001 Sim 12,63
183
13
2,14
2,28
tai20_5_002 Não 9,22
500
28
0,25
0,11
tai20_5_003 Sim 5,28
115
24
0,56
1,4
tai20_5_004 Sim 3,38
73
26
1,34
2,32
tai20_5_005 Não 9,42
500
41
0,95
2,94
tai20_5_006 Sim 8,7
105
17
0,12
0,11
tai20_5_007 Sim 0,08
0
0
0
0
tai20_5_008 Sim 4,39
93
21
1,16
1,62
tai20_5_009 Não 14,58
500
40
0,33
0,39
tai20_5_010 Sim 2,89
25
13
2,24
8,89
tai20_10_001
Não 65,61
500
32
4,62
15,57
tai20_10_002
Não 87,22
500
41
4,34
13,27
tai20_10_003
Não 41,95
500
47
2,36
6,22
tai20_10_004
Não 59,88
500
40
2,38
4,91
tai20_10_005
Não 84,38
500
35
3,9
12,54
tai20_10_006
Não 79,27
500
36
3,83
12,17
tai20_10_007
Não 33,7
500
42
4,17
14,15
tai20_10_008
Não 83,39
500
36
6,77
24,46
tai20_10_009
Não 62,47
500
40
2,55
8,89
tai20_10_010
Não 73,41
500
41
6,01
23,07
tai20_20_001
Não 185,86
500
49
8,59
33,91
tai20_20_002
Não 223,23
500
39
9,62
41,09
tai20_20_003
Não 198,92
500
43
12,65
35,31
tai20_20_004
Não 120,58
500
44
10,64
35,17
tai20_20_005
Não 208,83
500
42
12,7
28,62
tai20_20_006
Não 178,5
500
44
11,83
33,95
tai20_20_007
Não 171,58
500
41
9,72
30,68
tai20_20_008
Não 188,16
500
43
9,26
48,61
tai20_20_009
Não 192,94
500
47
9,09
36,24
tai20_20_010
Não 214,75
500
36
10
34,65
Médias 34,7
5,14
17,12
Tabela 6: Resultados da execução da regra de branch 2 com máximo de 500 iterações.
47
Com a regra 2 não faz sentido chamar os branches de “up” e “down”, pois nenhuma
variável está sendo individualmente fixada em nenhum limite superior ou inferior. Estamos
chamando os branches, na regra 2, de branch esquerdo (left) e branch direito (right).
Percebemos uma pequena melhora nas médias left e right em relação às médias “down” e
“up” da regra 1. Porém, a árvore de branch continua desbalanceada, com o branch de maior
aumento médio (o branch right) mais que três vezes maior que o branch de menor aumento
médio (o branch left).
Resolvemos também esses problemas e os de 50 tarefas e 5 máquinas usando a regra 2
com limite de 5000 branches. Os resultados estão na tabela seguinte.
Problema Resolvido
Tempo
N
úmero
de
Itera
ções
Profundidade
m
áxima
M
édia
Left
M
édia
Right
tai20_10_001
Não 1383,93
5000
58
4,03
6,93
tai20_10_002
Não 3344,91
5000
41
4,21
9,35
tai20_10_003
Não 2039,75
5000
52
3,23
6,37
tai20_10_004
Não 1633,64
5000
52
1,77
3,61
tai20_10_005
Não 2137,03
5000
59
2,13
4,49
tai20_10_006
Não 2539,15
5000
44
2,67
4,16
tai20_10_007
Não 1274,04
5000
52
4,51
13,35
tai20_10_008
Não 3781,62
5000
39
5,71
17,98
tai20_10_009
Não 1891,21
5000
40
2,35
6,76
tai20_10_010
Não 3032,11
5000
44
5,86
16,82
tai20_20_001
Não 9577,3
5000
51
9,69
31,49
tai20_20_002
Não 9996,01
5000
50
10,59
32,91
tai20_20_003
Não 10293,84
5000
50
10,87
32,18
tai20_20_004
Não 6457,11
5000
53
9,45
30,74
tai20_20_005
Não 12136,18
5000
43
10,48
24,67
tai20_20_006
Não 3947,16
5000
50
10,11
30,81
tai20_20_007
Não 1740,47
5000
49
10,75
27,42
tai20_20_008
Não 1566,97
5000
51
8,08
35,34
tai20_20_009
Não 1951,23
5000
47
10,12
29,86
tai20_20_010
Não 1749,8
5000
46
8,58
30,28
tai20_5_001 Sim 11,77
183
13
2,14
2,28
tai20_5_002 Não 97,05
5000
30
0,3
0,12
tai20_5_003 Sim 4,97
115
24
0,56
1,4
tai20_5_004 Sim 3,16
73
26
1,34
2,32
tai20_5_005 Não 86,98
5000
42
1,26
2,8
tai20_5_006 Sim 8,22
105
17
0,12
0,11
tai20_5_007 Sim 0,08
0
0
0
0
tai20_5_008 Sim 4,13
93
21
1,16
1,62
tai20_5_009 Sim 36,66
1403
42
0,16
0,14
tai20_5_010 Sim 2,73
25
13
2,24
8,89
tai50_5_001 Sim 0,59
0
0
0
0
tai50_5_002 Sim 110,64
75
16
0,83
2,5
tai50_5_003 Sim 130,84
104
18
0,82
2,67
tai50_5_004 Sim 94,02
138
24
0,75
0,9
48
Problema Resolvido
Tempo
N
úmero
de
Itera
ções
Profundidade
m
áxima
M
édia
Left
M
édia
Right
tai50_5_005 Sim 1407
1517
36
0,13
0,13
tai50_5_006 Sim 45,75
47
17
0,35
0,09
tai50_5_007 Sim 95,72
42
16
1
2,36
tai50_5_008 Sim 0,63
0
0
0
0
tai50_5_009 Sim 131,5
165
30
0,75
1,51
tai50_5_010 Sim 0,53
0
0
0
0
Médias 33,90
3,73
10,63
Tabela 7: Resultados da execução da regra de branch 2 com máximo de 5000 iterações.
O algoritmo da regra 2 foi modificado para que, a cada branch, todas as variáveis
zeradas sejam fixadas no branch left, de forma a tentar equilibrar os branches. Essa nova
regra, chamada de regra 3 é mostrada no algoritmo da figura seguinte.
Figura 24: Algoritmo de branch utilizando SOS – regra 3
Os resultados da utilização dessa regra estão na tabela seguinte.
49
Problema Resolvido
Tempo
N
úmero de
Iterações
Profundidade
máxima Média Left
Média Right
tai20_5_001 Sim 8,64
119
15
2,46
1,56
tai20_5_002 Não 31,52
500
31
0,26
0,2
tai20_5_003 Sim 4,64
53
12
0,83
0,77
tai20_5_004 Sim 2,39
31
9
2,25
3,83
tai20_5_005 Não 11,86
500
29
1,87
1,64
tai20_5_006 Sim 3,98
60
14
0,03
0,1
tai20_5_007 Sim 0,08
0
0
0
0
tai20_5_008 Sim 3,67
74
20
1,71
0,82
tai20_5_009 Não 16,64
500
34
0,47
0,24
tai20_5_010 Sim 2,48
15
7
4,02
5,02
tai20_10_001
Não 82,64
500
21
11,03
8,08
tai20_10_002
Não 97,72
500
27
8,96
7,39
tai20_10_003
Não 53,36
500
28
3,85
5,15
tai20_10_004
Não 69,42
500
40
4,72
3,08
tai20_10_005
Não 90,86
500
24
7,8
7,4
tai20_10_006
Não 95,86
500
26
7,9
5,45
tai20_10_007
Não 37,77
500
37
8,93
9,05
tai20_10_008
Não 106,7
500
27
16,39
8,28
tai20_10_009
Não 68,13
500
32
5,08
6,45
tai20_10_010
Não 94,53
500
29
13,97
11,49
tai20_20_001
Não 190,63
500
41
19,33
14,44
tai20_20_002
Não 232,06
500
32
21,1
18,68
tai20_20_003
Não 223,63
500
51
22,77
15,95
tai20_20_004
Não 149,86
500
36
21,2
14,87
tai20_20_005
Não 260,61
500
36
22,05
15,76
tai20_20_006
Não 182,53
500
36
20,71
16,13
tai20_20_007
Não 190,13
500
41
20,47
14,73
tai20_20_008
Não 170,84
500
32
20,35
15,79
tai20_20_009
Não 215,7
500
47
24,15
12,92
tai20_20_010
Não 233,33
500
34
23,69
12,54
Médias 28,27
10,61
7,93
Tabela 8: Resultados da execução da regra de branch 3 com máximo de 500 iterações.
Podemos observar que, com essa regra, o branch ficou mais tendencioso para a
esquerda, embora isso não tenha feito a árvore ficar muito desbalanceada, ao contrário das
regras anteriores. A profundidade média caiu de 34,7 no branch 2 para 28,27 no branch 3, o
que também mostra um aumento de performance.
A tabela seguinte mostra os resultados da execução da regra 3 com essas mesmas
instâncias e das instâncias de 50 tarefas e 5 máquinas, com limite de 5000 branches.
50
Problema Resolvido
Tempo
N
úmero
de
Itera
ções
Profundidade
m
áxima
M
édia
Left
M
édia
Right
tai20_10_001
Não 1263,25
5000
66
5,35
4,74
tai20_10_002
Não 3743,02
5000
39
7,94
5,77
tai20_10_003
Não 2164,3
5000
41
4,78
4,71
tai20_10_004
Não 2051,08
5000
56
2,95
2,48
tai20_10_005
Não 2477,89
5000
48
3,11
2,91
tai20_10_006
Não 2785,58
5000
48
3,5
3,15
tai20_10_007
Não 1405,48
5000
44
8,76
8,41
tai20_10_008
Não 4325,88
5000
30
12,98
8,28
tai20_10_009
Não 2373,89
5000
41
3,24
3,66
tai20_10_010
Não 3327,63
5000
41
12,25
9,15
tai20_20_001
Não 9802,57
5000
51
19,18
14,41
tai20_20_002
Não 10590,25
5000
42
19,88
16,2
tai20_20_003
Não 11054,57
5000
55
21,53
16,47
tai20_20_004
Não 7281,33
5000
45
19,15
14,81
tai20_20_005
Não 13486,93
5000
46
20,59
12,74
tai20_20_006
Não 4363,42
5000
42
20,33
14,97
tai20_20_007
Não 1991,94
5000
45
20,32
15,34
tai20_20_008
Não 1615,16
5000
44
17,74
13,42
tai20_20_009
Não 2118,3
5000
47
21,28
14,41
tai20_20_010
Não 1812
5000
42
18,91
13,44
tai20_5_001 Sim 8,16
119
15
2,46
1,56
tai20_5_002 Não 200,48
5000
51
0,25
0,23
tai20_5_003 Sim 4,38
53
12
0,83
0,77
tai20_5_004 Sim 2,27
31
9
2,25
3,83
tai20_5_005 Não 100,73
5000
35
2,43
1,87
tai20_5_006 Sim 3,78
60
14
0,03
0,1
tai20_5_007 Sim 0,08
0
0
0
0
tai20_5_008 Sim 3,5
74
20
1,71
0,82
tai20_5_009 Sim 31,16
1169
34
0,24
0,1
tai20_5_010 Sim 2,31
15
7
4,02
5,02
tai50_5_001 Sim 0,59
0
0
0
0
tai50_5_002 Sim 63,14
22
13
0,05
0,81
tai50_5_003 Sim 90,3
57
15
1,29
1,14
tai50_5_004 Sim 64,97
57
16
0,91
0,64
tai50_5_005 Sim 1452,03
1131
53
0,16
0,06
tai50_5_006 Sim 43,41
25
12
0,24
0,27
tai50_5_007 Sim 50,56
19
7
4,13
2,05
tai50_5_008 Sim 0,63
0
0
0
0
tai50_5_009 Sim 113,91
96
19
2,63
0,57
tai50_5_010 Sim 0,52
0
0
0
0
Médias 31,13
7,19
5,48
Tabela 9: Resultados da execução da regra de branch 3 com máximo de 5000 iterações.
A pr
óxima tentativa de balancear a árvore é, a cada branch, fixar todas as variáveis
zeradas no lado do branch que tenha o menor somatório dos valores das variáveis não-zeradas
51
fixadas naquele branch. Essa regra será chamada de regra 4 e está mostrada no algoritmo da
figura seguinte.
Figura 25: Algoritmo de branch utilizando SOS – regra 4.
Com esse algoritmo houve um considerável balanceamento entre a média de aumento
dos branches left e a média de aumento dos branches right, como demonstraram os
experimentos práticos mostrados na tabela seguinte.
Problema Resolvido
Tempo
N
úmero de
Iterações
Profundidade
máxima Média Left
Média Right
tai20_5_001 Sim 9,13
146
17
1,99
2,09
tai20_5_002 Não 12,22
500
29
0,3
0,17
tai20_5_003 Sim 4,23
54
12
0,84
1,01
tai20_5_004 Sim 2,47
30
9
2,25
4,15
tai20_5_005 Não 9,3
500
31
1,52
2
tai20_5_006 Sim 6,36
66
16
0,11
0,06
52
Problema Resolvido
Tempo
N
úmero de
Iterações
Profundidade
máxima Média Left
Média Right
tai20_5_007 Sim 0,06
0
0
0
0
tai20_5_008 Sim 3,55
66
18
1,3
1,34
tai20_5_009 Não 16,11
500
35
0,39
0,27
tai20_5_010 Sim 2,27
14
7
4,02
5,93
tai20_10_001
Não 71,66
500
25
8,17
10
tai20_10_002
Não 90,61
500
27
8,67
9,89
tai20_10_003
Não 51,88
500
37
3,49
5,12
tai20_10_004
Não 68,56
500
27
3,62
4,19
tai20_10_005
Não 89,44
500
25
6,81
8,49
tai20_10_006
Não 90,23
500
22
5,86
7,5
tai20_10_007
Não 38,06
500
40
6,62
10,93
tai20_10_008
Não 103,45
500
27
12,4
13,13
tai20_10_009
Não 61,52
500
26
3,99
7,55
tai20_10_010
Não 88,47
500
26
11,28
15,55
tai20_20_001
Não 190,94
500
44
16,2
15,73
tai20_20_002
Não 213,83
500
32
17,98
25,65
tai20_20_003
Não 250,64
500
48
20,09
18,38
tai20_20_004
Não 130,14
500
39
17,76
19,65
tai20_20_005
Não 241,06
500
41
18,27
17,73
tai20_20_006
Não 204,42
500
34
17,63
19,33
tai20_20_007
Não 193,28
500
40
15,08
19,28
tai20_20_008
Não 172,22
500
34
17,16
19,24
tai20_20_009
Não 205,05
500
40
18,5
18,91
tai20_20_010
Não 210,13
500
30
18,49
15,82
Médias 27,93
8,69
9,97
Tabela 10 - Resultados da execução da regra de branch 4 com máximo de 500 iterações.
O balanceamento conseguido com a regra 4 foi o melhor de todas as regras de branch
utilizadas nesse trabalho e proporcionou também a menor profundidade média da árvore de
branch. Executamos também rodadas de número máximo de 5000 iterações com a regra 4,
com essas mesmas instâncias e as 50 X 5. Os resultados dessas rodadas estão na tabela
seguinte.
Problema Resolvido
Tempo
N
úmero de
Iterações
Profundidade
máxima Média Left
Média Right
tai20_5_001 Sim 34,11
146
17
1,99
2,09
tai20_5_002 Não 412,04
5000
46
0,23
0,09
tai20_5_003 Sim 15,44
54
12
0,84
1,01
tai20_5_004 Sim 9,67
30
9
2,25
4,15
tai20_5_005 Não 377,54
5000
38
1,93
2,39
tai20_5_006 Sim 23,19
66
16
0,11
0,06
tai20_5_007 Sim 0,22
0
0
0
0
tai20_5_008 Sim 13,69
66
18
1,3
1,34
53
Problema Resolvido
Tempo
N
úmero de
Iterações
Profundidade
máxima Média Left
Média Right
tai20_5_009 Sim 122,55
1198
35
0,19
0,12
tai20_5_010 Sim 8,81
14
7
4,02
5,93
tai20_10_001
Não 1733,82
5000
55
4,98
5,33
tai20_10_002
Não 3990,59
5000
41
6,4
7,09
tai20_10_003
Não 2044,05
5000
41
3,93
5,51
tai20_10_004
Não 1715,68
5000
57
2,55
2,85
tai20_10_005
Não 2488,03
5000
51
2,78
3,43
tai20_10_006
Não 2741,78
5000
50
3,03
3,83
tai20_10_007
Não 1443,6
5000
45
6,83
10,38
tai20_10_008
Não 4098,65
5000
31
10,41
10,91
tai20_10_009
Não 2422,05
5000
37
2,93
4,47
tai20_10_010
Não 3317,7
5000
39
9,47
12,1
tai20_20_001
Não 8967,45
5000
48
14,84
19,65
tai20_20_002
Não 10132,73
5000
39
16,77
20,65
tai20_20_003
Não 10621,43
5000
48
17,06
18,29
tai20_20_004
Não 7087,19
5000
43
15,88
19,27
tai20_20_005
Não 13030,8
5000
45
15,44
17,01
tai20_20_006
Não 10574,48
5000
40
16,38
19,28
tai20_20_007
Não 10630,32
5000
45
15,7
18,3
tai20_20_008
Não 9485,29
5000
44
14,14
18,46
tai20_20_009
Não 11998,83
5000
40
16,66
18,93
tai20_20_010
Não 10108,32
5000
35
15,34
16,11
tai50_5_001 Sim 2,31
0
0
0
0
tai50_5_002 Sim 169,52
11
6
0
0,39
tai50_5_003 Sim 508,26
62
14
1,36
1,61
tai50_5_004 Sim 400,35
59
18
0,7
0,51
tai50_5_005 Sim 7018,07
1109
45
0,1
0,08
tai50_5_006 Sim 247,38
23
12
0,28
0,27
tai50_5_007 Sim 268,41
17
8
3,79
3,47
tai50_5_008 Sim 2,36
0
0
0
0
tai50_5_009 Sim 542,81
86
18
2,06
0,76
tai50_5_010 Sim 1,89
0
0
0
0
Médias 29,83
5,82
6,90
Tabela 11 - Resultados da execução da regra de branch 4 com máximo de 5000 iterações.
As médias de aumento left e right parecem ter diminuído porque com o andamento do
algoritmo, menos branches são feitos nos extremos do escalonamento (pois essas posições já
estão fixadas). Esses branches nos extremos tendem a ser mais efetivos. Observamos que,
mesmo rodando com limite de 5000 iterações, a profundidade máxima da árvore não
aumentou muito.
5 FORMULAÇÃO DE FLUXOS
Uma tentativa de melhorar a formulação de Wilson é acrescentar restrições que
definam os intervalos entre o início e o fim das tarefas adjacentes em máquinas adjacentes.
Esses intervalos serão representados pelas variáveis “tt”, conforme a figura seguinte, que
mostra um trecho de um escalonamento.
Figura 26
– restrições de intervalo.
A variável
k
i
tt
deve ser interpretada como “intervalo de tempo depois do fim da k-
ésima tarefa na máquina i depois do qual a máquina i+1 fica disponível para a (k+1)-ésima
tarefa”.
Para modelar todas as possibilidades de seq
üência entre as tarefas tomadas duas a
duas, introduziremos variáveis binárias x com o seguinte significado:
55
É importante notar a diferença entre essas variáveis x e as variáveis x definidas
anteriormente na formulação de Wilson. As variáveis x da formulação de Wilson têm dois
índices: k e j. Essas variáveis definidas agora têm três índices: k, j e l. Existe uma relação
entre os dois conjuntos de variáveis, que é:
njnkxx
n
l
k
lj
k
j
,...,1,..1
1
,
Agora podemos definir as variáveis tt da seguinte forma:
1,...,11,...,1),max(
1 1
.,1,
nkmixpptt
n
j
n
l
k
ljjili
k
i
Assim, temos uma formulação que é garantidamente mais forte que a de Wilson:
minktsc
minkxpt
nkx
njx
asujeito
c
k
i
k
i
k
i
n
j
k
jji
k
i
n
j
k
j
n
k
k
j
n
m
,...,1,...,13
,...,1,...,12
,..,11
,...,11
1
:
min
1
,
1
1
nlnjnkmiZttxtcsx
nkmisttc
nkmixpptt
njnkxx
s
minkcs
minkcs
k
i
k
lj
k
i
k
i
k
i
k
j
k
i
k
i
k
i
n
j
n
l
k
ljjili
k
i
n
l
k
lj
k
j
k
i
k
i
k
i
k
i
,...,1,...,1,...,1,...,1,,,,,
1,...,11,...,1)9(
1,...,11,...,1),max()8(
,...,1,..1)7(
06
,...,2,...,15
,...,1,...,24
,
1
1
1 1
.,1,
1
,
1
1
1
1
56
Essa nova formulação tem todas as restrições da formulação de Wilson e, portanto,
nenhuma relação linear conseguida com a nova formulação pode ser pior do que uma
relaxação linear conseguida com a formulação de Wilson. E para provar que a nova
formulação é mais forte que a de Wilson utilizaremos o exemplo anterior:
13
13
A relaxação linear dessa instância na nova formulação gera o valor 7 para a função
objetivo, que é exatamente o valor da função objetivo da solução ótima. Portanto, isso prova
que a nova formulação é mais forte que a formulação de Wilson.
Uma tentativa de criar uma formulação ainda mais forte do que esta última é adicionar
restrições de conservação de fluxo. Para entendermos essas restrições precisamos criar um
grafo, como o mostrado na figura seguinte.
Figura 27: Conservação de fluxo.
No grafo acima, cada arco que n
ão entra ou sai do nó fictício é associado a uma das
variáveis
k
lj
x
,
. Uma solução para o problema do permutation flow shop corresponde a um
caminho nesse grafo. Para acrescentar as novas restrições é necessário definir algumas
57
variáveis que representam os fluxos que entram e os fluxos que saem do nó fictício.
Adotaremos a convenção de chamar as variáveis correspondentes aos arcos que saem do nó
fictício para os nós da primeira posição de
nlx
l
,...,1,
0
,0
e os correspondentes aos arcos
que saem dos nós da n-ésima posição e entram no nó fictício de
njx
n
j
,...,1,
0,
. Dessa
forma, o nó fictício fica, conceitualmente, alocado na posição zero. Com essas novas variáveis
podemos escrever a nova formulação:
minktsc
minkxpt
nkx
njx
asujeito
c
k
i
k
i
k
i
n
j
k
jji
k
i
n
j
k
j
n
k
k
j
n
m
,...,1,...,13
,...,1,...,12
,..,11
,...,11
1
:
min
1
,
1
1
1,...,11,...,1)9(
1,...,11,...,1),max()8(
,...,1,..1)7(
06
,...,2,...,15
,...,1,...,24
1
1
1 1
.,1,
1
,
1
1
1
1
nkmisttc
nkmixpptt
njnkxx
s
minkcs
minkcs
k
i
k
i
k
i
n
j
n
l
k
ljjili
k
i
n
l
k
lj
k
j
k
i
k
i
k
i
k
i
nlxx
x
xx
nknjxx
nlxx
njxx
l
n
k
n
j
k
lj
n
l
n
l
n
l
n
l
n
j
j
n
l
k
lj
n
l
k
jl
n
j
n
lj
n
l
n
l
ljj
,...,11)15(
1)14(
)13(
1,...,2,...,1)12(
,...,1)11(
,...,1)10(
0
,0
2 1
,
1
0,
1
0,
1
0
,0
1
,
1
1
,
1
1
,0,
1
1
,
0
,0
58
nlnjnkZx
njminkZtttcsx
k
lj
k
i
k
i
k
i
k
i
k
j
,...,0,...,0,...,0
,...,1,...,1,...,1,,,,
,
As restrições (10) garantem que um fluxo que sai do nó fictício para um nó na
primeira posição e somatório dos fluxos que saem desse mesmo nó vale o mesmo, como
ilustra a figura seguinte.
Figura 28: Conservação de fluxo na primeira posição.
As restrições (11) definem que o somatório dos fluxos que entram em um nó da última
posição é igual ao fluxo que sai desse mesmo nó e entra no nó fictício, como mostra a figura
seguinte.
59
Figura 29: Conservação de fluxo na última posição.
As restrições (12) igualam o somatório dos fluxos que entram em um nó nas posições
de 2 a n-1 e o somatório dos fluxos que saem desse mesmo nó, de acordo com a ilustração
seguinte.
Figura 30: Conservação de fluxo em um nó na posição de 2 a n-1.
60
As restrições (13) fazem o balanceamento dos fluxos que entram e saem do nó fictício
e as restrições (14) igualam o somatório dos fluxos que entram no nó fictício a 1, forçando o
fluxo a existir no grafo. A figura seguinte ilustra esses fluxos.
Figura 31: Conservação de fluxo no nó fictício.
As restrições (15) forçam a que cada tarefa participe exatamente uma vez do caminho
a ser percorrido no grafo. Ela diz que o somatório de todos os fluxos que entram nos nós que
correspondem a uma tarefa, em todas as posições, é igual a 1.
Essa formulação será chamada de formulação de fluxos.
Para fazer uma comparação entre as formulações de Wilson e a de fluxos, resolvemos
a relaxação linear dos problemas de Taillard de 20 e de 50 tarefas. A tabela seguinte mostra os
resultados da resolução da relaxação linear dos problemas usando as diferentes formulações:
Problema Wilson Fluxos LB UB
Tempo
Wilson
Tempo
Fluxos
Gap Wilson
(%)
Gap Fluxos
(%)
tai20_5_001 1248,63
1257,26
1278
1278
0,03
1,09
2,30
1,62
tai20_5_002 1326,38
1333,94
1359
1359
0,03
0,81
2,40
1,84
tai20_5_003 1073
1073
1081
1081
0,03
0,92
0,74
0,74
tai20_5_004 1268
1268,37
1293
1293
0,03
1,06
1,93
1,90
tai20_5_005 1203,4
1206,56
1235
1235
0,03
0,91
2,56
2,30
tai20_5_006 1181,87
1185,43
1195
1195
0,03
0,91
1,10
0,80
tai20_5_007 1234
1234
1234
1234
0,02
0,61
0,00
0,00
tai20_5_008 1178,48
1183,85
1206
1206
0,03
1,09
2,28
1,84
tai20_5_009 1208,11
1211,31
1230
1230
0,03
1
1,78
1,52
tai20_5_010 1083,95
1088,07
1108
1108
0,03
0,8
2,17
1,80
tai20_10_001
1477,81
1491,84
1582
1582
0,13
1,22
6,59
5,70
61
Problema Wilson Fluxos LB UB
Tempo
Wilson
Tempo
Fluxos
Gap Wilson
(%)
Gap Fluxos
(%)
tai20_10_002
1544,27
1567,87
1659
1659
0,09
1,22
6,92
5,49
tai20_10_003
1423,76
1423,76
1496
1496
0,08
2,14
4,83
4,83
tai20_10_004
1318,97
1323,15
1377
1377
0,08
1,89
4,21
3,91
tai20_10_005
1330,71
1341,44
1419
1419
0,08
1,33
6,22
5,47
tai20_10_006
1314,75
1321,6
1397
1397
0,09
1,5
5,89
5,40
tai20_10_007
1389,76
1391,19
1484
1484
0,08
1,53
6,35
6,25
tai20_10_008
1384,85
1425,36
1538
1538
0,08
1,17
9,96
7,32
tai20_10_009
1513,13
1531,74
1593
1593
0,09
1,11
5,01
3,85
tai20_10_010
1446,59
1475,72
1591
1591
0,09
1,06
9,08
7,25
tai20_20_001
1984,07
2046,67
2297
2297
0,27
2,14
13,62
10,90
tai20_20_002
1802,39
1866,01
2099
2099
0,23
2,44
14,13
11,10
tai20_20_003
1939,29
2046,56
2326
2326
0,25
2,31
16,63
12,01
tai20_20_004
1922,67
1973,69
2223
2223
0,25
2,22
13,51
11,22
tai20_20_005
2028,76
2078,09
2291
2291
0,25
2,75
11,45
9,29
tai20_20_006
1929,56
1982,33
2226
2226
0,28
2,58
13,32
10,95
tai20_20_007
1990,37
2050,63
2273
2273
0,25
2,72
12,43
9,78
tai20_20_008
1930,05
1972,13
2200
2200
0,27
2,22
12,27
10,36
tai20_20_009
1914,94
1996,1
2237
2237
0,25
2,45
14,40
10,77
tai20_20_010
1928,45
1955,44
2178
2178
0,3
2,5
11,46
10,22
tai50_5_001 2720,24
2720,24
2724
2724
0,23
36,39
0,14
0,14
tai50_5_002 2808,05
2814,28
2834
2834
0,28
42,03
0,92
0,70
tai50_5_003 2603,54
2606,55
2621
2621
0,27
37,69
0,67
0,55
tai50_5_004 2740
2740,19
2751
2751
0,27
45,38
0,40
0,39
tai50_5_005 2847,81
2848,29
2863
2863
0,23
40,36
0,53
0,51
tai50_5_006 2805,39
2810,94
2829
2829
0,28
37,19
0,83
0,64
tai50_5_007 2692,47
2694,66
2725
2725
0,25
39,41
1,19
1,11
tai50_5_008 2671,93
2672,18
2683
2683
0,22
34,2
0,41
0,40
tai50_5_009 2530,64
2531,55
2552
2552
0,25
39,06
0,84
0,80
tai50_5_010 2777,05
2777,3
2782
2782
0,23
35,94
0,18
0,17
tai50_10_001
2939,04
2945,9
2991
2991
0,73
79,41
1,74
1,51
tai50_10_002
2825,01
2826,07
2867
2867
1,22
196,08
1,46
1,43
tai50_10_003
2803,63
2806,67
2839
2839
0,72
74,55
1,25
1,14
tai50_10_004
3004,84
3014,44
3063
3063
0,89
73,83
1,90
1,59
tai50_10_005
2911,75
2914,66
2976
2976
1,03
75,91
2,16
2,06
tai50_10_006
2952,15
2958,13
3006
3006
0,69
80,08
1,79
1,59
tai50_10_007
3062,2
3062,74
3093
3093
0,77
79,02
1,00
0,98
tai50_10_008
2976,25
2986,79
3037
3037
0,78
76,83
2,00
1,65
tai50_10_009
2807,83
2827,15
2897
2897
0,88
114,36
3,08
2,41
tai50_10_010
3046
3046
3065
3065
0,69
78,42
0,62
0,62
tai50_20_001
3556,53
3590
3771
3850
2,45
52,53
7,62
6,75
tai50_20_002
3479,36
3494,76
3668
3704
2,72
69,31
6,06
5,65
tai50_20_003
3379,02
3404,2
3591
3640
2,56
58,2
7,17
6,48
tai50_20_004
3394,9
3437,18
3635
3720
2,05
46,92
8,74
7,60
tai50_20_005
3345,84
3363,42
3553
3610
2,88
60,05
7,32
6,83
tai50_20_006
3497,66
3509,85
3667
3681
2,47
69,84
4,98
4,65
tai50_20_007
3456,53
3478,52
3672
3704
2,72
63,63
6,68
6,09
tai50_20_008
3417,17
3432,76
3627
3691
2,84
62,69
7,42
7,00
tai50_20_009
3457,66
3466,41
3645
3743
2,19
63,17
7,62
7,39
tai50_20_010
3517,77
3535,03
3696
3756
2,77
63,94
6,34
5,88
Tabela 12 – comparação entre as formulações de Wilson e a de fluxos.
62
Nessa tabela as colunas têm o seguinte significado:
Problema: Nome da instância do problema.
Wilson: Valor da solução ótima da relaxação da formulação de Wilson.
Fluxos: Valor da solução ótima da relaxação da formulação de fluxos.
LB: limite inferior (lower bound) conhecido do problema.
UB: limite superior (upper bound) conhecido do problema.
Tempo Wilson: Tempo, em segundos, da resolução da relaxação da formulação de
Wilson.
Tempo Fluxos: Tempo, em segundos, da resolução da relaxação da formulação de
fluxos.
Gap Wilson (%): Intervalo (gap) entre o valor ótimo da relaxação de Wilson e o
limite superior conhecido, em percentual.
Gap Fluxos (%): Intervalo (gap) entre o valor ótimo da relaxação de fluxos e o
limite superior conhecido, em percentual.
Analisando os resultados verificamos que a relaxação de fluxos fornece um gap menor
que a formulação de Wilson. Apesar dessa melhora dos gaps das relaxações lineares, não foi
possível encontrar a solução inteira de nenhum dos problemas de Taillard utilizando a
formulação de fluxos.
6 CONCLUSÃO
O primeiro objetivo desta dissertação foi propor e avaliar regras de branch sobre a
formulação de Wilson. De fato, foi mostrado que com as regras de branch realmente possuem
um grande potencial para alterar o desempenho de um algoritmo de branch-and-bound sobre
essa formulação. A tabela abaixo sumariza os resultados com cada uma das regras de branch
testadas (rodadas de 5000 branches no máximo).
Técnica Profundidade
máxima
Média de aumento
do pior lado
Média de aumento
do melhor lado
Default CPLEX
124,38
0,92
6,69
Regra 1 (branch em
uma variável)
37,85
3,25
10,92
Regra 2 (SOS)
33,9
3,73
10,63
Regra 3 (SOS)
31,13
5,48
7,19
Regra 4 (SOS)
29,83
5,82
6,9
Tabela 13: Comparação sumarizada entre as regras de branch.
Embora a resolução exata de vários dos problemas de Taillard ainda não tenha sido
conseguida, demonstramos claramente a importância do uso de uma regra de branch com
conhecimento das características específicas do problema do permutation flow shop.
O segundo objetivo foi propor e estudar uma nova formulação para o Permutation
Flowshop. Os limites obtidos com a nova formulação de fluxo proposta se mostraram
consistentemente melhores do que os obtidos com a formulação de Wilson. Entretanto, o
elevado tempo computacional exigido para resolver sua relaxação linear faz com que ela
ainda seja pouco prática para ser aplicada diretamente em um algoritmo de branch-and-bound
como o do CPLEX, conforme mostrado na tabela a seguir.
64
Formulação Tempo médio (s) Gap médio %
Wilson 0,67 5,14
Fluxos 32,9 4,35
Tabela 14 – comparação sumarizada entre a formulação de Wilson e a de fluxos.
De qualquer forma, não conhecemos nenhuma outra formulação compacta para esse
problema (com um número polinomial de variáveis e restrições) que forneça melhores limites
inferiores.
7 REFERÊNCIAS
AGARWAL, A.; COLAK, S.; ERYARSOY, E. Improvement heuristic for the flow-shop
scheduling problem: An adaptive-learning approach. European Journal of Operational
Research, 2006, 169; 3: 801-815.
ASHOUR, S. An experimental investigation and comparative evaluation of flow-shop
scheduling techniques. Operations Research, 18 3, 1970, 541–549.
BROWN, A. P. G.; LOMNICKI, Z. A. Some applications of the branch and bound algorithm
to the machine scheduling problem. Operational Research Quarterly, 17, 1966, 173–180.
CAMPBELL, H. G.; DUDEK, R. A.; SMITH, M. L. A heuristic algorithm for the n-job, m-
machine scheduling problem. Management Science, 16, 1970: 630–637.
CARLIER, J.; REBAÏ, I. Two branch and bound algorithms for the permutation flow shop
scheduling problem. European Journal of Operational Research, 90, 1996, 238–251.
DANNENBRING, D. G. An evaluation of flow shop sequencing heuristics. Management
Science, 23(11):1174-1182, 1977.
GRABOWSKI, J. On two-machine scheduling with release and due dates to minimize
maximum lateness. Opsearch, 1980;17:133-54.
GRAHAM, R. L. et al. Optimization and approximation in deterministic sequencing and
scheduling: a survey, Ann. Discrete Math. 4, 1979, 287-326.
GUPTA J. N. D. A Functional Heuristic Algorithm for the Flowshop Scheduling Problem.
Operational Research Quarterly, (1970-1977), Vol. 22, No. 1, 1971, 39-47.
HELD, M.; KARP, R. M. A dynamic programming approach to sequencing problems.
Journal of the Society for Industrial and Applied Mathematics,10, 1962, 196–210.
66
IGNALL, E.; SCHRAGE, L. E. Application of the branch-and-bound technique to some
flowshop problems. Oper. Res. 13, 1965, 400–412, MathSciNet.
JOHNSON, S. M. Optimal two- and three-stage Production Schedules with set-up times
included. Naval Research Logistics Quartely, 1, 61-68, 1954.
KNUTH, D. E. The Art of Computer Programming. 2. ed., v3. Addison-Wesley Professional,
1973.
LADHARI, T.; HAOUARI, M. A computational study of the permutation flow shop problem
based on a tight lower bound. Computers and Operations Research, 2005, v.32 n.7, 1831-
1847.
LAGEWEG, B. J. et al. A general bounding scheme for the permutation flow-shop problem.
Operations Research, 26, 1978, 53–67.
______. Computer-aided complexity classification of deterministic scheduling problems.
Report BW 138, Mathematisch Centrum, Amsterdam, 1981.
LOMNICKI, L. A branch and bound algorithm for the exact solution of the three-machine
scheduling problem. Operational Research Quarterly, 16, 1965.
McMAHON, G. B.; BURTON, P. G. Flow-shop scheduling with the branch-and-bound
method. Operations Research,15, n. 3, 1967, 473–481.
PALMER, D. S. Sequencing jobs through a multi-stage process in the minimum total time—a
quick method of obtaining a near optimum. Operational Research Quarterly, 16, 1965, 101–
107.
PINEDO, M. Scheduling: Theory, Algorithms, and Systems. Second edition, Prentice-Hall,
New Jersey, 2002.
POTTS, C. N. An adaptive branching rule for the permutation flow-shop problem. European
Journal of Operational Research, 1980;5:19-25.
RÖCK, H.; SCHMIDT, G. Machine aggregation heuristics in shop scheduling. Methods of
Operations Research, 45, 1982, 303–314.
RUIZ, R.; MAROTO, C. A comprehensive review and evaluation of permutation flowshop
heuristics. European Journal of Operational Research, 165, 2005.
TAILLARD,
É. D. Benchmarks for basic scheduling problems. European Journal of
Operational Research, 64, 1993, 278 285.
67
TSENG, F. T.; STAFFORD Jr, E. F.; GUPTA, J. N. D. Comparative evaluation of MILP
flowshop models. Journal of the Operational Research Society, 2005; 56, 88–101.
WAGNER, H. M. An integer linear-programming model for machine scheduling. Naval
Research Logistics Quarterly, 1959, 199;6:131-40.
WILSON, J. M. Alternative formulations of a flow-shop scheduling problem. Journal of the
Operational Research Society, 1989;40:395-9.
WOLSEY, L. A. Integer Programming. New York, 1998.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
