Formulazioni di PLI per problemi di scheduling

(1)

Formulazioni di PLI S. Nocella

Formulazione disgiuntiva

Il problema Il modello matematico Formulazioni time-indexed

Nozioni preliminari Il problema Formulazione xjt Formulazione yjt Formulazione posizionale

Il problema Il modello matematico

Vincoli speciali Vincoli di precedenza Machine breakdown Esercizi

Formulazioni di PLI per problemi di scheduling

Salvatore Nocella

[email protected]

October 26, 2006

(2)

Sommario

Problemi su singola macchina

I

Formulazione disgiuntiva

I

Formulazioni time indexed Macchine parallele identiche

I

Formulazione posizionale Formulare vincoli speciali

I

Vincoli di precedenza

I

Machine breakdown

Esercizi

(3)

Single-machine: notazione

I

Si vuole formulare il seguente problema di scheduling:

1| | X w

j

C

j I

Dati del problema:

I

Insieme dei job: J = {1, . . . , n}

I

Per ogni job j ∈ J

I wj costo

I pjtempo di processamento

I Cj tempo di completamento

(4)

Formulazione disgiuntiva: 1| | P w j C j

Variabili di decisione

t

_j

∈ R : istante di inizio del processamento di j (∀j) Funzione obiettivo

I

C

_j

= t

_j

+ p

_j

I

min P

j ∈J

w

j

(t

j

+ p

j

) Vincoli

Comunque scelgo una coppia di job distinti j , k

t

_j

+ p

_j

≤ t

_k

oppure t

_k

+ p

_k

≤ t

_j

Attenzione! Siamo interessati a formulazioni di

Programmazione LINEARE Intera

(5)

Un modello di MILP

I

Definiamo la seguente variabile di decisione:

α

jk

=

( 1 se j precede k 0 altrimenti

I

Il vincolo disgiuntivo precedente si riscrive:

(1 − α

_jk

)M + t

_k

− t

_j

≥ p

_j

∀j, k ∈ J (1 − α

_kj

)M + t

_j

− t

_k

≥ p

_k

∀j, k ∈ J

I

M P

j ∈J

p

_j

(6)

Formulazione disgiuntiva: resume

min X

j ∈J

w

j

(t

j

+ p

j

)

(1 − α

_jk

)M + t

_k

− t

_j

≥ p

_j

∀j, k ∈ J (1 − α

kj

)M + t

j

− t

_k

≥ p

_k

∀j, k ∈ J

α

jk

∈ {0, 1} ∀j, k ∈ J

t

_j

∈ R

+

∀j ∈ J

(7)

Formulazione disgiuntiva: caratteristiche

Vantaggi

I

Dimensione del modello: O |J |

²

variabili e vincoli

Svantaggi

I

Qualit` a del gap pessima: dovuta alla presenza del

coefficiente M

(8)

Esempio

job 1 2 3 4

p

_j

6 11 9 5

w

_j

3 5 7 4

Funzione obiettivo

min 3 · (t

1

+ 6) + 5 · (t

2

+ 11) + 7 · (t

3

+ 9) + 4 · (t

4

+ 5)

Vincoli

(1,2) (1 − α

₁₂

)M + t

₂

− t

₁

≥ 6, (1 − α

₂₁

)M + t

₁

− t

₂

≥ 11

(1,3) (1 − α

₁₃

)M + t

₃

− t

₁

≥ 6, (1 − α

₃₁

)M + t

₁

− t

₃

≥ 9

(1,4) (1 − α

₁₄

)M + t

₄

− t

₁

≥ 6, (1 − α

₄₁

)M + t

₁

− t

₄

≥ 5

(2,3) (1 − α

23

)M + t

3

− t

₂

≥ 11, (1 − α

₃₂

)M + t

2

− t

₃

≥ 9

(2,4) (1 − α

24

)M + t

4

− t

₂

≥ 11, (1 − α

₄₂

)M + t

2

− t

₄

≥ 5

(3,4) (1 − α

₃₄

)M + t

₄

− t

₃

≥ 9, (1 − α

₄₃

)M + t

₃

− t

₄

≥ 5

(9)

Esempio

job 1 2 3 4

p

_j

6 11 9 5

w

_j

3 5 7 4

Funzione obiettivo

min 3 · (t

1

+ 6) + 5 · (t

2

+ 11) + 7 · (t

3

+ 9) + 4 · (t

4

+ 5)

Vincoli

(1,2) (1 − α

₁₂

)M + t

₂

− t

₁

≥ 6, (1 − α

₂₁

)M + t

₁

− t

₂

≥ 11

(1,3) (1 − α

₁₃

)M + t

₃

− t

₁

≥ 6, (1 − α

₃₁

)M + t

₁

− t

₃

≥ 9

(1,4) (1 − α

₁₄

)M + t

₄

− t

₁

≥ 6, (1 − α

₄₁

)M + t

₁

− t

₄

≥ 5

(2,3) (1 − α

23

)M + t

3

− t

₂

≥ 11, (1 − α

₃₂

)M + t

2

− t

₃

≥ 9

(2,4) (1 − α

24

)M + t

4

− t

₂

≥ 11, (1 − α

₄₂

)M + t

2

− t

₄

≥ 5

(3,4) (1 − α

₃₄

)M + t

₄

− t

₃

≥ 9, (1 − α

₄₃

)M + t

₃

− t

₄

≥ 5

(10)

Esempio

job 1 2 3 4

p

_j

6 11 9 5

w

_j

3 5 7 4

Funzione obiettivo

min 3 · (t

1

+ 6) + 5 · (t

2

+ 11) + 7 · (t

3

+ 9) + 4 · (t

4

+ 5)

Vincoli

(1,2) (1 − α

₁₂

)M + t

₂

− t

₁

≥ 6, (1 − α

₂₁

)M + t

₁

− t

₂

≥ 11

(1,3) (1 − α

₁₃

)M + t

₃

− t

₁

≥ 6, (1 − α

₃₁

)M + t

₁

− t

₃

≥ 9

(1,4) (1 − α

₁₄

)M + t

₄

− t

₁

≥ 6, (1 − α

₄₁

)M + t

₁

− t

₄

≥ 5

(2,3) (1 − α

23

)M + t

3

− t

₂

≥ 11, (1 − α

₃₂

)M + t

2

− t

₃

≥ 9

(2,4) (1 − α

24

)M + t

4

− t

₂

≥ 11, (1 − α

₄₂

)M + t

2

− t

₄

≥ 5

(3,4) (1 − α

₃₄

)M + t

₄

− t

₃

≥ 9, (1 − α

₄₃

)M + t

₃

− t

₄

≥ 5

(11)

Esempio

job 1 2 3 4

p

_j

6 11 9 5

w

_j

3 5 7 4

Funzione obiettivo

min 3 · (t

1

+ 6) + 5 · (t

2

+ 11) + 7 · (t

3

+ 9) + 4 · (t

4

+ 5)

Vincoli

(1,2) (1 − α

₁₂

)M + t

₂

− t

₁

≥ 6, (1 − α

₂₁

)M + t

₁

− t

₂

≥ 11

(1,3) (1 − α

₁₃

)M + t

₃

− t

₁

≥ 6, (1 − α

₃₁

)M + t

₁

− t

₃

≥ 9

(1,4) (1 − α

₁₄

)M + t

₄

− t

₁

≥ 6, (1 − α

₄₁

)M + t

₁

− t

₄

≥ 5

(2,3) (1 − α

23

)M + t

3

− t

₂

≥ 11, (1 − α

₃₂

)M + t

2

− t

₃

≥ 9

(2,4) (1 − α

24

)M + t

4

− t

₂

≥ 11, (1 − α

₄₂

)M + t

2

− t

₄

≥ 5

(3,4) (1 − α

34

)M + t

4

− t

₃

≥ 9, (1 − α

₄₃

)M + t

3

− t

₄

≥ 5

(12)

Notazione

Orizzonte di pianificazione

I

periodo (finito) nel quale avviene la schedulazione dei job del problema

I

quando non viene esplicitamente definito dall’istanza ` e una stima di C

max

Discretizzazione

I

L’orizzonte di pianificazione di lunghezza T ` e suddiviso in T periodi “atomici ” di durata unitaria

I

Il periodo t concide con l’intervallo di tempo [t − 1, t]

(13)

Il problema

I

Si vuole formulare il problema 1|r

_j

| X

w

_j

U

_j

I

r

_j

: release date

I

U

j

∈ {0, 1}: tardy-job

I

Orizzonte di pianificazione: T ≥ r

max

+ P

j ∈J

p

_j

(14)

Formulazione x jt

Variabili di decisione

x

_jt

=

( 1 se il job j termina il processamento all’istante t 0 altrimenti

Funzione obiettivo

min X

j ∈J T

X

t=dj+1

w

_j

x

_jt

ESERCIZIO

Utilizzando la precedente variabile di decisione, scrivere

l’espressione della funzione obiettivo per il problema

1|r

_j

| P w

_j

C

_j

(15)

Formulazione x jt

Variabili di decisione

x

_jt

=

( 1 se il job j termina il processamento all’istante t 0 altrimenti

Funzione obiettivo

min X

j ∈J T

X

t=dj+1

w

j

x

jt

ESERCIZIO

Utilizzando la precedente variabile di decisione, scrivere

l’espressione della funzione obiettivo per il problema

1|r

_j

| P w

_j

C

_j

(16)

Formulazione x jt

Variabili di decisione

x

_jt

=

( 1 se il job j termina il processamento all’istante t 0 altrimenti

Funzione obiettivo

min X

j ∈J T

X

t=dj+1

w

j

x

jt

ESERCIZIO

Utilizzando la precedente variabile di decisione, scrivere

l’espressione della funzione obiettivo per il problema

1|r

_j

| P w

_j

C

_j

(17)

Formulazione x jt

Vincoli

I

ciascun job deve essere processato esattamente una volta:

T

X

t=rj+pj

x

jt

= 1 ∀j ∈ J

I

l’unica macchina disponibile pu` o processare, senza interruzione, al pi` u un job per volta

X

j ∈J t+pj−1

X

s=t

x

js

≤ 1 ∀t = 1, . . . , T

I

x

jt

∈ {0, 1} ∀j ∈ J , t = r

_j

+ p

j

, . . . , T

(18)

Formulazione x jt

Vincoli

I

ciascun job deve essere processato esattamente una volta:

T

X

t=rj+pj

x

jt

= 1 ∀j ∈ J

I

l’unica macchina disponibile pu` o processare, senza interruzione, al pi` u un job per volta

X

j ∈J t+pj−1

X

s=t

x

js

≤ 1 ∀t = 1, . . . , T

I

x

jt

∈ {0, 1} ∀j ∈ J , t = r

_j

+ p

j

, . . . , T

(19)

Formulazione x jt

Vincoli

I

ciascun job deve essere processato esattamente una volta:

T

X

t=rj+pj

x

jt

= 1 ∀j ∈ J

I

l’unica macchina disponibile pu` o processare, senza interruzione, al pi` u un job per volta

X

j ∈J t+pj−1

X

s=t

x

js

≤ 1 ∀t = 1, . . . , T

I

x

jt

∈ {0, 1} ∀j ∈ J , t = r

_j

+ p

j

, . . . , T

(20)

Formulazione x jt : resume

min X

j ∈J T

X

t=dj+1

w

j

x

jt T

X

t=rj+pj

x

jt

= 1 ∀j ∈ J

X

j ∈J t+pj−1

X

s=t

x

_js

≤ 1 ∀t = 1, . . . , T

x

_jt

∈ {0, 1} ∀j ∈ J , t = r

_j

+ p

_j

, . . . , T

(21)

Formulazione x jt : caratteristiche

Svantaggi

I

Dimensione del modello: O (|J | · T ) variabili, O(|J | + T ) vincoli

Vantaggi

I

E’ possibile modellare facilmente diverse funzioni obiettivo ed alcune classi di vincoli (machine availability, precedenze, . . . )

I

Qualit` a del gap molto buono

I

Riconducibilit` a a problemi di ottimizzazione

combinatoria molto noti

(22)

Esempio

Utilizzando le variabili x

_jt

formulare il problema 1|r

_j

| P w

_j

U

_j

relativamente all’istanza seguente:

job 1 2 3 4

r

_j

4 3 5 0

p

j

3 1 5 4

d

_j

10 6 11 8

w

_j

3 5 10 2

Orizzonte di pianificazione

T = 18

(23)

Esempio

Utilizzando le variabili x

_jt

formulare il problema 1|r

_j

| P w

_j

U

_j

relativamente all’istanza seguente:

job 1 2 3 4

r

j

4 3 5 0

p

_j

3 1 5 4

d

_j

10 6 11 8

w

j

3 5 10 2

Orizzonte di pianificazione

T = 18

(24)

Esempio

Utilizzando le variabili x

_jt

formulare il problema 1|r

_j

| P w

_j

U

_j

relativamente all’istanza seguente:

job 1 2 3 4

r

j

4 3 5 0

p

_j

3 1 5 4

d

_j

10 6 11 8

w

j

3 5 10 2

Orizzonte di pianificazione

T = 18

(25)

Esempio (cont’d)

Funzione obiettivo

min3 · (x

_1,11

+ x

_1,12

+ · · · + x

_1,18

) + 5 · (x

_2,7

+ · · · + x

_2,18

) +

+ 10 · (x

3,12

+ · · · + x

3,18

) + 2 · (x

4,9

+ · · · + x

4,18

)

(26)

Esempio (cont’d)

Vincoli

I

ciascun job deve essere processato esattamente una volta

PT

t=rj +pjx_jt= 1 ∀j ∈ J

j = 1 x

1,7

+ x

1,8

+ · · · + x

1,18

= 1

j = 2 x

_2,4

+ · · · + x

_2,18

= 1

j = 3 x

_3,10

+ · · · + x

_3,18

= 1

j = 4 x

_4,4

+ · · · + x

_4,18

= 1

(27)

Esempio (cont’d)

Vincoli

I

ciascun job deve essere processato esattamente una volta

PT

j = 1 x

1,7

+ x

1,8

+ · · · + x

1,18

= 1

j = 2 x

_2,4

+ · · · + x

_2,18

= 1

j = 3 x

_3,10

+ · · · + x

_3,18

= 1

j = 4 x

_4,4

+ · · · + x

_4,18

= 1

(28)

Esempio (cont’d)

Vincoli

I

ciascun job deve essere processato esattamente una volta

PT

j = 1 x

1,7

+ x

1,8

+ · · · + x

1,18

= 1

j = 2 x

_2,4

+ · · · + x

_2,18

= 1

j = 3 x

_3,10

+ · · · + x

_3,18

= 1

j = 4 x

_4,4

+ · · · + x

_4,18

= 1

(29)

Esempio (cont’d)

Vincoli

I

ciascun job deve essere processato esattamente una volta

PT

j = 1 x

1,7

+ x

1,8

+ · · · + x

1,18

= 1

j = 2 x

_2,4

+ · · · + x

_2,18

= 1

j = 3 x

_3,10

+ · · · + x

_3,18

= 1

j = 4 x

_4,4

+ · · · + x

_4,18

= 1

(30)

Esempio (cont’d)

Vincoli

I

ciascun job deve essere processato esattamente una volta

PT

j = 1 x

1,7

+ x

1,8

+ · · · + x

1,18

= 1

j = 2 x

_2,4

+ · · · + x

_2,18

= 1

j = 3 x

_3,10

+ · · · + x

_3,18

= 1

j = 4 x

_4,4

+ · · · + x

_4,18

= 1

(31)

Esempio (cont’d)

Vincoli

I

l’unica macchina disponibile pu` o processare, senza interruzione, al pi` u un job per volta

I

t = 10

P j ∈J

Pt+pj −1

s=t x_js≤ 1 ∀t = 1, . . . , T

x_1,10+ x_1,11+ x_1,12+ +x_2,10+

+x_3,10+ x_3,11+ x_3,12+ x_3,13+ x_3,14+ +x4,10+ x4,11+ x4,12+ x4,13≤ 1

(32)

Esempio (cont’d)

Vincoli

I

l’unica macchina disponibile pu` o processare, senza interruzione, al pi` u un job per volta

I

t = 10

P j ∈J

Pt+pj −1

s=t x_js≤ 1 ∀t = 1, . . . , T

x_1,10+ x_1,11+ x_1,12+ +x_2,10+

+x_3,10+ x_3,11+ x_3,12+ x_3,13+ x_3,14+ +x4,10+ x4,11+ x4,12+ x4,13≤ 1

(33)

Esempio (cont’d)

Vincoli

I

l’unica macchina disponibile pu` o processare, senza interruzione, al pi` u un job per volta

I

t = 10

P j ∈J

Pt+pj −1

s=t x_js≤ 1 ∀t = 1, . . . , T

x_1,10+ x_1,11+ x_1,12+ +x_2,10+

+x_3,10+ x_3,11+ x_3,12+ x_3,13+ x_3,14+ +x4,10+ x4,11+ x4,12+ x4,13≤ 1

(34)

Esempio (cont’d)

Vincoli

I

l’unica macchina disponibile pu` o processare, senza interruzione, al pi` u un job per volta

I

t = 6

P j ∈J

Pt+pj −1

s=t x_js≤ 1 ∀t = 1, . . . , T

x_1,7+ x_1,8+ +x_2,6+ +x_3,10+

+x4,6+ x4,7+ x4,8+ x4,9≤ 1

(35)

Esempio (cont’d)

Vincoli

I

l’unica macchina disponibile pu` o processare, senza interruzione, al pi` u un job per volta

I

t = 6

P j ∈J

Pt+pj −1

s=t x_js≤ 1 ∀t = 1, . . . , T

x_1,7+ x_1,8+ +x_2,6+ +x_3,10+

+x4,6+ x4,7+ x4,8+ x4,9≤ 1

(36)

Esempio (cont’d)

Vincoli

I

l’unica macchina disponibile pu` o processare, senza interruzione, al pi` u un job per volta

I

t = 6

P j ∈J

Pt+pj −1

s=t x_js≤ 1 ∀t = 1, . . . , T

x_1,7+ x_1,8+ +x_2,6+ +x_3,10+

+x4,6+ x4,7+ x4,8+ x4,9≤ 1

(37)

Esempio (cont’d)

Vincoli

I

l’unica macchina disponibile pu` o processare, senza interruzione, al pi` u un job per volta

I

t = 16

P j ∈J

Pt+pj −1

s=t x_js≤ 1 ∀t = 1, . . . , T

x_1,16+ x_1,17+ x_1,18+ +x_2,16+

+x_3,16+ x_3,17+ x_3,18+ +x4,16+ x4,17+ x4,18≤ 1

(38)

Esempio (cont’d)

Vincoli

I

l’unica macchina disponibile pu` o processare, senza interruzione, al pi` u un job per volta

I

t = 16

P j ∈J

Pt+pj −1

s=t x_js≤ 1 ∀t = 1, . . . , T

x_1,16+ x_1,17+ x_1,18+ +x_2,16+

+x_3,16+ x_3,17+ x_3,18+ +x4,16+ x4,17+ x4,18≤ 1

(39)

Esempio (cont’d)

Vincoli

I

l’unica macchina disponibile pu` o processare, senza interruzione, al pi` u un job per volta

I

t = 16

P j ∈J

Pt+pj −1

s=t x_js≤ 1 ∀t = 1, . . . , T

x_1,16+ x_1,17+ x_1,18+ +x_2,16+

+x_3,16+ x_3,17+ x_3,18+ +x4,16+ x4,17+ x4,18≤ 1

(40)

Formulazione y jt

Variabili di decisione

y

_jt

=

( 1 se il job j viene processato nel periodo t 0 altrimenti

u

j

=

( 1 se il job j termina oltre la sua due date 0 altrimenti

Funzione obiettivo

min X

j ∈J

w

_j

u

_j

(41)

Formulazione y jt

Variabili di decisione

y

_jt

=

( 1 se il job j viene processato nel periodo t 0 altrimenti

u

j

=

( 1 se il job j termina oltre la sua due date 0 altrimenti

Funzione obiettivo

min X

j ∈J

w

_j

u

_j

(42)

Formulazione y jt

Vincoli

I

ciascun job j deve essere processato in esattamente p

_j

istanti

T

X

t=rj+1

y

jt

= p

j

∀j ∈ J

I

durante il periodo t al pi` u un job pu` o essere in esecuzione

X

j ∈J

y

_jt

≤ 1 ∀t = 1, . . . , T

(43)

Formulazione y jt

Vincoli

I

ciascun job j deve essere processato in esattamente p

_j

istanti

T

X

t=rj+1

y

jt

= p

j

∀j ∈ J

I

durante il periodo t al pi` u un job pu` o essere in esecuzione

X

j ∈J

y

_jt

≤ 1 ∀t = 1, . . . , T

(44)

Formulazione y jt

Vincoli

I

ciascun job j deve essere processato in esattamente p

_j

istanti

T

X

t=rj+1

y

jt

= p

j

∀j ∈ J

I

durante il periodo t al pi` u un job pu` o essere in esecuzione

X

j ∈J

y

_jt

≤ 1 ∀t = 1, . . . , T

(45)

Formulazione y jt

Vincoli

I

il processamento deve avvenire in periodi contigui (non

`

e ammessa preemption)

C

j

= p

j

2 + 1 p

_j

T

X

t=rj+1

t − 1

2 y

jt

I

un job ` e in ritardo se termina oltre la sua due date T · u

_j

≥ C

_j

− d

_j

∀j ∈ J

I

y

_jt

∈ {0, 1} ∀j ∈ J , t = r

_j

+ p

_j

, . . . , T

I

u

_j

∈ {0, 1} ∀j ∈ J

(46)

Formulazione y jt

Vincoli

I

il processamento deve avvenire in periodi contigui (non

`

e ammessa preemption)

C

j

= p

j

2 + 1 p

_j

T

X

t=rj+1

t − 1

2 y

jt

I

un job ` e in ritardo se termina oltre la sua due date

T · u

_j

≥ C

_j

− d

_j

∀j ∈ J

I

y

_jt

∈ {0, 1} ∀j ∈ J , t = r

_j

+ p

_j

, . . . , T

I

u

_j

∈ {0, 1} ∀j ∈ J

(47)

Formulazione y jt

Vincoli

I

il processamento deve avvenire in periodi contigui (non

`

e ammessa preemption)

C

j

= p

j

2 + 1 p

_j

T

X

t=rj+1

t − 1

2 y

jt

I

un job ` e in ritardo se termina oltre la sua due date T · u

_j

≥ C

_j

− d

_j

∀j ∈ J

I

y

_jt

∈ {0, 1} ∀j ∈ J , t = r

_j

+ p

_j

, . . . , T

I

u

_j

∈ {0, 1} ∀j ∈ J

(48)

Formulazione y jt : resume

minX

j ∈J w_ju_j

XT t=rj +1

y_jt= p_j ∀j ∈ J

X j ∈J

y_jt≤ 1 ∀t = 1, . . . , T

C_j=p_j 2 + 1

p_j XT t=rj +1

t −1

2

y_jt ∀j ∈ J

T · u_j≥ C_j− d_j ∀j ∈ J

y_jt∈ {0, 1} ∀j ∈ J , t = r_j+ p_j, . . . , T

u_j∈ {0, 1} ∀j ∈ J

(49)

Formulazione y jt : resume

minX

j ∈J w_ju_j

XT t=rj +1

X j ∈J

y_jt≤ 1 ∀t = 1, . . . , T

C_j=p_j 2 + 1

p_j XT t=rj +1

t −1

2

y_jt ∀j ∈ J

T · u_j≥ C_j− d_j ∀j ∈ J

y_jt∈ {0, 1} ∀j ∈ J , t = r_j+ p_j, . . . , T

u_j∈ {0, 1} ∀j ∈ J

DOMANDA

Come modifichereste la precedente formulazione per ammettere la

preemption?

(50)

Formulazione y jt : resume

minX

j ∈J w_ju_j

XT t=rj +1

X j ∈J

y_jt≤ 1 ∀t = 1, . . . , T

C_j=p_j 2 + 1

p_j XT t=rj +1

t −1

2

y_jt ∀j ∈ J

T · u_j≥ C_j− d_j ∀j ∈ J

y_jt∈ {0, 1} ∀j ∈ J , t = r_j+ p_j, . . . , T

u_j∈ {0, 1} ∀j ∈ J

ESERCIZIO

Data l’istanza del problema di scheduling dell’esempio precedente,

utilizzando le variabili y

jt

, formulare il problema 1|| P w

j

T

j

(51)

Indetical Parallel Machine: notazione

I

Si vuole formulare il seguente problema:

P

_m

| | X T

_j

I

in cui:

I

Insieme dei job: J = {1, . . . , n}

I

Insieme delle macchine (identiche): M = {1, . . . , m}

I

Per ogni job j:

I pj: tempo di processamento, indipendente dalla macchina su cui j viene eseguito

I dj: due date

(52)

Formulazione posizionale: P m | | P T j

Variabili di decisione

x

_jh^k

=

( 1 se j ` e processato sulla macchina h in posizione k 0 altrimenti

Vincoli del problema

I

Ciascun job deve essere schedulato, ininterrottamente, esattamente una volta

I

Ciascuna macchina pu` o processare, al pi` u, un job per

volta

Formulazioni di PLI per problemi di scheduling