Restrições Globais - Escalonamento
Para além das restrições globais de Sequenciação,
existem outras restrições importantes em problemas
de escalonamento (de tarefas, horários, etc).
Algumas restrições importantes são
• Garantir que uma tarefa se executa antes de
outra
• Garantir que duas tarefas não se sobrepõem no
tempo (por exemplo, por usarem o mesmo
recurso)
• Garantir que o número de tarefas que utiliza os
mesmos recursos nunca excede um dado número
(a quantidade de recurso disponível)
1
Restrições de Precedência
Precedência
Em geral, para cada tarefa i podemos considerar um
tempo de início da tarefa Ti e a sua duração Di.
Com estes pressupostos a precedência da tarefa i em
relação à tarefa j é naturalmente expressa pela
restrição
before(Ti, Di, Tj) :Ti + Di #=< Tj.
2
Restrições de Precedência
Precedência
Sendo as restrições primitivas restrição “indexicais”,
a restrição de precedência
pode ser
indexicais
Ti + Di #=< Tj
expressa directamente
before(Ti,
Ti in
Di in
Tj in
através
dos
Di, Tj)+:
inf .. max(Tj)-min(Di)
inf .. max(Tj)-min(Ti)
min(Ti)+min(Di) .. sup
3
Restrições de Não-Sobreposição
A não sobreposição de duas tarefas ém equivalente a
uma disjunção de duas restrições de precedência:
Ou a tarefa i é anterior à tarefa j ,
Ou a tarefa j é anterior à tarefa i .
Há várias formas de implementar esta disjunção,
nomeadamente através:
1. de retrocesso,
2. do operador de cardinalidade com compromisso
mínimo,
3. de disjunção construtiva
4. de restrições globais
4
Restrições de Não-Sobreposição
Exemplo
Suponhamos as 4 tarefas do grafo,
em
que
são
indicadas
as
precedências e a exclusão mútua.
As durações são indicadas nos nós.
Pretende-se determinar quais os
escalonamentos de tarefas que
permitem terminar T4 até ao
instante 10.
T1/2
T2/4
T3/3
T4/1
project([T1,T2,T3,T4]):domain([T1,T2,T3,T4], 1, 10),
before(T1, 2, T2),
before(T1, 2, T3),
before(T2, 4, T4),
before(T3, 3, T4),
no_overlap(T2, 4, T3, 3).
5
Restrições de Não-Sobreposição
Retrocesso
A disjunção pode ser
retrocesso (a la Prolog):
implementada
através
do
no_overlap(T1, D1, T2, _):before(T1, D1, T2).
no_overlap(T1, _, T2, D2):before(T2, D2, T1).
No entanto, esta implementação tenta sempre colocar
primeiro T1 antes de T2, o que pode ser impossível ou
indesejável. Este compromisso máximo pode pois colocar
problemas de eficiência (em grandes e complexos
problemas).
6
Restrições de Não-Sobreposição
Cardinal
A disjunção pode ser implementada através do operador
de “cardinalidade”:
no_overlap(T1,D1,T2,D2):exactly(1, [T1 + D1 #=< T2, T2 + D2 #=< T1]).
exactly(0,[]).
exactly(N, [H|T]):call(H #<=> B),
N #= M+B,
exactly(M, T).
Esta implementação já não tenta colocar T1 antes de
T2. Quando a enumeração começar, um dos disjuntos é
escolhido e o outro negado. No entanto, não se eliminam
valores que são eliminados em qualquer dos disjuntos.
7
Restrições de Não-Sobreposição
Disjunção Construtiva
Com a disjunção construtiva pretende eliminar-se os valores
que não pertencem a nenhum dos disjuntos, sem optar por
nenhum deles.
no_overlap3(T1, D1, T2, D2)+:
T1 in (inf..max(T2)-min(D1)) \/ (min(T2)+min(D2)..sup),
T2 in (inf..max(T1)-min(D2)) \/ (min(T1)+min(D1)..sup),
D1 in (inf..max(T2)-min(T1)) \/ (min(D1) .. max(D1)),
D2 in (inf..max(T1)-min(T2)) \/ (min(D2) .. max(D2))
Esta implementação da disjunção construtiva é garantida
pela semântica das restrições indexicais primitivas.
8
Restrições de Não-Sobreposição
Restrição Global serialized/2
Neste problema, as 4 tarefas acabam por ser realizadas
disjuntivamente. Neste caso pode adoptar-se uma restrição
global primitiva, serialized(T,D) que garante que todas as
tarefas começadas no instante Ti com duração Di não se
sobrepõem.
no_overlap([T1,T2,T3,T4],[2,4,3,1]):serialized([T1,T2,T3,T4],[2,4,3,1],[edge_finder(true)])
De notar a opção edge_finder, que implementa um algoritmo,
baseado em [CaPi94], para melhor restringir o início de cada
tarefadetectar implementação da disjunção construtiva é
garantida pela semântica das restrições indexicais
primitivas.
9
Restrições de Não-Sobreposição
Resultados
Com a opção de retrocesso são apresentadas as duas
soluções em alternativa. De notar que como em cada
alternativa é imposta uma ordenação (não existente no
problema inicial) os domínios das variáveis são muito
restringidos.
|? T in 1..10, project(T).
|? T in 1..11, project(T).
T1 = 1 ,T2 = 3,
T1 in 1..2, T2 in 3..4,
T3 = 7, T4 = 10 ? ;
T3 in 7..8, T4 in 10..11 ? ;
T1 = 1 ,T2 = 6,
T1 in 1..2, T2 in 6..7,
T3 = 3, T4 = 10 ? ;
T3 in 3..4, T4 in 10..11 ? ;
no
no
10
Restrições de Não-Sobreposição
Resultados
Com a opção de compromisso mínimo, não se obtem muitos
cortes. Apenas se descobrem sequências T1, T2 e T4 e T1,
T3 e T4, separadas, pelo que os cortes no fim de T1 e no
início de T4 não são tão significativos como antes.
|?- T in 1..10, project(T).
T1 in 1 .. 4,
T2 in 3 .. 6,
T3 in 3 .. 7,
T4 in 7 .. 10
? ;
no
| ?T1
T2
T3
T4
no
T in
in 1
in 3
in 3
in 7
1..11, project(T).
.. 5,
.. 7,
.. 8,
.. 11
? ;
11
Restrições de Não-Sobreposição
Resultados
Com a opção de disjunção construtiva, obtem-se os mesmos
cortes em T1 e T4. Adicionalmente, a disjunção construtiva
elimina valores de T2 e T3 que não podem pertencer a
nenhuma solução.
|?- T in 1..10, project(T).
T1 in 1 .. 4,
T2 in{3} \/ {6},
T3 in{3} \/ {7},
T4 in 7.. 10
? ;
no
| ?T1
T2
T3
T4
no
T in 1..11, project(T).
in 1 .. 5,
in(3..4) \/ (6..7),
in(3..4) \/ (7..8),
in 7 .. 11
? ;
12
Restrições de Não-Sobreposição
Resultados
Com a opção de serialização, conseguem-se não só os
resultados da disjunção construtiva, como se restringem os
valores de T1 (mas não de T4) por se considerarem as
sequências T1, T2, T3 e T4 ou T1, T3, T2 e T4.
|?- T in 1..10, project(T).
T1 = 1,
T2 in{3}\/{6},
T3 in{3}\/{7},
T4 = 10 ? ;
no
| ?T1
T2
T3
T4
no
T in 1..11, project(T).
in 1..2,
in(3..4)\/(6..7),
in(3..4)\/(7..8),
in 7..11 ? ;
13
Restrições de Não-Sobreposição
Redundância
Nem mesmo a opção de serialização consegue inferir na
totalidade os cortes nos domínios das variáveis. O
resolvedor de restrições pode ser auxiliado neste
objectivo pela explicitação de restrições redundantes.
Com efeito, as tarefas 2 e 3 nunca podem terminar antes
de se esgotarem as duas durações após o início da primeira
tarefa. Assim a tarefa T4 nunca poderá começar antes de
min(min(T2),min(T3))+D2+D3
14
Restrições Redundantes
Redundância
No SICStus, tal pode ser expresso da seguinte forma.
1. Cria-se um intervalo cujo limite inferior seja o pretendido.
Assim para o limite inferior
min(min(T2),min(T3))+D2+D3
cria-se o intervalo
E in (min(T2)+D2+D3..sup)\/(min(T3)+D2+D3..sup))
2. Garante-se que a tarefa 4 se executa neste intervalo
(pode considerar-se esta intervalo como o início de uma
tarefa de duração nula e garantir que esta é anterior a T4)
before(E, 0, T4)
15
Restrições Redundantes
Um procedimento semelhante pode ser tomado para garantir
que a tarefa T1 não começa “tarde de mais”. Combinando as
duas inferências
1. Determinam-se os limites (“edges”) das tarefas 2 e 3 com
a chamada
edges(T2,4,T3,3,Edge23_lo,Edge23_up)
2. Impõem-se limites às tarefas 1 e 4 com base nos limites
assim definidos
before(Edge23_up, 0, T4),
before(T1, 2, Edge23_lo),
16
Restrições Redundantes
A definição dos “edges” das tarefas 2 e 3 combinadas é
feita como indicado antes
edges(T2,D2,T3,D3,Lo,Up)+:
Lo in ((inf..max(T2)-D3) \/ (inf..max(T3)-D2)),
Up in ((min(T2)+D2+D3..sup) \/ (min(T3)+D2+D3..sup)).
já que min(min(T2),min(T3))+D2+D3 corresponde a
Up in ((min(T2)+D2+D3..sup) \/ (min(T3)+D2+D3..sup))
e que max(max(T2+D2),max(T3+D3))-D2-D3 corresponde a
Lo in ((inf..max(T2)-D3) \/ (inf..max(T3)-D2))
17
Restrições Redundantes
Resultados
Com a opção de compromisso mínimo, não se obtem cortes
na disjunção das tarefas T2 e T3, mas os limites de T1 e
T4 são bem delimitados.
|?- T in 1..10, project(T).
T1 = 1,
T2 in 3 .. 6,
T3 in 3 .. 7,
T4 = 10
? ;
no
| ?T1
T2
T3
T4
no
T in 1..11, project(T).
in 1 .. 2,
in 3 .. 7,
in 3 .. 8,
in 10.. 11
? ;
18
Restrições Redundantes
Resultados
Com a opção de disjunção construtiva, além de se obterem
cortes na disjunção das tarefas T2 e T3, obtêm-se os
limites correctos de T1 e T4.
|?- T in 1..10, project(T).
T1 = 1,
T2 in{3}\/{6},
T3 in{3}\/{7},
T4 = 10
? ;
no
| ?T1
T2
T3
T4
no
T in 1..11, project(T).
in 1 .. 2,
in(3..4) \/ (6..7),
in(3..4) \/ (7..8),
in 10 .. 11
? ;
19
Restrição Global - Cumulative
A restrição global serialized(T,D), que impõe a não
sobreposição de tarefas Ti com durações Di, é um caso
particular da restrição global cumulative(T,D,R,L),
que para um conjunto de tarefas Ti com durações Di e que
utilizam uma quantidade Ri de um recurso, garante que a
utilização desse recurso nunca excede L unidades.
Nestas condições
serialized(T,D)  cumulative(T,D,R,1)
em que R = [1,1,...1]. Como cada tarefa utiliza a
única unidade de recurso disponível, a serialização das
tarefas é garantida.
20
Restrição Global - Cumulative
A restrição global cumulative/4, permite não só
raciocinar de uma forma global sobre a duração das
tarefas, mas também especificar este tipo de
restrições, cuja decomposição em restrições mais
simples é muito pouco prática.
Sejam a = min i (Ti)
e b = maxi(Ti+Di). Seja
ainda Si,k = Ri se Ti =< tk =< Ti+Di ou 0 no caso
contrário.
cumulative(T,D,R,L) 

 Si,k  L
k[a,b] i
21
Restrição Global - Cumulative
A restrição global cumulative/4, foi inicialmente
introduzida na linguagem CHIP [AgBe94] tendo em vista
a
execução
eficiente
de
vários
problemas,
nomeadamente
1. escalonamento temporal de tarefas disjuntas
2. escalonamento de tarefas com limitação de recursos
3. colocação de componentes
A sua implementação não é apresentada no artigo
referido. No entanto, uma generalização da restrição
global (com tarefas incluindo recursos negativos para
modelar processos de produção e consumo) é explicada
num artigo mais recente [BeCa02].
22
Escalonamento de Tarefas - Cumulative
Exemplo: São dadas 7 tarefas (A a G) com as durações e
o consumo de recursos (por exemplo número de
trabalhadores necessárias para a efectuar) indicados na
seguinte tabela.
D=[2,4,3,2,1,2,2]
R=[4,1,3,1,2,3,2]
Gráficamente
Pretende determinar-se se as tarefas podem ser todas
concluídas num dado tempo máximo (Tmax), se estiver
disponível um número de trabalhadores Rmax.
23
Escalonamento de Tarefas - Cumulative
Com a restrição global cumulative/4, o problema anterior
pode ser facilmente especificado (o predicado latest
garante que todas as tarefas terminam antes de Tmax)
plan1(Tmax,Rmax, T):T = [T1,T2,T3,T4,T5,T6,T7],
D = [ 2, 4, 3, 2, 1, 2, 2],
R = [ 4, 1, 3, 1, 2, 3, 2],
domain(T, 1, 15),
cumulative(T,D,R,Rmax),
latest(T,D,Tmax),
labeling([ff],T).
Nota: A “área” de todas as tarefas é 35, donde o problema
só é possível se Tmax * Rmax >= 35
24
Restrições Global - Cumulative
Resultados
Com Tmax = 9 e Rmax = 4 obtém-se várias respostas,
nomeadamente
R
4
1 3 3 7 9 6 8
3
2
t
1
1
2
3
4
5
6
7
8
9
8 1 3 5 7 1 6
6 1 1 8 5 8 4
25
Restrições Global - Cumulative
Resultados
Com Tmax = 7 e Rmax = 5 (neste caso não há tempos
livres) continuam-se a obter várias respostas, tais como
1 1 3 3 5 6 6
4 4 1 6 3 6 1
26
Restrições Global - Cumulative
Resultados
Com Tmax = 6 e Rmax = 6 (neste caso há 1 tempo livre)
ainda se continuam a obter várias respostas, tais como
1 1 3 1 6 5 3
5 3 2 5 1 1 3
Questão: E com Tmax = 5 e Rmax = 7 ?
27
Escalonamento de Tarefas Versáteis
As tarefas são “versáteis” quando permitem troca de
tempo por recursos.
Por exemplo, uma tarefa pode ser feita por 2 pessoas
em 3 horas ou por 3 pessoas em 2 horas.
Tarefas versáteis podem “encaixar-se” melhor na “área”
disponível.
O escalonamento dessas tarefas pode ser feito como
anteriormente. No entanto, se antes havia constantes
Kdi e Kri para a duração e recursos requeridos pela
tarefa i, agora passamos a ter variáveis Di e Ri tais que
Di * Ri #= Kdi * Kri
28
Escalonamento de Tarefas - Cumulative
O programa é semelhante ao anterior, igualmente fazendo
uso da restrição global cumulative/4. As diferenças são
a versatilidade das tarefas (listas D e R), restringida pelo
predicado constrain_tasks/2. A enumeração deve agora
ser feita não só nas variáveis T mas também nas D (ou R).
plan2(Tmax,Rmax, T, D, R):T = [T1,T2,T3,T4,T5,T6,T7],
domain([T1,T2,T3,T4,T5,T6,T7], 1, 15),
D = [D1,D2,D3,D4,D5,D6,D7],
Dc = [ 2, 4, 3, 2, 1, 2, 2],
R = [R1,R2,R3,R4,R5,R6,R7],
Rc = [ 4, 1, 3, 1, 2, 3, 2],
constrain_tasks(D,R,Dc,Rc),
cumulative(T,D,R,Rmax),
latest(T,D,Tmax),
append(T,D,V),
labeling([ff],V).
29
Escalonamento de Tarefas - Cumulative
O predicado constrain_tasks/2 é implementado como
abaixo indicado. As variáveis D e R são inicializadas com o
domínio 1..9), e é imposta para cada tarefa a restrição que
define a sua versatilidade.
constrain_tasks(D,R,Dc,Rc):domain(D, 1, 9),
domain(R, 1, 9),
set_cons(D,R,Dc,Rc).
set_cons([],[],[],[]).
set_cons([D1|Dt1],[R1|Rt1],[D2|Dt2],[R2|Rt2]):D1 * R1 #= D2 * R2,
set_cons(Dt1,Rt1,Dt2,Rt2).
30
Escalonamento de Tarefas - Cumulative
Resultados
Com Tmax = 6 e Rmax = 6 (neste caso há 1
tempo livre) obtêem-se novas respostas, tais
como
D
R
T
2 1 3 1 1 2 2
4 4 3 2 2 3 2
4 6 1 5 6 1 3
31
Escalonamento de Tarefas - Cumulative
Com Tmax = 5 e Rmax = 7 (sem resposta anteriormente)
existem agora várias respostas. De notar que, na
segunda resposta não só há uma rotação como ocorre
uma transformação (4*1  2*2).
D
R
T
2 4 3 1 1 2 2
4 1 3 2 2 3 2
4 2 1 1 1 2 4
D
R
T
2 2 3 1 1 2 2
4 2 3 2 2 3 2
1 4 1 5 3 4 3
32
Job Shop - Cumulative
O problema de “job shop” consiste em executar as várias
tarefas de vários trabalhos garantindo-se que não são
excedidos os recursos disponíveis.
Dentro de cada trabalho existem várias tarefas, com
uma dada duração. Dentro de cada trabalho, as tarefas
têm de ser feitas na sua sequência natural, sendo
aceites intervalos entre o fim de uma tarefa e o início
da próxima.
Tarefas de trabalhos diferentes são independentes a
menos da utilização de recursos (máquinas).
Cada tarefa deve ser realizada numa máquina de um
determinado tipo. O número de máquinas de cada tipo é
limitado.
33
Job Shop - Cumulative
Denotando por JXYZ a Y-ésima tarefa do trabalho X
que deve ser executada na máquina Z, e tem uma
duração D, uma instância do problema 10*10 é a seguinte
(cada máquina só aceita uma tarefa de cada vez)
Y
X
M, D
1
2
3
4
5
6
7
8
9
a
1
1, 29
1, 43
2, 91
2, 81
3, 14
3, 84
2, 46
3, 31
1, 76
2, 85
2
2, 78
3, 90
1, 85
3, 95
1, 6
2, 2
1, 37
1, 86
2, 69
1, 13
3
3, 9
5, 75
4, 39
1, 71
2, 22
6, 52
4, 61
2, 46
4, 76
3, 61
4
4, 36
a, 11
3, 74
5, 99
6, 61
4, 95
3, 13
6, 74
6, 51
7, 7
5
5, 49
4, 69
9, 90
7, 9
4, 26
9, 48
7, 32
5, 32
3, 85
9, 64
6
6, 11
2, 28
6, 10
9, 52
5, 69
a, 72
6, 21
7, 88
a, 11
a, 76
7
7, 62
7, 46
8, 12
8, 85
9, 21
1, 47
a, 32
9, 19
7, 40
6, 47
8
8, 56
6, 46
7, 89
4, 98
8, 49
7, 65
9, 89
a, 48
8, 89
4, 52
9
9, 44
8, 72
a, 45
a, 22
a, 72
5, 6
8, 30
8, 36
5, 26
5, 90
a
a, 21
9, 30
5, 33
6, 43
7, 53
8, 25
5, 55
4, 79
9, 74
8, 45
34
Job Shop - Cumulative
Esta instância foi proposta
Scheduling [MuTh63].
no
livro
Industrial
Durante 20 anos não se obteve a solução óptima (do
ponto de vista do “makespan”, isto é, da terminação mais
rápida).
Por volta de 1980, a melhor solução era 935 (unidades
de tempo). Em 1985, um limite inferior de 930 foi obtido
para o óptimo.
Em 1987 o problema foi resolvido com um algoritmo
altamente especializado, obtendo-se o óptimo de 930.
Com a utilização de restrição cumulative/4, o problema
foi resolvido em 1506 segundos (SUN/SPARC).
35
Job Shop - Cumulative
Uma instância mais simples deste problema é dado pelo
quadro abaixo ( com a respectiva representação gráfica).
De notar que nesta instância se assume que cada tarefa
requer uma unidade do recurso indicado, mas que existem
2 recursos do tipo 1 e outros 2 do tipo 2.
X
M, D
1
2
3
4
1
2,1
3,1
5,1
3,1
Y
2
4,2
4,2
3,2
3,2
J1
3
7,1
5,1
3,2
4,2
J2
1
2
1
J3
J4
3
2
1
1
3
2
2
3
3
36
Job Shop - Cumulative
Esta instância do problema pode ser facilmente resolvida
como seguinte programa SICStus:
jobs([J1,J2,J3,J4]):% definição dos vários trabalhos
J1 = [S111,S122,S131]-[2,4,7]-[1,2,1],
J2 = [S211,S222,S231]-[3,4,5]-[1,2,1],
J3 = [S311,S322,S332]-[5,3,3]-[1,2,2],
J4 = [S411,S422,S432]-[3,3,4]-[1,2,2],
% declaração de domínios
domain([S111,S122,S131],0,15), domain([S211,S222,S231],0,15),
domain([S311,S322,S332],0,15), domain([S411,S422,S432],0,15),
% restrições de precedência
% restrições de limitação de recursos
% restrições sobre a terminação dos vários trabalhos
% enumeração do início das diversas tarefas
37
Job Shop - Cumulative
As restrições são as seguintes:
% restrições de precedência
S122#>=S111+2, S131#>=S122+4, S222#>=S211+3, S231#>=S222+4,
S322#>=S311+5, S332#>=S322+3, S422#>=S411+3, S432#>=S422+3,
% restrições de limitação de recursos
cumulative([S111,S131,S211,S231,S311,S411],[2,7,3,5,5,3],
[1,1,1,1,1,1],2),
cumulative([S122,S222,S322,S332,S422,S432],[4,4,3,3,3,4],
[1,1,1,1,1,1],2),
% restrições sobre a terminação dos vários trabalhos
E #>= S131+7, E #>= S231+5, E #>= S332+3, E #>= S432+4,
E #=< 13,
% enumeração do início das diversas tarefas
labeling([ff], [S111, S122, S131, S211, S222, S231,
S311, S322, S332, S411, S422, S432]).
38
Job Shop - Cumulative
Os resultados obtidos (com terminação naterior a 13) são os seguintes:
| ?- jobs(J).
J=[[0,2, 6]-[2,4,7]-[1,2,1],
0
1
2
3
4
1
1
5
6
7
8
9
1
3
1
3
10
11
[0,3, 7]-[3,4,5]-[1,2,1],
2
2
[2,7,10]-[5,3,3]-[1,2,2],
2
3
2
3
[3,6, 9]-[3,3,4]-[1,2,2]]? ;
J=[[0,2, 6]-[2,4,7]-[1,2,1],
1
[0,3, 8]-[3,4,5]-[1,2,1],
[2,7,10]-[5,3,3]-[1,2,2],
1
1
3
1
3
2
2
2
3
2
3
[3,6, 9]-[3,3,4]-[1,2,2]]? ;
no
39
12
Colocação de Componentes
Vários problemas de grande importância económica
envolvem restrições de colocação, ou seja como
colocar vários componentes num determinado espaço.
Alguns desses problemas são
• Cortes de peças de madeira de pranchas grandes
e padronizadas;
• Corte de peças de um rolo de tecido;
• Colocação de pacotes em contentores.
Os primeiros dois problemas são a 2 dimensões
enquanto que o terceiro é a 3 dimensões. Vamo-nos
restringir a problemas de 2 dimensões em que todos
os elementos são rectangulares.
40
Colocação de Componentes
Uma constatação imediata é o paralelismo entre
estes problemas 2D e os de escalonamento de
tarefas, considerando-se
• O tempo como a dimensão X (abcissas);
• Os recursos como dimensão Y (ordenadas);
• A duração de uma tarefa como a sua dimensão X
• Os recursos da tarefa como a sua dimensão Y
Assim os programas utilizados anteriormente podem
aparentemente continuar a sê-lo com esta nova
interpretação.
41
Colocação de Componentes
Exemplo: São dados 11 peças rectângulares (A a K) que é
necessário obter através do corte de uma prancha
rectangular.
Os
rectângulos
têm
as
(comprimento-W e altura-H)
seguintes
dimensões
W = [ 1, 2, 1, 3, 1, 2, 4, 5, 2, 3, 3]
H = [ 2, 1, 3, 1, 4, 2, 1, 1, 3, 2, 3]
Gráficamente
D
A
E
F
G
C
I
B
J
K
H
42
Colocação de Componentes
place(Comprimento,Altura, Time):-
% definição dos rectângulos
X = [Ax,Bx,Cx,Dx,Ex,Fx,Gx,Hx,Ix,Jx,Kx],
W = [ 2, 1, 1, 3, 1, 2, 4, 5, 2, 3, 3],
H = [ 1, 2, 3, 1, 4, 2, 1, 1, 3, 2, 3],
domain(X, 1, Comprimento),
% restrições em altura e comprimento nos X
maximo(X,W,Comprimento),
cumulative(X,W,H,Altura),
% enumeração da origem-X dos rectângulos
labeling([ffc], X).
43
Colocação de Componentes
Infelizmente, os resultados obtidos não têm uma leitura
directa. Por exemplo uma das soluções obtidas com um
rectângulo de 8 * 6 são
X = [ 6, 7, 5, 1, 4, 5, 1, 1, 7, 6, 1]
que pode ser lida como (???)
ou como
F
K
I
E
A
D
C
G
B
J
H
D
A
E
F
G
C
I
B
H
J
K
44
Colocação de Componentes
Desta forma há que garantir a fixação da origem de
cada peça igualmente no eixo das ordenadas (Y).
Esta fixação pode ser feita tendo em atenção que ao
rodarmos os rectângulos iniciais em 90º (e fizermos
uma simetria vertical), os eixos do X e do Y ficam
trocados.
Assim o tratamento do eixo dos Y pode ser feito
como o do eixo do X, obtendo-se um programa
semelhante ao anterior.
45
Colocação de Componentes
place(Comprimento,Altura, Time):% definição dos rectângulos
% restrições em altura e comprimento nos X
% enumeração da origem-X dos rectângulos
% determinação das origens-Y dos rectângulos
Y = [Ay,By,Cy,Dy,Ey,Fy,Gy,Hy,Iy,Jy,Ky],
domain(Y, 1, Altura),
% restrições em altura e comprimento nos Y
maximo(Y,H,Altura),
cumulative(Y,H,W,Comprimento),
% enumeração da origem-Y dos rectângulos
labeling([ff], Y).
46
Colocação de Componentes
Infelizmente, os resultados obtidos ainda não são os
esperados. Por exemplo, a primeira solução obtida é
X-Y = [7-4,6-2,5-1,1-5,4-1,5-4,1-1,1-6,7-1,6-5,1-2]
correspondendo a
?????
Analisando-se a causa do problema é fácil concluir que não foi
imposta nenhuma “não-sobreposição” entre os componentes !
D
A
E
F
G
C
I
B
H
J
K
47
Não-Sobreposição de Componentes
A não-sobreposição de elementos com características
(X1,Y1,W1,H1) e (X2,Y2,W2,H2) é garantida desde que
uma das seguintes restrições seja satisfeita
X1+W1 =< X2
O elemento 1 está à esquerda do 2
X2+W2 =< X1
O elemento 1 está à direita do 2
Y1+H1 =< Y2
O elemento 1 está abaixo do 2
Y2+H2 =< Y1
O elemento 1 está acima do 2
Em vez de impôr uma destas condições e testar as
alternativas por retrocesso, podemos impô-las através
do compromisso mínimo, com um operador do tipo do
operador cardinalidade.
48
Não-Sobreposição de Componentes
none_overlap([],[],[],[]).
none_overlap([Hx|Tx], [Hy|Ty], [Hd|Td], [Hr|Tr]):no_overlap_each(Hx, Hy, Hd, Hr, Tx, Ty, Td, Tr),
none_overlap(Tx, Ty, Td, Tr).
no_over (_,_,_,_,[],[],[],[]).
no_over (X1,Y1,D1,R1,[X2|Tx],[Y2|Ty],[D2|Td],[R2|Tr]):disj(X1,Y1,D1,R1,X2,Y2,D2,R2),
no_over (X1,Y1,D1,R1,Tx, Ty, Td, Tr).
disj(X1,Y1,D1,R1,X2,Y2,D2,R2):sat(M,[X1+D1#=<X2,X2+D2#=<X1,Y1+R1#=<Y2,Y2+R2#=<Y1]),
M #>=1.
sat(0,[]).
sat(N,[H|T]):call(H #<=> B),
N #= M + B,satisfy(M, T).
49
Não-Sobreposição de Componentes
Podemos agora apresentar o programa completo para
colocação de componentes, salientando a simetria em
relação aos eixos dos X e dos Y
place(Comp,Altura, Time):% definição dos rectângulos
X = [Ax ... Kx],
Y = [Ay ... Ky],
W = [ 1 ... 3],
H = [ 2 ... 3],
domain(X, 1, Comp),
domain(Y, 1, Altura),
% restrições em altura e comprimento
maximo(X,W,Comp),
maximo(Y,H,Altura),
% restrições cumulativas redundantes
cumulative(Y,H,W,Comp), cumulative(X,W,H,Altura),
% restrições de não sobreposição
none_overlap(X,Y,D,R),
% enumeração das origens dos rectângulos
app(X,Y,Z),
labeling([ffc], Z).
50
Colocação de Componentes
De notar ainda que
• a enumeração deve ser feita quer nos Xi quer nos Yj,
donde a sua junção numa só lista Z;
• Há várias heurísticas possíveis para enumeração das
variáveis. A escolhida (para a variável), ffc, é “clássica”.
• Outra hipótese é ir colocando um rectângulo (o “maior”)
na primeira casa não ocupada num “canto” (todas as casas
têm de ser ocupadas).
• As restrições Cumulative não são estritamente
necessárias, já que os limites ficam assegurados pelas
restrições de limites em ambos os eixos.
• No, entanto, elas são muito úteis como restrições
redundantes!
51
Colocação de Componentes
Os resultados obtidos mostram bem a importância de se
utilizar a restrição global cumulative/4 como restrição
redundante. Com efeito, testando o programa anterior com e
sem estas restrições redundantes obtemos os seguintes
resultados
em 40 ms c/ cumulative em 24.465 ms sem cumulative
D
A
E
F
G
C
I
B
H
J
K
52
Colocação de Componentes com Rotação
Uma limitação óbvia dos programas feitos até agora é a sua
impossibilidade de rodarem os componentes de 90º de
forma a poderem “encaixar” melhor no espaço disponível.
Por vezes só através destas rotações é que é possível
colocar os componentes pretendidos.
As alterações a fazer aos programas anteriores são
pequenas. Dadas dimensões constantes Wc - Hc em
comprimento e altura, apenas há que permitir que as
dimensões “reais” dos componentes W-H ou são as
indicadas ou são as “trocadas”.
Dadas as dimensões constantes, essa flexibilidade é obtida
pelo valor do parametro Modo (fixo/roda)
53
Colocação de Componentes com Rotação
Exemplo:
... Wc = [ 6, 6, 5, 5, 4, 4, 3, 3, 2, 2],
Hc = [ 2, 1, 2, 1, 2, 1, 2, 1, 2, 1],
domains(Modo,W,H,Wc,Hc),
...
=======================
domains(fixo, [],[],[],[]).
domains(fixo, [W|Wt],[H|Ht],[Wc|Wtc],[Hc|Htc]):W = Wc, H = Hc, domains(fixo,Td,Tr,Tdc,Trc).
domains(roda, [],[],[],[]).
domains(roda,[Hd|Td],[Hr|Tr],[Hdc|Tdc],[Hrc|Trc]):Hd in {Hdc}\/{Hrc},
Hr in {Hdc}\/{Hrc},
Hr * Hd #= Hdc * Hrc,
domains(roda, Td,Tr,Tdc,Trc).
54
Colocação de Componentes com Rotação
Na enumeração há agora que ter em conta a rotação ou não
do componente. Para isso basta enumerar uma das
dimensões (W), para além da enumeração das origens X e Y
de cada componente.
Uma heurística possível é tentar colocar primeiro os
componentes mais “difíceis”. Aqui consideramo-los como os
que têm uma dimensão mais comprida e ordenamo-los como
indicado atrás.
Assim esta heurística de enumeração
implementada através das chamadas
pode
ser
merge( X, Y, Z),
labeling([], Z),
labeling([ffc], W),
55
Colocação de Componentes com Rotação
Exemplo: São dados 10 rectangulos (A a J) que é
necessário colocar numa prancha rectangular com área
total de 60, podendo eventualmente ser rodados.
Os
rectângulos
têm
as
(comprimento-W e altura-H)
seguintes
dimensões
Wc = [ 6, 6, 5, 5, 4, 4, 3, 3, 2, 2],
Hc = [ 2, 1, 2, 1, 2, 1, 2, 1, 2, 1],
Gráficamente
A
C
E
G
I
B
D
F
H
J
56
Colocação de Componentes com Rotação
Resultados em modo fixo (tempos em ms):
Comp Larg
2
30
3
20
4
15
5
12
6
10
10
6
12
5
15
4
20
3
30
2
ms
532
542
542
542
552
40
40
50
40
120
X-Y
no
no
no
no
no
[1-1,1-3,1-4,1-6,7-1,7-3,6-4,6-6,9-4,9-6]
[1-1,1-3,1-4,6-5,7-1,6-4,10-3,7-3,11-1,11-5]
[1-1,1-3,7-1,1-4,12-1,7-3,11-3,6-4,14-3,9-4]
[1-1,1-3,7-1,7-3,12-1,12-3,16-1,16-3,19-1,19-3]
[1-1,7-1,17-1,7-2,22-1,13-1,26-1,12-2,29-1,15-2]
A
C
E
G
I
B
D
F
H
J
57
Colocação de Componentes com Rotação
Resultados c/ rotação (a vermelho as peças rodadas):
Comp Larg
2
30
3
20
4
15
5
12
6
10
10
6
12
5
15
4
20
3
30
2
ms
301
191
190
60
60
60
70
250
50
261
X-Y
[1-1,1-7,1-16,2-7,1-21,2-12,1-25,1-13,1-28,1-30]
[1-1,1-7,1-13,3-13,2-7,3-1,1-18,1-20,2-11,3-5]
[1-1,1-7,2-7,4-5,3-1,4-10,2-14,1-13,2-12,3-5]
[1-1,1-7,2-7,3-1,4-1,2-12,4-7,3-6,4-10,4-5]
[1-1,1-3,1-4,1-6,1-7,3-7,3-8,6-4,5-8,5-10
[1-1,1-3,1-4,1-6,6-4,6-6,7-1,10-4,9-1,9-3]
[1-1,1-3,1-4,6-4,7-1,7-3,11-1,6-5,11-4,9-5]
[1-1,1-3,7-1,1-4,9-3,15-1,12-1,6-4,13-3,7-3]
[1-1,1-3,7-1,7-3,12-1,12-3,16-1,16-3,19-1,19-3]
[1-1,7-1,16-1,7-2,21-1,12-2,25-1,13-1,28-1,30-1]
A
C
E
G
I
B
D
F
H
J
58