F o rm u la z io n i d i P L I p e r p ro b le m i d i sc h e d u li n g

DipartimentodiInformatica UniversitàdegliStudi–L’Aquila –Italy salvatore.nocella@di.univaq.it http://www.oil.di.univaq.it

F o rm u la z io n i d i P L I p e r p ro b le m i d i sc h e d u li n g

Sommario »Problemisusingolamacchina ›Formulazionedisgiuntiva ›Formulazionetime indexed »Macchineparalleleidentiche ›Formulazioneposizionale

Single-machine: notazione »Si vuoleformulareilseguenteproblemadi scheduling: »Datidel problema: ›Insiemedeijob J= {1, …, n} ›Per ognijob j: -w jpeso -p jtempo diprocessamento -C jtempo dicompletamento -d jdue date

11//

n jj jwC =∑

Formulazionedisgiuntiva »Sceltadellavariabile: ›tempo diiniziodel job j, j=1, …, n »Vincolodisgiuntivo: ›Comunquescelgounacoppiadijob distintij, k oppure »Attenzione! Siamointeressatia formulazioni diProgrammazioneLINEAREIntera

n jt∈ℝ jjktpt+≤ kkjtpt+≤

Formulazionedisgiuntiva »Definiamola seguentevariabiledi decisione: »Il vincolodisgiuntivoprecedentesiriscrive: dove Mèunacostantemolto grande

1 0jkjk α =  

seprecede altrimenti (1), jkkjjMttpjkJα−+−≥∀∈ (1), kjjkkMttpjkJα−+−≥∀∈

Formulazionedisgiuntiva st1min()

n jjj jwtp =+ ∑ (1), ijjiiMttpijJα−+−≥∀∈ , ijijjMttpijJα+−≥∀∈ 0 jtjJ≥∀∈ {0,1}, ijijJα∈∀∈

Identical Parallel-machine: notazione »Si vuoleformulareilseguenteproblemadi scheduling: »Datidel problema: ›Insiemedeijob J= {1, …, n} ›InsiemedimacchineM= {1,…, m} ›Per ognijob j: -p jtempo diprocessamente -d jdue date

1//

n mj jPT =∑

Identical Parallel-machine »Variabile di decisione »Vincoli del problema ›Ciascun job deve essere schedulato, ininterrottamente, esattamente una volta ›Ciascuna macchina può processare, al più, un job per volta

1 0

se è processato sulla macchina in posizione altrimenti

k hjjhk x = 

Identical Parallel-machine »Definiamopreliminarmente: ›t[k,h]: istantediiniziodel k-esimojob (ovverodel job in posizionek) sullamacchinah ›p[k,h]: duratadel k-esimojob sullamacchinah ›d[k,h]: due date del k-esimojob sullamacchinah »Funzioneobiettivo: [][][]() 11minmax0,,,,

nm khtkhpkhdkh ==+− ∑∑

Identical Parallel-machine 111

mn k ij ikxjJ ===∀∈ ∑∑ 1[,],1,...,

n k jhj jpkhpxhMkn ==∀∈= ∑ 1[,],1,...,

n k jhj jdkhdxhMkn ==∀∈= ∑ [,][1,][1,],1,...,tkhtkhpkhiMkn=−+−∀∈= [,]0,1,...,tkhhMkn≥∀∈=

[][][]() 11minmax0,,,,

nm khtkhpkhdkh ==+− ∑∑ [][][][],,,,Tkhtkhpkhdkh≥+− [],0Tkh≥[] 11min,

nm khTkh ==∑∑

FormulazioneTime-Indexed »L’orizzonte temporale Tèdiscretizzatoin periodi di durata unitaria. »Il periodo tconcidecon l’intervallo di tempo [t –1 , t] »Formuliamoilproblema: »Ipotesi:

11//

n jjj jrwC =∑ 1

n j jTp =≥

∑

FormulazioneTime-Indexed »Variabiledidecisione: »Definiamoc jtilcostodischedulareiljob j all’istantet:

1 0jtjt x =  

se inizia nel periodo altrimenti () jtjjctpw=+

st

FormulazioneTime-Indexed 1 11min

jTpn jtjt jtcx

−+ ==∑∑ 11,,

j j

Tp jt trxjn

− ==∀= ∑… 1111,, j

nt js jstpxtT ==−+≤∀= ∑∑… {}0,11,;1,,1 jtjxjntTp∈∀==−+……

FormulazioneTime-Indexed: proprietà »Svantaggi: ›Dimensione del modello: nTvariabili, n+Tvincoli »Vantaggi: ›E’possibilemodellarefacilmentediverse funzioniobiettivo ed alcuneclassidivincoli(machine availability, precedenze, …) ›Qualitàdel gap molto buono ›Struttura di alcune facce massimali conosciuta ›Riconducibilitàa problemi di ottimizzazione combinatori già studiati »Principali metodi risolutivi investigati (in letteratura): ›Branch-and-cut ›Columngeneration