Vedlegg til CIV

Alguns estudos abordam o problema de sequenciamento de lotes em uma m´aquina

com capacidade ilimitada, como ´e o caso de Cheng et al (2001). Os autores considera-

ram datas de libera¸c˜ao e datas de vencimento das tarefas, provando que mesmo quando

s˜ao considerados tempos de processamento e datas de vencimento proporcionais (ou seja,

p

≤ · · · ≤ p

e ¯d

≤ · · · ≤ ¯d

), o problema ´e tido como

N P-dif´ıcil. Al´em disso, desen-

Tabela 3.2: Resumo dos trabalhos com compt, Q < n, s

distintos,

∀j ∈ J

Fun¸c˜ao Objetivo

arja

apja ap(Bi)a Config.

Outras caracter´ısticas (min) cte cte aOffa aOna

Uzsoy (1994) PCjouPCmax x

Ghazvini e Dupont (1998) PCj x Azizoglu e Webster (2000) PwjCj x

Zhang et al (2001b) Cmax x

Dupont e Dhaenens-Flipo (2002) Cmax x

Melouk et al (2004) Cmax x

Chang e Wang (2004) PCj x x

Li et al (2005) Cmax x

Chou et al (2005) Cmax x

Gupta e Sivakumar (2006) (PTj)/n, TmaxouPUj x

Kashan et al (2006) Cmax x

Damodaran et al (2006) Cmax x

Erramilli e Mason (2006) PwjTj x Agrupamento de pedidos

Wang et al (2007) Cmax x x

Damodaran et al (2007) Cmax x Q limitada pelo # de tarefas. Chou e Wang (2008) PwjTj x x

Parsa et al (2010) Cmax x

Kashan et al (2010) Cmaxe Tmax x Mathirajan et al (2010) PwjTj x x Chen et al (2011) Cmax x Wang (2011) PwjTj x x Xu et al (2012) Cmax x x Li et al (2015) P|Cj− dj| x dj= cte Christ (2015) PwjTj x x

de libera¸c˜ao s˜ao proporcionais `as de vencimento; quando as datas de libera¸c˜ao s˜ao pro-

porcionais aos tempos de processamento; e para quando ´e conhecido o n´umero de datas

de libera¸c˜ao distintas, de distintos tempos de processamento ou de distintas datas de

vencimento. Segundo relatado, os algoritmos podem ser adaptados para o problema de

minimiza¸c˜ao do tempo de t´ermino m´aximo multiplicado por uma fun¸c˜ao n˜ao decrescente

referente aos tempos de t´ermino.

Liu et al (2003) provaram que o problema de minimiza¸c˜ao do atraso total que con-

siderada uma m´aquina sem limita¸c˜ao de capacidade ´e_{N P-dif´ıcil. Desenvolveram tamb´em}

um algoritmo pseudo-polinomial para o problema que possui como objetivo uma fun¸c˜ao

regular e considera datas de libera¸c˜ao das tarefas diferentes de zero. Poon e Yu (2005)

propuseram uma heur´ıstica para o problema de sequenciamento online de lotes com uma

m´aquina de capacidade ilimitada, considerando datas de libera¸c˜ao e com o objetivo de

minimizar o makespan. Um segundo algoritmo foi tamb´em proposto a partir da uni˜ao do

primeiro algoritmo desenvolvido com m´etodos apresentados por Deng et al (1999) e Zhang

et al (2001a), em conjunto com a adi¸c˜ao de um parˆametro ajust´avel, que torna o algoritmo

flex´ıvel.

He et al (2007) consideraram o problema multiobjetivo, visando minimizar con-

comitantemente o m´aximo lateness e o makespan. Os autores apresentaram um algo-

ritmo de tempo polinomial baseado em PD para achar as solu¸c˜oes Pareto-´otimas. Em

Ridouard et al (2008) foram propostos trˆes algoritmos online com o objetivo de minimizar

o makespan, considerando datas de libera¸c˜ao. Os autores mostraram que dois desses algo-

ritmos fornecem as melhores solu¸c˜oes poss´ıveis para casos especiais do problema.

Al´em de considerar datas de libera¸c˜ao das tarefas, Lu et al (2008) incorporaram

ao problema a possibilidade de rejei¸c˜ao. A fun¸c˜ao objetivo tratada foi a minimiza¸c˜ao do

somat´orio do makespan das tarefas aceitas para processamento e do total de penalidades

das tarefas n˜ao processadas. Os autores propuseram um algoritmo de tempo pseudo-

polinomial baseado em PD, e provaram se tratar de um problema tido como

N P-dif´ıcil.

Quando a penalidade em caso de rejei¸c˜ao ´e igual para todas as tarefas, o algoritmo pro-

posto ´e executado em tempo polinomial. Al´em disso, um algoritmo de aproxima¸c˜ao e um

esquema de aproxima¸c˜ao de tempo polinomial foram propostos para o problema.

Yuan et al (2011) estudaram o problema de minimiza¸c˜ao do makespan com datas

de libera¸c˜ao e em uma configura¸c˜ao semi-online. A configura¸c˜ao chamada pelos autores

de semi-online, se refere ao fato de que, no instante de tempo t, s˜ao conhecidas as infor-

ma¸c˜oes sobre a pr´oxima tarefa que chegar´a no sistema de maior tempo de processamento,

chamada J

∗

_{. Algoritmos online foram propostos para os seguintes casos: quando o tempo}

de processamento de J

∗

_{´e conhecido e s˜ao gerados no m´aximo 2 lotes; quando a data de}

libera¸c˜ao de J

∗

_{´e conhecida, gerando no m´aximo 3 lotes; e quando a data de libera¸c˜ao de}

J

∗

_{´e conhecida e com a restri¸c˜ao de que um algoritmo online gera no m´aximo 2 lotes.}

No problema estudado em Bellanger et al (2012), o objetivo adotado foi a minimi-

za¸c˜ao de uma fun¸c˜ao objetivo regular, ou seja, uma fun¸c˜ao n˜ao decrescente. No problema

abordado, as tarefas possuem intervalos de tempos de processamento e devem ser proces-

sadas em lotes, necessitando para tanto que os intervalos de tempo de processamento das

tarefas pertencentes ao mesmo lote possuam uma interse¸c˜ao n˜ao-vazia. Foram identifi-

cadas propriedades de solu¸c˜oes ´otimas, com base nas quais foi desenvolvido um algoritmo

enumerativo. Para fun¸c˜oes objetivo espec´ıficas, foram apresentados(as): um algoritmo de

PD, para a minimiza¸c˜ao do tempo total de t´ermino; uma prova de que ´e poss´ıvel resolver o

problema de minimiza¸c˜ao do makespan em tempo O(nlogn); uma prova de que o problema

de minimiza¸c˜ao do m´aximo lateness ´e tido como

_{N P-dif´ıcil.}

Na Tabela 3.3 est˜ao expostos os problemas estudados nos trabalhos descritos anteri-

ormente, nesta e nas Subse¸c˜oes 3.1.1 e 3.1.2, os quais consideram a capacidade da m´aquina

ilimitada.

Tabela 3.3: Resumo dos trabalhos com compt e Q_{≥ n}

Fun¸c˜ao Objetivo

arja

apja ap(Bi)a Config.

Outras caracter´ısticas (min) cte cte aOffa aOna

Brucker et al (1998) Pfj(Cj) x d¯j

x x d¯j, p1≤ · · · ≤ pne ¯d1≤ · · · ≤ ¯dn x x d¯j, r1≤ · · · ≤ rne ¯d1≤ · · · ≤ ¯dn x x d¯j, r1≤ · · · ≤ rne p1≤ · · · ≤ pn Cheng et al (2001) max fj(Cj) *

x x d¯j, #rj= cte, #pj= cte ou # ¯dj= cte Zhang et al (2001a) Cmax x x

Tj x

Liu et al (2003)

max fj(Cj) ouPfj(Cj) x x Poon e Zhang (2004) Cmax x x

Poon e Yu (2005) Cmax x x

He et al (2007) LmaxeCmax x Ridouard et al (2008) Cmax x x

Lu et al (2008) Cmax+PJj∈Rwj ** x x Possibilidade de rejei¸c˜ao Yuan et al (2011) Cmax x Configura¸c˜ao semi-online Bellanger et al (2012) max fj(Cj) ouPfj(Cj) x Intervalos de pj

He et al (2015) CmaxouP_J

j∈Rwj x x

* fje gjs˜ao fun¸c˜oes n˜ao decrescente em rela¸c˜ao `a Cj

** R ´e o conjunto de tarefas rejeitadas

In document INTERNASJONAL OVERENSKOMST (sider 56-66)

Alguns estudos abordam o problema de sequenciamento de lotes em uma m´aquina

com capacidade ilimitada, como ´e o caso de Cheng et al (2001). Os autores considera-

ram datas de libera¸c˜ao e datas de vencimento das tarefas, provando que mesmo quando

s˜ao considerados tempos de processamento e datas de vencimento proporcionais (ou seja,

p

≤ · · · ≤ p

e ¯d

≤ · · · ≤ ¯d

), o problema ´e tido como

N P-dif´ıcil. Al´em disso, desen-

Tabela 3.2: Resumo dos trabalhos com compt, Q < n, s

distintos,

∀j ∈ J

de libera¸c˜ao s˜ao proporcionais `as de vencimento; quando as datas de libera¸c˜ao s˜ao pro-

porcionais aos tempos de processamento; e para quando ´e conhecido o n´umero de datas

de libera¸c˜ao distintas, de distintos tempos de processamento ou de distintas datas de

vencimento. Segundo relatado, os algoritmos podem ser adaptados para o problema de

minimiza¸c˜ao do tempo de t´ermino m´aximo multiplicado por uma fun¸c˜ao n˜ao decrescente

referente aos tempos de t´ermino.

Liu et al (2003) provaram que o problema de minimiza¸c˜ao do atraso total que con-

siderada uma m´aquina sem limita¸c˜ao de capacidade ´eN P-dif´ıcil. Desenvolveram tamb´em

um algoritmo pseudo-polinomial para o problema que possui como objetivo uma fun¸c˜ao

regular e considera datas de libera¸c˜ao das tarefas diferentes de zero. Poon e Yu (2005)

propuseram uma heur´ıstica para o problema de sequenciamento online de lotes com uma

m´aquina de capacidade ilimitada, considerando datas de libera¸c˜ao e com o objetivo de

minimizar o makespan. Um segundo algoritmo foi tamb´em proposto a partir da uni˜ao do

primeiro algoritmo desenvolvido com m´etodos apresentados por Deng et al (1999) e Zhang

et al (2001a), em conjunto com a adi¸c˜ao de um parˆametro ajust´avel, que torna o algoritmo

flex´ıvel.

He et al (2007) consideraram o problema multiobjetivo, visando minimizar con-

comitantemente o m´aximo lateness e o makespan. Os autores apresentaram um algo-

ritmo de tempo polinomial baseado em PD para achar as solu¸c˜oes Pareto-´otimas. Em

Ridouard et al (2008) foram propostos trˆes algoritmos online com o objetivo de minimizar

o makespan, considerando datas de libera¸c˜ao. Os autores mostraram que dois desses algo-

ritmos fornecem as melhores solu¸c˜oes poss´ıveis para casos especiais do problema.

Al´em de considerar datas de libera¸c˜ao das tarefas, Lu et al (2008) incorporaram

ao problema a possibilidade de rejei¸c˜ao. A fun¸c˜ao objetivo tratada foi a minimiza¸c˜ao do

somat´orio do makespan das tarefas aceitas para processamento e do total de penalidades

das tarefas n˜ao processadas. Os autores propuseram um algoritmo de tempo pseudo-

polinomial baseado em PD, e provaram se tratar de um problema tido como

N P-dif´ıcil.

Quando a penalidade em caso de rejei¸c˜ao ´e igual para todas as tarefas, o algoritmo pro-

posto ´e executado em tempo polinomial. Al´em disso, um algoritmo de aproxima¸c˜ao e um

esquema de aproxima¸c˜ao de tempo polinomial foram propostos para o problema.

Yuan et al (2011) estudaram o problema de minimiza¸c˜ao do makespan com datas

de libera¸c˜ao e em uma configura¸c˜ao semi-online. A configura¸c˜ao chamada pelos autores

de semi-online, se refere ao fato de que, no instante de tempo t, s˜ao conhecidas as infor-

ma¸c˜oes sobre a pr´oxima tarefa que chegar´a no sistema de maior tempo de processamento,

chamada J

. Algoritmos online foram propostos para os seguintes casos: quando o tempo

de processamento de J

´e conhecido e s˜ao gerados no m´aximo 2 lotes; quando a data de

libera¸c˜ao de J

´e conhecida, gerando no m´aximo 3 lotes; e quando a data de libera¸c˜ao de

J

´e conhecida e com a restri¸c˜ao de que um algoritmo online gera no m´aximo 2 lotes.

No problema estudado em Bellanger et al (2012), o objetivo adotado foi a minimi-

za¸c˜ao de uma fun¸c˜ao objetivo regular, ou seja, uma fun¸c˜ao n˜ao decrescente. No problema

abordado, as tarefas possuem intervalos de tempos de processamento e devem ser proces-

sadas em lotes, necessitando para tanto que os intervalos de tempo de processamento das

tarefas pertencentes ao mesmo lote possuam uma interse¸c˜ao n˜ao-vazia. Foram identifi-

cadas propriedades de solu¸c˜oes ´otimas, com base nas quais foi desenvolvido um algoritmo

enumerativo. Para fun¸c˜oes objetivo espec´ıficas, foram apresentados(as): um algoritmo de

PD, para a minimiza¸c˜ao do tempo total de t´ermino; uma prova de que ´e poss´ıvel resolver o

problema de minimiza¸c˜ao do makespan em tempo O(nlogn); uma prova de que o problema

de minimiza¸c˜ao do m´aximo lateness ´e tido como

N P-dif´ıcil.

Na Tabela 3.3 est˜ao expostos os problemas estudados nos trabalhos descritos anteri-

ormente, nesta e nas Subse¸c˜oes 3.1.1 e 3.1.2, os quais consideram a capacidade da m´aquina

ilimitada.

Tabela 3.3: Resumo dos trabalhos com compt e Q≥ n

siderada uma m´aquina sem limita¸c˜ao de capacidade ´e_{N P-dif´ıcil. Desenvolveram tamb´em}

_{. Algoritmos online foram propostos para os seguintes casos: quando o tempo}

_{´e conhecido e s˜ao gerados no m´aximo 2 lotes; quando a data de}

_{´e conhecida, gerando no m´aximo 3 lotes; e quando a data de libera¸c˜ao de}

_{´e conhecida e com a restri¸c˜ao de que um algoritmo online gera no m´aximo 2 lotes.}

_{N P-dif´ıcil.}

Tabela 3.3: Resumo dos trabalhos com compt e Q_{≥ n}