Teoria orarului

Secvențierea și planificarea sunt forme de procese de luare a deciziilor, „luarea deciziilor”, care constau în alocarea resurselor finite în așa fel încât o anumită țintă să fie optimizată. Exemple tipice de resurse limitate sunt mașinile unei întreprinderi producătoare, orele săptămânale de muncă ale asistentelor medicale într-un spital sau angajate într-un magazin, pante de aterizare-decolare ale unui aeroport , în timp ce exemple de obiective sunt optimizarea timpului pentru finalizarea unui proiect , timpul de așteptare al unui avion în zbor sau o mulțime de muncă în fața unei mașini de lucru , costul orelor suplimentare, costul penalităților pentru întârzierea livrării unui produs-serviciu-muncă.

Distincția dintre secvențiere și planificare constă în faptul că prima are legătură doar cu ordonarea operațiunilor de efectuat, în timp ce cea din urmă sincronizează și cronometrează succesiunea operațiilor. Programarea conține, de asemenea, informații temporale care specifică calendarul activităților individuale, prin urmare, în general, programarea include secvențierea. O problemă de secvențiere sau planificare conține următoarele informații:

variabilele de decizie
criteriul prin care sunt evaluate variabilele de decizie (măsura performanței)
regiunea fezabilă în care variabilele de decizie pot varia

O soluție la o problemă, secvență sau programare constă în identificarea deciziei optime în sensul specificat de criteriul particular adoptat. Secvența specifică numai ordinea operațiunilor-activități care urmează să fie efectuate, în timp ce programul specifică, de asemenea, orele de început și sfârșit ale fiecărei activități-operații.

Secvențierea

Problemele de secvențiere apar ori de câte ori este necesar să se decidă ordinea în care ar trebui să se desfășoare un anumit număr de activități, „sarcină”. Exemple de probleme de secvențializare sunt avioanele în aer care așteaptă permisiunea de a ateriza sau de a decola, clienții stau la coadă în fața unei uși sau așteaptă la telefon câteva call-center , programele unui computer pentru a fi executate o unitate de calcul, loturile pentru a fi prelucrate la bordul unei anumite mașini de operare, rundele de livrări de către o companie de distribuție, diferitele meciuri de țiței prin distilare într-o rafinărie . Numitorul comun al problemelor de secvențiere este timpul interpretat ca o resursă limitată care trebuie alocată într-un mod optim și, în general, rezoluția lor constă în determinarea permutării variabilelor de decizie, astfel încât timpul să fie minimizat. În cele din urmă, o problemă de secvențiere este o problemă de optimizare combinatorie. De exemplu, în problema de bază a secvențierii n loturi pentru o singură mașină, numărul de secvențe distincte eligibile este egal cu n! adică numărul de permutări diferite de n elemente.

Clasificarea problemelor de programare

Pentru a clasifica marea varietate de probleme de planificare, se folosește o notație folosind trei câmpuri $\alpha |\beta |\gamma$ ${\ displaystyle \ alpha | \ beta | \ gamma}$ ${\ displaystyle \ alpha | \ beta | \ gamma}$ care reflectă caracteristicile mașinilor, operațiuni și specifică măsura de performanță pentru a evalua programul, notația pentru problemele de programare . Mașinile sunt clasificate în paralel dacă sunt capabile să efectueze aceleași operațiuni; Ei spun că sunt dedicați dacă sunt specializați în executarea unor operațiuni specifice și anume. Trei tipuri de mașini paralele sunt identificate pe baza vitezei lor: identice dacă viteza de execuție a operației este aceeași; uniformă dacă viteza dintre mașini este diferită, dar viteza fiecărei mașini rămâne constantă indiferent de operația pe care o efectuează; necorelat dacă viteza depinde de operația care trebuie efectuată.

În cazul mașinilor dedicate, există trei modele pentru a efectua clase specifice de operațiuni: magazin de flux, magazin deschis și magazin de locuri de muncă. Să presupunem că anumite clase de operații pot fi grupate în seturi numite joburi și că două operațiuni aparținând aceluiași job sunt considerate diferite dacă trebuie efectuate pe mașini diferite. În magazinul deschis numărul de operații este constant pentru fiecare lucrare și fiecare operație este efectuată, fără constrângeri de prioritate, de către mașina dedicată acestuia: nu există o ordine specială de urmat și, prin urmare, un program determină nu numai ordinea de execuție a operații de către mașini, dar și sortarea lucrărilor între mașini. Magazinul de fluxuri diferă de magazinul deschis pentru faptul că introducem constrângerile de prioritate între operațiuni și, prin urmare, este de a crea o ordonare naturală a mașinilor.

În fluxul de procesare al magazinului de locuri de muncă nu este unidirecțional ca în magazinul de fluxuri și numărul de tranzacții variază în mod arbitrar între un loc de muncă și celălalt. Trebuie remarcat faptul că, de obicei, se presupune că între mașini există un spațiu de stocare, „tampon”, cu capacitate nelimitată. Astfel, tamponul face posibil ca un lot tocmai procesat de o singură mașină să aștepte începutul procesării pe următoarea mașină. Dacă bufferul are o capacitate zero, atunci loturile nu au spațiul de așteptare între două mașini adiacente și, în consecință, nicio variabilă de timp de așteptare nu poate lua o valoare non-nulă: un lot care tocmai a terminat o operațiune trebuie să înceapă imediat procesarea pe următoarea mașină .

Problemă de secvențiere cu o singură mașină

Indiferent dacă este atribuit unei mașini și unui set de n elemente care trebuie procesate la bord. Fiecare procesare necesită un anumit timp, nu poate fi întreruptă (nu preempțiune) și nu necesită timp de configurare (configurare), dacă există un timp de prelucrare, se presupune că nu depinde de ordinea loturilor de procesat: dacă timpul de configurare depinde doar de la un anumit lot poate fi apoi inclus în timpul de procesare al aceluiași lot. Mai mult, se presupune că loturile sunt disponibile pentru procesare în același timp sau că mașina poate începe procesarea cu oricare dintre ele. Problema secvențierii pentru o singură mașină este de a determina ordinea în care loturile urmează să fie procesate în așa fel încât să se minimizeze unul dintre următoarele criterii de evaluare:

timpul mediu de finalizare a loturilor, „ timpul de finalizare ”
timpul mediu de curgere, „timpul mediu de curgere ”
timpul total de așteptare a loturilor din coada de la mașină, „ timpul de așteptare ”
întârzierea totală medie comparativ cu datele de livrare fixate pentru fiecare lot, „ întârziere medie ”
întârzierea maximă între loturi, „ întârzierea maximă la locul de muncă ”

Principalele rezultate ale teoriei planificării pentru o singură mașină sunt prezentate mai jos.

Timpul mediu de curgere este minimizat prin ordonarea tuturor articolelor în ordinea descrescătoare a timpului de proces (SPT- Timpul de procesare cel mai scurt ).

Amintind că numărul mediu de stocuri dintr-un sistem este direct proporțional cu timpul mediu de curgere, rezultă că secvența care minimizează timpul mediu de curgere minimizează și numărul mediu de stocuri dintr-un sistem; prin urmare, SPT rezolvă și problema minimizării stocurilor de depozite și a costurilor aferente.

Următoarele măsuri de performanță sunt echivalente: timpul mediu de finalizare a lotului, timpul mediu de curgere, timpul total de așteptare al loturilor la coadă la mașină, întârzierea totală medie.

Această teoremă înseamnă că, dacă o secvență este optimă pentru un criteriu, atunci este optimă și pentru criteriile rămase.

Dacă loturile sunt supuse termenelor de livrare (două date), atunci li se aplică următoarea regulă de încărcare:

Întârzierea maximă între loturi este minimizată prin comandarea tuturor articolelor în ordinea de livrare nedescendentă (EDD - Data scadenței anticipate).

În plus față de situația flagrantă a unui departament de producție care prezintă o singură mașină, există numeroase cazuri în care plantele se comportă ca o singură mașină: gândiți-vă la industria chimică și de proces în care întreaga fabrică este un set integrat de procese. pe numeroase elemente diferite în succesiune. Într-un sistem de producție cu mai multe mașini, se poate întâmpla să existe o mașină cu cea mai mică capacitate de producție și să fie denumită blocaj, deoarece departamentul este „dominat” de această mașină. Rezultă că optimizarea procesului de producție pentru un mediu cu mai multe mașini poate fi simplificată într-o problemă de programare pentru mașina de blocaj: secvența de lot atribuită blocajului va determina performanța întregului sistem.

Dacă se presupune că momentul configurării depinde de succesiunea loturilor, atunci este în prezența unei probleme de planificare, deoarece finalizarea timpului n loturilor depinde de cât de eficient sunt sortate loturile. Soluția sa este un program care minimizează n timpii de configurare. Exemplul tipic al unei activități dependente de configurare se găsește în departamentele de vopsire sau turnare sub presiune pentru piese din PVC colorat: ori de câte ori culoarea se schimbă, buncărul care conține culoarea trebuie înlocuit și mașina de turnat prin injecție trebuie curățată de orice culoare reziduală. În practică, se preferă trecerea de la culori deschise la culori închise, deoarece timpul de curățare este mai scurt.

Problemă de programare a magazinului de fluxuri

Trebuie efectuate m mașini alocate și un set de n loturi, pe ultimele m procese: fiecare mașină este dedicată realizării unui singur proces. Fiecare proces necesită un anumit timp, nu poate fi întrerupt (nu preempțiune) și poate fi efectuat de fiecare mașină pe rând. Un flux-magazin este o configurație de mașini pentru care fluxul de lot este unidirecțional, liniar și urmează aceeași ordine de la o mașină la alta, mai exact dacă un lot trebuie procesat mai întâi pe o mașină și apoi pe alta. Ordinea de lucru este validă pentru toate loturile, în plus, dacă o mașină funcționează un lot înainte de alta, această comandă a loturilor este păstrată pentru toate mașinile rămase. Prin urmare, un magazin de flux conține o comandă naturală a mașinilor. Dacă a priori nu există constrângeri de prioritate între diferitele loturi, o problemă de planificare pentru un magazin de fluxuri constă în găsirea secvenței de loturi care minimizează timpul de finalizare a tuturor proceselor sau timpul de întârziere generală sau timpul maxim de curgere.

Mașini paralele

Să presupunem că există m resurse paralele, adică că există m mașini disponibile pentru a funcționa simultan în n loturi, toate gata să fie procesate la momentul zero. În plus, presupuneți că fiecare lot poate fi procesat de cel mult o mașină. Problema constă în alocarea atât a resurselor, cât și în planificarea loturilor. Resursele pot consta din: mașini identice, uniforme sau fără legătură. Mașinile identice au același timp de procesare între ele, mașinile uniforme au timpi de procesare proporționale între ele, în cele din urmă, mașinile fără legătură au timpi de proces care variază într-un mod complet arbitrar.

Indicat cu termenul makepan timpul scurs între începutul procesării primului lot și finalizarea ultimului lot, în problema unei singure mașini cu secvențe independente de set-up această cantitate este o constantă, adică nu depinde de secvența particulară adoptată. În cazul mașinilor paralele, fațada este variabilă și, prin urmare, poate fi utilizată ca indicator de performanță. În general, o problemă de programare cu mașini paralele poate fi rezolvată în două faze, în special pentru situații cu un număr mare de combinații: într-o primă fază, loturile sunt alocate în modul cel mai echitabil, cât mai uniform posibil între toate mașinile și apoi pentru fiecare mașină secvența optimă este determinată separat. O formulare de programare liniară a problemei pentru mașini identice fără posibilitatea de preempiton este următoarea:

Funcție obiectivă:

minC_{max}

{\ displaystyle minC_ {max}}

{\ displaystyle minC_ {max}}

sub rezerva următoarelor constrângeri:

\left\{{\begin{array}{l}C_{max}-\sum _{i=1}^{n}x_{i,1}\cdot \ p_{i}\geq 0\\\vdots \\C_{max}-\sum _{i=1}^{n}x_{i,m}\cdot \ p_{i}\geq 0\\\sum _{i=1}^{n}x_{i,k}=1\forall \ k\\\sum _{k=1}^{n}x_{i,k}=1\forall \ i\\x_{i,k}\in \left\{0;1\right\}\forall \ i,k\end{array}}\right.

{\ displaystyle \ left \ {{\ begin {array} {l} C_ {max} - \ sum _ {i = 1} ^ {n} x_ {i, 1} \ cdot \ p_ {i} \ geq 0 \ \\ vdots \\ C_ {max} - \ sum _ {i = 1} ^ {n} x_ {i, m} \ cdot \ p_ {i} \ geq 0 \\\ sum _ {i = 1} ^ { n} x_ {i, k} = 1 \ forall \ k \\\ sum _ {k = 1} ^ {n} x_ {i, k} = 1 \ forall \ i \\ x_ {i, k} \ in \ left \ {0; 1 \ right \} \ forall \ i, k \ end {array}} \ right.}

{\ displaystyle \ left \ {{\ begin {array} {l} C_ {max} - \ sum _ {i = 1} ^ {n} x_ {i, 1} \ cdot \ p_ {i} \ geq 0 \ \\ vdots \\ C_ {max} - \ sum _ {i = 1} ^ {n} x_ {i, m} \ cdot \ p_ {i} \ geq 0 \\\ sum _ {i = 1} ^ { n} x_ {i, k} = 1 \ forall \ k \\\ sum _ {k = 1} ^ {n} x_ {i, k} = 1 \ forall \ i \\ x_ {i, k} \ in \ left \ {0; 1 \ right \} \ forall \ i, k \ end {array}} \ right.}

Când este permisă preempțiunea, procesarea unui lot poate fi întreruptă, iar prelucrarea rămasă poate fi efectuată ulterior, poate pe o altă mașină. Pentru a modela preempțiunea, este suficient să eliminați, în jargon, constrângerea de integritate pentru variabilele de decizie $x_{i,j}$ ${\ displaystyle x_ {i, j}}$ ${\ displaystyle x_ {i, j}}$ și înlocuiți-l cu $x_{i,j}\geq 0\forall \ i,j$ ${\ displaystyle x_ {i, j} \ geq 0 \ forall \ i, j}$ ${\ displaystyle x_ {i, j} \ geq 0 \ forall \ i, j}$ . Rețineți că modelul nu oferă un program de timp, ci pur și simplu împărțirea loturilor între mașini pentru a reduce la minimum viteza.

Problemă de programare a magazinului de locuri de muncă

Luați în considerare un sistem de producție format din m mașini care să fie utilizate pentru a lucra n loturi: în problemele de programare a magazinului de lucru, fluxul de lucru nu este unidirecțional și fiecare lot are exact m operații de efectuat, una pentru fiecare mașină. Acest lucru înseamnă că secvența operațiunilor nu este definită prin ordonarea mașinilor ca în magazinul de curgere: nu există nici o mașină k-a dedicată numai efectuării mașinii k-a pe fiecare lot; de aceea este necesar să se caracterizeze fiecare proces cu trei indici care specifică lotul, mașina și operațiunea. Atribuirea operațiilor către mașini pentru un lot dat reprezintă rutare sau cale, în jargonul de rutare, a lotului în sine.

Metode de rezoluție

În general, găsirea soluției optime la o problemă de planificare necesită enumerarea tuturor soluțiilor posibile și selectarea celei mai bune. Metodele de rezoluție sunt clasificate în două macro-clase: metodele exacte și metodele euristice. Metodele exacte sunt împărțite la rândul lor în:

Metode constructive: o soluție optimă este construită pe baza datelor problemei, urmând o serie de reguli simple de prioritate. Un exemplu este regulile de prioritate SPT și EDD.
Metode enumerative: sunt enumerate toate soluțiile posibile, cele care nu sunt optime sunt eliminate din listă și se selectează cel mai bun program. Programarea dinamică constă în descompunerea problemei în subprobleme mai mici care sunt rezolvate recursiv pentru a reduce timpul de calcul: soluția găsită pentru fiecare subproblemă contribuie la soluționarea următoarei probleme până la soluționarea problemei inițiale. Modelarea în formă stilizată a problemelor de planificare ca programe liniare, pe de altă parte, permite obținerea soluției optime prin intermediul algoritmilor exacți.

Cu toate acestea, abordarea exactă a metodei se aplică numai problemelor cu un număr mic de loturi, în timp ce în realitate problemele sunt mari și, prin urmare, nu pot fi rezolvate exact cu timpi de calcul rezonabili. Prin urmare, se recurge la metode de soluționare euristică a căutării locale, cum ar fi căutarea tabu , recușirea simulată , algoritmii genetici . Metodele euristice nu garantează o soluție optimă la problemă, deoarece scopul lor este de a găsi o soluție rezonabilă într-un timp relativ scurt.

Reprezentarea timpului

Reprezentarea timpului este un subiect fundamental în problemele de programare. Formulările matematice ale problemelor de planificare pot fi clasificate în două macro-categorii pe baza tipului de reprezentare adoptat pentru a descrie trecerea timpului. O categorie reprezintă timpul ca o cantitate discretă; cealaltă ca magnitudine continuă. În cazul discret, ideea de bază este discretizarea timpului luând în considerare un set finit de instanțe: $t_{j+1}=t_{j}+h_{j}$ ${\ displaystyle t_ {j + 1} = t_ {j} + h_ {j}}$ ${\ displaystyle t_ {j + 1} = t_ {j} + h_ {j}}$ cu $j=0,1,...,T-1$ ${\ displaystyle j = 0,1, ..., T-1}$ ${\ displaystyle j = 0,1, ..., T-1}$ ; $h_{j}$ ${\ displaystyle h_ {j}}$ ${\ displaystyle h_ {j}}$ reprezintă etapa de discretizare. Cea mai naturală alegere este de a lua în considerare pașii $h_{j}$ ${\ displaystyle h_ {j}}$ ${\ displaystyle h_ {j}}$ constante, adică $h_{j}=h$ ${\ displaystyle h_ {j} = h}$ ${\ displaystyle h_ {j} = h}$ pentru $j=0,1,...$ ${\ displaystyle j = 0,1, ...}$ ${\ displaystyle j = 0,1, ...}$ În acest fel, orizontul de timp este împărțit într-un anumit număr de intervale de durată egală și constantă: în general, numărul de ferestre de timp și poziționarea lor sunt postulate a priori. Evenimentele care apar în modelul matematic discret nu sunt altceva decât variații ale valorii unei variabile; astfel de evenimente pot apărea numai la extremele unuia dintre intervalele cu care se împarte orizontul de timp, adică la începutul sau la sfârșitul intervalului în sine. Pe de altă parte, în cazul continuu, evenimentele pot apărea în orice moment al continuumului temporal, astfel încât se poate spune că într-un astfel de context valoarea punctelor evenimentului nu este cunoscută a priori, ceea ce se postulează este un anumit număr a variabilelor temporale adecvate.

Modele de programare liniară

Mașină unică

În tabelul de mai jos oferim formularea în termeni de programare liniară a unei probleme de secvențiere generică la o mașină. Dat fiind n loturi care trebuie secvențiate, se introduc n variabile non-negative $A_{i}$ ${\ displaystyle A_ {i}}$ $Către}$ și $n^{2}$ ${\ displaystyle n ^ {2}}$ $n ^ {2}$ variabile binare $x_{i,j}$ ${\ displaystyle x_ {i, j}}$ ${\ displaystyle x_ {i, j}}$ , în total variabilele care trebuie gestionate pentru o problemă cu n loturi sunt $n+n^{2}$ ${\ displaystyle n + n ^ {2}}$ ${\ displaystyle n + n ^ {2}}$ .

$A_{i}$ ${\ displaystyle A_ {i}}$ $Către}$ : indică timpul de așteptare între finalizarea lotului în poziția i-1 și începutul procesării următorului lot în poziția i-a

$p_{k}$ ${\ displaystyle p_ {k}}$ ${\ displaystyle p_ {k}}$ : este momentul procesării lotului k-th

$r_{k}$ ${\ displaystyle r_ {k}}$ ${\ displaystyle r_ {k}}$ : este momentul în care lotul k-lea este disponibil pentru procesare (timp de pregătire)

$x_{1,1}$ ${\ displaystyle x_ {1,1}}$ ${\ displaystyle x_ {1,1}}$ , ..., $x_{1,n}$ ${\ displaystyle x_ {1, n}}$ ${\ displaystyle x_ {1, n}}$ , ..., $x_{n,1}$ ${\ displaystyle x_ {n, 1}}$ ${\ displaystyle x_ {n, 1}}$ , ..., $x_{n,n}$ ${\ displaystyle x_ {n, n}}$ ${\ displaystyle x_ {n, n}}$ : $n^{2}$ ${\ displaystyle n ^ {2}}$ $n ^ {2}$ variabile binare asociate cu n loturi

Prin urmare, pentru fiecare lot sunt introduse n variabile binare $x_{i,j}$ ${\ displaystyle x_ {i, j}}$ ${\ displaystyle x_ {i, j}}$ care indică poziția lotului în secvența optimă. Șirul $x_{i,1}=0$ ${\ displaystyle x_ {i, 1} = 0}$ ${\ displaystyle x_ {i, 1} = 0}$ , ..., $x_{i,k}=1$ ${\ displaystyle x_ {i, k} = 1}$ ${\ displaystyle x_ {i, k} = 1}$ , ..., $x_{i,n}=0$ ${\ displaystyle x_ {i, n} = 0}$ ${\ displaystyle x_ {i, n} = 0}$ înseamnă că lotul I este prelucrat în poziția k. Soluția problemei secvențiale optime constă tocmai în valoarea acestor variabile binare.

Funcție obiectivă:

min\left\{\sum _{i=1}^{n}A_{i}+\sum _{i=1}^{n}x_{i,n}\cdot \ p_{i}\right\}

{\ displaystyle min \ left \ {\ sum _ {i = 1} ^ {n} A_ {i} + \ sum _ {i = 1} ^ {n} x_ {i, n} \ cdot \ p_ {i} \ dreapta \}}

{\ displaystyle min \ left \ {\ sum _ {i = 1} ^ {n} A_ {i} + \ sum _ {i = 1} ^ {n} x_ {i, n} \ cdot \ p_ {i} \ dreapta \}}

sub rezerva următoarelor constrângeri:

\left\{{\begin{array}{l}A_{1}=\sum _{i=1}^{n}x_{i,1}\cdot \ r_{i}\\A_{2}=A_{1}+\sum _{i=1}^{n}x_{i,2}\cdot \ r_{i}+\sum _{i=1}^{n}x_{i,1}\cdot \ p_{i}\\\vdots \\A_{n}=A_{n-1}+\sum _{i=1}^{n}x_{i,n}\cdot \ r_{i}+\sum _{i=1}^{n}x_{i,n-1}\cdot \ p_{i}\\\sum _{i=1}^{n}x_{i,k}=1\forall \ k\\\sum _{k=1}^{n}x_{i,k}=1\forall \ i\\A_{i}\geq 0\forall \ i\\x_{i,k}\in \left\{0;1\right\}\forall \ i,k\end{array}}\right.

{\ displaystyle \ left \ {{\ begin {array} {l} A_ {1} = \ sum _ {i = 1} ^ {n} x_ {i, 1} \ cdot \ r_ {i} \\ A_ { 2} = A_ {1} + \ sum _ {i = 1} ^ {n} x_ {i, 2} \ cdot \ r_ {i} + \ sum _ {i = 1} ^ {n} x_ {i, 1} \ cdot \ p_ {i} \\\ vdots \\ A_ {n} = A_ {n-1} + \ sum _ {i = 1} ^ {n} x_ {i, n} \ cdot \ r_ { i} + \ sum _ {i = 1} ^ {n} x_ {i, n-1} \ cdot \ p_ {i} \\\ sum _ {i = 1} ^ {n} x_ {i, k} = 1 \ forall \ k \\\ sum _ {k = 1} ^ {n} x_ {i, k} = 1 \ forall \ i \\ A_ {i} \ geq 0 \ forall \ i \\ x_ {i , k} \ in \ left \ {0; 1 \ right \} \ forall \ i, k \ end {array}} \ right.}

{\ displaystyle \ left \ {{\ begin {array} {l} A_ {1} = \ sum _ {i = 1} ^ {n} x_ {i, 1} \ cdot \ r_ {i} \\ A_ { 2} = A_ {1} + \ sum _ {i = 1} ^ {n} x_ {i, 2} \ cdot \ r_ {i} + \ sum _ {i = 1} ^ {n} x_ {i, 1} \ cdot \ p_ {i} \\\ vdots \\ A_ {n} = A_ {n-1} + \ sum _ {i = 1} ^ {n} x_ {i, n} \ cdot \ r_ { i} + \ sum _ {i = 1} ^ {n} x_ {i, n-1} \ cdot \ p_ {i} \\\ sum _ {i = 1} ^ {n} x_ {i, k} = 1 \ forall \ k \\\ sum _ {k = 1} ^ {n} x_ {i, k} = 1 \ forall \ i \\ A_ {i} \ geq 0 \ forall \ i \\ x_ {i , k} \ in \ left \ {0; 1 \ right \} \ forall \ i, k \ end {array}} \ right.}

Suma $\sum _{i=1}^{n}x_{i,k}\cdot \ p_{i}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} x_ {i, k} \ cdot \ p_ {i}}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} x_ {i, k} \ cdot \ p_ {i}}$ reprezintă timpul de procesare a k-a lotului într-o poziție optimă pe mașină. Suma $\sum _{i=1}^{n}x_{i,k}\cdot \ r_{i}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} x_ {i, k} \ cdot \ r_ {i}}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} x_ {i, k} \ cdot \ r_ {i}}$ reprezintă momentul în care lotul k este gata pentru procesare. Constrângerea non-simultaneității proceselor este $\sum _{i=1}^{n}x_{i,k}=1$ ${\ displaystyle \ sum _ {i = 1} ^ {n} x_ {i, k} = 1}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} x_ {i, k} = 1}$ , o ecuație care necesită ca unul și un singur lot să fie procesat în poziția k. Constrângerea de neeligibilitate a preempțiunii este $\sum _{k=1}^{n}x_{i,k}=1$ ${\ displaystyle \ sum _ {k = 1} ^ {n} x_ {i, k} = 1}$ ${\ displaystyle \ sum _ {k = 1} ^ {n} x_ {i, k} = 1}$ , ecuație care impune că lotul i este atribuit unei singure poziții. Rețineți că pentru $r_{k}=0$ ${\ displaystyle r_ {k} = 0}$ ${\ displaystyle r_ {k} = 0}$ pentru fiecare k ducem înapoi la problema în care loturile sunt toate disponibile pentru a fi procesate în momentul inițial 0.

Programare în prezența timpilor de configurare dependenți de secvență

Presupunând că timpul de configurare pentru a pregăti o mașină să proceseze următorul lot este independent de lotul care l-a precedat imediat, permite includerea timpului de configurare în timpul de procesare a lotului, $p_{i}$ ${\ displaystyle p_ {i}}$ ${\ displaystyle p_ {i}}$ . În cele ce urmează, se presupune ipoteza dependenței timpilor de configurare de secvență. Timpii de configurare sunt notați ca $s_{i,j}$ ${\ displaystyle s_ {i, j}}$ ${\ displaystyle s_ {i, j}}$ , notație care reprezintă timpul pentru a echipa o mașină să funcționeze lotul j când mașina a fost configurată pentru a lucra lotul i. În programarea unei singure mașini, minimizarea timpului maxim de curgere sau a vitezei de lucru este echivalentă cu minimizarea sumei tuturor timpilor de configurare. Problema minimizarea sumei totale de ori set-up este echivalentă cu problema de călătorie agent de vânzări, în jargon problema comis - voiajorului . Dacă o mulțime este potrivită cu fiecare oraș și timpul de configurare pentru a echipa mașina de la un lot la altul se potrivește cu fiecare distanță dintre două orașe, atunci echivalența celor două probleme devine evidentă.

Exemplu discret de programare a timpului pentru o singură mașină

Alegerea numărului de intervale de timp cu care se împarte orizontul de planificare se face în prealabil. Ca etapă de discretizare a timpului, puteți alege unitatea de timp utilizată pentru a reprezenta timpii de procesare. Pentru fiecare interval de timp introdus, acestea sunt definite $n$ ${\ displaystyle n}$ $n$ variabile binare pentru a indica intervalul de timp în care lotul începe procesarea. Variabilele sunt de formă $x_{i,j}$ ${\ displaystyle x_ {i, j}}$ ${\ displaystyle x_ {i, j}}$ unde indicele $i=1,...,n$ ${\ displaystyle i = 1, ..., n}$ ${\ displaystyle i = 1, ..., n}$ indică lotul și indicele $j=1,...,T$ ${\ displaystyle j = 1, ..., T}$ ${\ displaystyle j = 1, ..., T}$ indică intervalul de timp. Șirul generic $x_{i,1}=0,...,x_{i,t}=1,...,x_{i,T}=0$ ${\ displaystyle x_ {i, 1} = 0, ..., x_ {i, t} = 1, ..., x_ {i, T} = 0}$ ${\ displaystyle x_ {i, 1} = 0, ..., x_ {i, t} = 1, ..., x_ {i, T} = 0}$ indică faptul că primul lot începe procesarea la intervalul de timp $j=t$ ${\ displaystyle j = t}$ ${\ displaystyle j = t}$ . Soluția la problema optimă de secvențiere este valoarea acestor variabile binare. Două sau mai multe loturi nu pot fi procesate de aceeași mașină în aceeași fereastră de timp, prin urmare sunt introduse constrângeri pentru a preveni atribuirile conflictuale:

$\sum _{i=1}^{n}x_{i,j}\leq 1\forall \ j=1,...,T$ ${\ displaystyle \ sum _ {i = 1} ^ {n} x_ {i, j} \ leq 1 \ forall \ j = 1, ..., T}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} x_ {i, j} \ leq 1 \ forall \ j = 1, ..., T}$

În cele din urmă, constrângerile formei

$\sum _{j=1}^{T}x_{i,j}=1\forall \ i=1,...,n$ ${\ displaystyle \ sum _ {j = 1} ^ {T} x_ {i, j} = 1 \ forall \ i = 1, ..., n}$ ${\ displaystyle \ sum _ {j = 1} ^ {T} x_ {i, j} = 1 \ forall \ i = 1, ..., n}$

impun ca procesarea fiecărui lot să aibă loc o singură dată în orizontul de planificare, astfel se evită ca algoritmul soluției să propună soluția banală cu toate variabilele nule.

Faptul că nicio operațiune nu poate începe înainte de finalizarea procesării lotului anterior este reprezentat matematic de următoarele constrângeri T-1

\left\{{\begin{array}{l}\sum _{i=1}^{n}x_{i,1}\cdot \ p_{i}\leq \left(1-\sum _{i=1}^{n}x_{i,2}\right)\cdot \ M+1\\A_{1}-1+\sum _{i=1}^{n}x_{i,2}\cdot \ p_{i}\leq \left(1-\sum _{i=1}^{n}x_{i,3}\right)\cdot \ M+1\\\vdots \\A_{T-2}-1+\sum _{i=1}^{n}x_{i,T-1}\cdot \ p_{i}\leq \left(1-\sum _{i=1}^{n}x_{i,T}\right)\cdot \ M+1\\\end{array}}\right.

{\ displaystyle \ left \ {{\ begin {array} {l} \ sum _ {i = 1} ^ {n} x_ {i, 1} \ cdot \ p_ {i} \ leq \ left (1- \ sum _ {i = 1} ^ {n} x_ {i, 2} \ right) \ cdot \ M + 1 \\ A_ {1} -1+ \ sum _ {i = 1} ^ {n} x_ {i, 2} \ cdot \ p_ {i} \ leq \ left (1- \ sum _ {i = 1} ^ {n} x_ {i, 3} \ right) \ cdot \ M + 1 \\\ vdots \\ A_ {T-2} -1+ \ sum _ {i = 1} ^ {n} x_ {i, T-1} \ cdot \ p_ {i} \ leq \ left (1- \ sum _ {i = 1} ^ {n} x_ {i, T} \ right) \ cdot \ M + 1 \\\ end {array}} \ right.}

{\ displaystyle \ left \ {{\ begin {array} {l} \ sum _ {i = 1} ^ {n} x_ {i, 1} \ cdot \ p_ {i} \ leq \ left (1- \ sum _ {i = 1} ^ {n} x_ {i, 2} \ right) \ cdot \ M + 1 \\ A_ {1} -1+ \ sum _ {i = 1} ^ {n} x_ {i, 2} \ cdot \ p_ {i} \ leq \ left (1- \ sum _ {i = 1} ^ {n} x_ {i, 3} \ right) \ cdot \ M + 1 \\\ vdots \\ A_ {T-2} -1+ \ sum _ {i = 1} ^ {n} x_ {i, T-1} \ cdot \ p_ {i} \ leq \ left (1- \ sum _ {i = 1} ^ {n} x_ {i, T} \ right) \ cdot \ M + 1 \\\ end {array}} \ right.}

unde este $A_{1}=\sum _{i=1}^{n}x_{i,1}\cdot \ p_{i};A_{2}=A_{1}-1+\sum _{i=1}^{n}x_{i,2}\cdot \ p_{i};...$ ${\ displaystyle A_ {1} = \ sum _ {i = 1} ^ {n} x_ {i, 1} \ cdot \ p_ {i}; A_ {2} = A_ {1} -1+ \ sum _ { i = 1} ^ {n} x_ {i, 2} \ cdot \ p_ {i}; ...}$ ${\ displaystyle A_ {1} = \ sum _ {i = 1} ^ {n} x_ {i, 1} \ cdot \ p_ {i}; A_ {2} = A_ {1} -1+ \ sum _ { i = 1} ^ {n} x_ {i, 2} \ cdot \ p_ {i}; ...}$

Funcția obiectivă trebuie să se asigure că prelucrarea începe cât mai curând posibil, prin urmare se introduc coeficienți de cost care fac mai dificilă efectuarea prelucrării la sfârșitul orizontului de planificare.

Problemă cu datele de livrare

Pentru completitudine, oferă formularea în termeni de programare liniară a unei probleme generice de secvențiere a loturilor n atribuite cu date de livrare (două date). Pentru a ține cont de data livrării, se ia în considerare orice întârziere a livrărilor $\sum _{i=1}^{n}R_{i}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} R_ {i}}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} R_ {i}}$ provenite dintr-o secvență dată, în acest fel funcția obiectivă determină succesiunea loturilor astfel încât acestea să fie plătite în depozit pentru a respecta datele de livrare solicitate, în cazul întârzierilor, modelul matematic determină secvența care minimizează întârzierile.

$p_{i}$ ${\ displaystyle p_ {i}}$ ${\ displaystyle p_ {i}}$ : este momentul procesării lotului i

$C_{i}$ ${\ displaystyle C_ {i}}$ ${\ displaystyle C_ {i}}$ : indică timpul în care lotul i este finalizat

$t_{1},t_{2},\dots ,t_{n}$ ${\ displaystyle t_ {1}, t_ {2}, \ dots, t_ {n}}$ ${\ displaystyle t_ {1}, t_ {2}, \ dots, t_ {n}}$ : datele de livrare ale fiecărui lot care urmează să fie convertite în ore sau zile ca timp disponibil de la începutul programării

$T_{1},T_{2},\dots ,T_{n}$ ${\ displaystyle T_ {1}, T_ {2}, \ dots, T_ {n}}$ ${\ displaystyle T_ {1}, T_ {2}, \ dots, T_ {n}}$ : indică data livrării loturilor secvențiate, va fi calculată ca număr de ore / zile de la data programării până la data livrării solicitată de client

$R_{1},R_{2},\dots ,R_{n}$ ${\ displaystyle R_ {1}, R_ {2}, \ dots, R_ {n}}$ ${\ displaystyle R_ {1}, R_ {2}, \ dots, R_ {n}}$ : cuantificați orice întârziere

Funcție obiectivă:

min\left\{\sum _{i=1}^{n}C_{i}+\sum _{i=1}^{n}R_{i}\right\}

{\ displaystyle min \ left \ {\ sum _ {i = 1} ^ {n} C_ {i} + \ sum _ {i = 1} ^ {n} R_ {i} \ right \}}

{\ displaystyle min \ left \ {\ sum _ {i = 1} ^ {n} C_ {i} + \ sum _ {i = 1} ^ {n} R_ {i} \ right \}}

sub rezerva următoarelor constrângeri:

\left\{{\begin{array}{l}C_{1}=\sum _{i=1}^{n}x_{i,1}\cdot \ p_{i}\\C_{2}=C_{1}+\sum _{i=1}^{n}x_{i,2}\cdot \ p_{i}\\\vdots \\C_{n}=C_{n-1}+\sum _{i=1}^{n}x_{i,n}\cdot \ p_{i}\\T_{1}=\sum _{i=1}^{n}x_{i,1}\cdot \ t_{i}\\\vdots \\T_{n}=\sum _{i=1}^{n}x_{i,n}\cdot \ t_{i}\\R_{1}=C_{1}-T_{1}\\\vdots \\R_{n}=C_{n}-T_{n}\\\sum _{i=1}^{n}x_{i,k}=1\forall \ k\\\sum _{k=1}^{n}x_{i,k}=1\forall \ i\\C_{i}\geq 0\forall \ i\\x_{i,k}\in \left\{0;1\right\}\forall \ i,k\end{array}}\right.

{\ displaystyle \ left \ {{\ begin {array} {l} C_ {1} = \ sum _ {i = 1} ^ {n} x_ {i, 1} \ cdot \ p_ {i} \\ C_ { 2} = C_ {1} + \ sum _ {i = 1} ^ {n} x_ {i, 2} \ cdot \ p_ {i} \\\ vdots \\ C_ {n} = C_ {n-1} + \ sum _ {i = 1} ^ {n} x_ {i, n} \ cdot \ p_ {i} \\ T_ {1} = \ sum _ {i = 1} ^ {n} x_ {i, 1 } \ cdot \ t_ {i} \\\ vdots \\ T_ {n} = \ sum _ {i = 1} ^ {n} x_ {i, n} \ cdot \ t_ {i} \\ R_ {1} = C_ {1} -T_ {1} \\\ vdots \\ R_ {n} = C_ {n} -T_ {n} \\\ sum _ {i = 1} ^ {n} x_ {i, k} = 1 \ forall \ k \\\ sum _ {k = 1} ^ {n} x_ {i, k} = 1 \ forall \ i \\ C_ {i} \ geq 0 \ forall \ i \\ x_ {i , k} \ in \ left \ {0; 1 \ right \} \ forall \ i, k \ end {array}} \ right.}

{\ displaystyle \ left \ {{\ begin {array} {l} C_ {1} = \ sum _ {i = 1} ^ {n} x_ {i, 1} \ cdot \ p_ {i} \\ C_ { 2} = C_ {1} + \ sum _ {i = 1} ^ {n} x_ {i, 2} \ cdot \ p_ {i} \\\ vdots \\ C_ {n} = C_ {n-1} + \ sum _ {i = 1} ^ {n} x_ {i, n} \ cdot \ p_ {i} \\ T_ {1} = \ sum _ {i = 1} ^ {n} x_ {i, 1 } \ cdot \ t_ {i} \\\ vdots \\ T_ {n} = \ sum _ {i = 1} ^ {n} x_ {i, n} \ cdot \ t_ {i} \\ R_ {1} = C_ {1} -T_ {1} \\\ vdots \\ R_ {n} = C_ {n} -T_ {n} \\\ sum _ {i = 1} ^ {n} x_ {i, k} = 1 \ forall \ k \\\ sum _ {k = 1} ^ {n} x_ {i, k} = 1 \ forall \ i \\ C_ {i} \ geq 0 \ forall \ i \\ x_ {i , k} \ in \ left \ {0; 1 \ right \} \ forall \ i, k \ end {array}} \ right.}

Flow-shop a due macchine

In aggiunta si fornisce la formulazione in termini di programmazione lineare di un generico problema di tipo flow-shop a due macchine , l'estensione al caso con m macchine è immediata.

$p_{k,1}$ $p_{k,1}$ $p_{k,1}$ : è il tempo per la lavorazione del lotto k-esimo a bordo della macchina 1

$p_{k,2}$ $p_{k,2}$ $p_{k,2}$ : è il tempo per la lavorazione del lotto k-esimo a bordo della macchina 2

$C_{1,k}$ $C_{1,k}$ $C_{1,k}$ : indica il tempo di attesa per completare la lavorazione del lotto k-esimo sulla macchina 1

$C_{2,k-1}$ $C_{2,k-1}$ $C_{2,k-1}$ : indica il tempo di attesa per completare la lavorazione del lotto k-1 sulla macchina 2

$M_{i}$ $M_{i}$ $M_{i}$ : indica il tempo di attesa della macchina 2 per lavorare il lotto i-esimo affinché il lotto i-esimo venga completato sulla macchina precedente

$L_{i}$ $L_{i}$ $L_{i}$ : indica il tempo in coda del lotto i-esimo alla macchina 2 affinché questa termini la lavorazione del lotto precedente i-1

Funzione obiettivo:

min\left\{\sum _{i=2}^{n}L_{i}+\sum _{i=2}^{n}M_{i}\right\}

min\left\{\sum _{i=2}^{n}L_{i}+\sum _{i=2}^{n}M_{i}\right\}

min\left\{\sum _{i=2}^{n}L_{i}+\sum _{i=2}^{n}M_{i}\right\}

soggetta ai seguenti vincoli:

\left\{{\begin{array}{l}C_{1,1}=\sum _{i=1}^{n}x_{i,1}\cdot \ p_{i,1}\\C_{1,2}=C_{1,1}+\sum _{i=1}^{n}x_{i,2}\cdot \ p_{i,1}\\\vdots \\C_{1,n}=C_{1,n-1}+\sum _{i=1}^{n}x_{i,n}\cdot \ p_{i,1}\\C_{2,1}=C_{1,1}+\sum _{i=1}^{n}x_{i,1}\cdot \ p_{i,2}\\C_{2,2}=C_{2,1}+\sum _{i=1}^{n}x_{i,2}\cdot \ p_{i,2}\\\vdots \\C_{2,n}=C_{2,n-1}+\sum _{i=1}^{n}x_{i,n}\cdot \ p_{i,2}\\C_{1,2}+L_{2}=C_{2,1}+M_{2}\\C_{1,3}+L_{3}=C_{2,2}+M_{3}\\\vdots \\C_{1,n}+L_{n}=C_{2,n-1}+M_{n}\\\sum _{i=1}^{n}x_{i,k}=1\forall \ k\\\sum _{k=1}^{n}x_{i,k}=1\forall \ i\\L_{i},M_{i}\geq 0\forall \ i\\x_{i,k}\in \left\{0;1\right\}\forall \ i,k\end{array}}\right.

\left\{{\begin{array}{l}C_{1,1}=\sum _{i=1}^{n}x_{i,1}\cdot \ p_{i,1}\\C_{1,2}=C_{1,1}+\sum _{i=1}^{n}x_{i,2}\cdot \ p_{i,1}\\\vdots \\C_{1,n}=C_{1,n-1}+\sum _{i=1}^{n}x_{i,n}\cdot \ p_{i,1}\\C_{2,1}=C_{1,1}+\sum _{i=1}^{n}x_{i,1}\cdot \ p_{i,2}\\C_{2,2}=C_{2,1}+\sum _{i=1}^{n}x_{i,2}\cdot \ p_{i,2}\\\vdots \\C_{2,n}=C_{2,n-1}+\sum _{i=1}^{n}x_{i,n}\cdot \ p_{i,2}\\C_{1,2}+L_{2}=C_{2,1}+M_{2}\\C_{1,3}+L_{3}=C_{2,2}+M_{3}\\\vdots \\C_{1,n}+L_{n}=C_{2,n-1}+M_{n}\\\sum _{i=1}^{n}x_{i,k}=1\forall \ k\\\sum _{k=1}^{n}x_{i,k}=1\forall \ i\\L_{i},M_{i}\geq 0\forall \ i\\x_{i,k}\in \left\{0;1\right\}\forall \ i,k\end{array}}\right.

\left\{{\begin{array}{l}C_{1,1}=\sum _{i=1}^{n}x_{i,1}\cdot \ p_{i,1}\\C_{1,2}=C_{1,1}+\sum _{i=1}^{n}x_{i,2}\cdot \ p_{i,1}\\\vdots \\C_{1,n}=C_{1,n-1}+\sum _{i=1}^{n}x_{i,n}\cdot \ p_{i,1}\\C_{2,1}=C_{1,1}+\sum _{i=1}^{n}x_{i,1}\cdot \ p_{i,2}\\C_{2,2}=C_{2,1}+\sum _{i=1}^{n}x_{i,2}\cdot \ p_{i,2}\\\vdots \\C_{2,n}=C_{2,n-1}+\sum _{i=1}^{n}x_{i,n}\cdot \ p_{i,2}\\C_{1,2}+L_{2}=C_{2,1}+M_{2}\\C_{1,3}+L_{3}=C_{2,2}+M_{3}\\\vdots \\C_{1,n}+L_{n}=C_{2,n-1}+M_{n}\\\sum _{i=1}^{n}x_{i,k}=1\forall \ k\\\sum _{k=1}^{n}x_{i,k}=1\forall \ i\\L_{i},M_{i}\geq 0\forall \ i\\x_{i,k}\in \left\{0;1\right\}\forall \ i,k\end{array}}\right.

Le equazioni del tipo $C_{1,k}+L_{k}=C_{2,k-1}+M_{k}$ $C_{1,k}+L_{k}=C_{2,k-1}+M_{k}$ $C_{1,k}+L_{k}=C_{2,k-1}+M_{k}$ fanno corrispondere il tempo di fine lavorazione del generico lotto in posizione k sulla macchina 1 più il tempo di attesa che la macchina 2 completi la lavorazione del lotto precedente k-1 al tempo di fine lavorazione del lotto k-1 sulla macchina 2 più il tempo di attesa che il lotto k sia ultimato sulla macchina 1.

Job-shop

Si consideri un sistema produttivo costituito da M macchine da utilizzarsi per lavorare N lotti, job-shop : per semplicità di trattazione e notazione si assuma che ogni lotto debba essere lavorato da ogni macchina una ed una sola volta.

$p_{k,m}$ $p_{k,m}$ $p_{k,m}$ : è il tempo per la lavorazione del lotto k-esimo a bordo della macchina m

$x_{k,j,m}$ $x_{k,j,m}$ $x_{k,j,m}$ : è pari a 1 se la lavorazione j-esima del lotto k-esimo viene svolta sulla macchina m-esima; è pari a 0 altrimenti

$t_{k,m}$ $t_{k,m}$ $t_{k,m}$ : è l'istante di inizio della lavorazione del lotto k sulla macchina m

Per rappresentare i vincoli di precedenza della lavorazioni sulle M macchine come ad esempio il fatto che l'operazione j sul lotto k richiede la macchina me l'operazione j+1 sul lotto k richiede la macchina h, si introducono (M-1)N vincoli del tipo seguente:

$\sum _{m=1}^{M}\left(t_{k,m}+p_{k,m}\right)\cdot \ x_{k,j,m}\leq \ \sum _{m=1}^{M}t_{k,m}\cdot \ x_{k,j+1,m}$ $\sum _{m=1}^{M}\left(t_{k,m}+p_{k,m}\right)\cdot \ x_{k,j,m}\leq \ \sum _{m=1}^{M}t_{k,m}\cdot \ x_{k,j+1,m}$ $\sum _{m=1}^{M}\left(t_{k,m}+p_{k,m}\right)\cdot \ x_{k,j,m}\leq \ \sum _{m=1}^{M}t_{k,m}\cdot \ x_{k,j+1,m}$

Inoltre è necessario ricorrere ad un gran numero di vincoli per impedire la lavorazione simultanea di due operazioni sulla stessa macchina, ovvero che in ogni istante di tempo solo ed un solo lotto possa essere in lavorazione a bordo di una macchina. Si introducono i vincoli disgiunti in numero M(N(N-1))/2

$\left\{{\begin{array}{l}t_{i,m}+p_{i,m}\geq \ t_{j,m}\ +L\cdot \ \left(1-y_{i,j,m})\right)\\t_{j,m}+p_{j,m}\geq \ t_{i,m}\ +L\cdot \ y_{i,j,m}\\\end{array}}\right.$ $\left\{{\begin{array}{l}t_{i,m}+p_{i,m}\geq \ t_{j,m}\ +L\cdot \ \left(1-y_{i,j,m})\right)\\t_{j,m}+p_{j,m}\geq \ t_{i,m}\ +L\cdot \ y_{i,j,m}\\\end{array}}\right.$ $\left\{{\begin{array}{l}t_{i,m}+p_{i,m}\geq \ t_{j,m}\ +L\cdot \ \left(1-y_{i,j,m})\right)\\t_{j,m}+p_{j,m}\geq \ t_{i,m}\ +L\cdot \ y_{i,j,m}\\\end{array}}\right.$

dove L è una costante scelta sufficientemente grande, per esempio L= $\sum _{k=1}^{N}\sum _{m=1}^{M}p_{k,m}$ $\sum _{k=1}^{N}\sum _{m=1}^{M}p_{k,m}$ $\sum _{k=1}^{N}\sum _{m=1}^{M}p_{k,m}$ .

Infine $y_{i,j,m}$ $y_{i,j,m}$ $y_{i,j,m}$ : è pari a 1 se il lotto i-esimo precede il lotto j-esimo sulla macchina m, altrimenti è pari a 0. In altri termini, poiché per ipotesi ogni lotto viene lavorato da una macchina una ed una sola volta, a bordo della macchina m l'operazione i viene svolta prima dell'operazione j.

Per M macchine ed N lotti il modello formulato in termini di programmazione intera è il seguente, dove si minimizza la somma dei tempi di inizio di ciascun lotto.

Funzione obiettivo:

min\sum _{k=1}^{N}\sum _{m=1}^{M}t_{k,m}\cdot \ x_{k,j,m}

min\sum _{k=1}^{N}\sum _{m=1}^{M}t_{k,m}\cdot \ x_{k,j,m}

min\sum _{k=1}^{N}\sum _{m=1}^{M}t_{k,m}\cdot \ x_{k,j,m}

soggetta ai seguenti vincoli:

\left\{{\begin{array}{l}\sum _{m=1}^{M}\left(t_{k,m}+p_{k,m}\right)\cdot \ x_{k,j,m}\leq \ \sum _{m=1}^{M}t_{k,m}\cdot \ x_{k,j+1,m}\\t_{i,m}+p_{i,m}\geq \ t_{j,m}\ +L\cdot \ \left(1-y_{i,j,m})\right)\\t_{j,m}+p_{j,m}\geq \ t_{i,m}\ +L\cdot \ y_{i,j,m}\\t_{i,m}\geq 0\forall \ i,m\\y_{i,j,m}\in \left\{0;1\right\}\forall \ i,j,m\\\end{array}}\right.

\left\{{\begin{array}{l}\sum _{m=1}^{M}\left(t_{k,m}+p_{k,m}\right)\cdot \ x_{k,j,m}\leq \ \sum _{m=1}^{M}t_{k,m}\cdot \ x_{k,j+1,m}\\t_{i,m}+p_{i,m}\geq \ t_{j,m}\ +L\cdot \ \left(1-y_{i,j,m})\right)\\t_{j,m}+p_{j,m}\geq \ t_{i,m}\ +L\cdot \ y_{i,j,m}\\t_{i,m}\geq 0\forall \ i,m\\y_{i,j,m}\in \left\{0;1\right\}\forall \ i,j,m\\\end{array}}\right.

\left\{{\begin{array}{l}\sum _{m=1}^{M}\left(t_{k,m}+p_{k,m}\right)\cdot \ x_{k,j,m}\leq \ \sum _{m=1}^{M}t_{k,m}\cdot \ x_{k,j+1,m}\\t_{i,m}+p_{i,m}\geq \ t_{j,m}\ +L\cdot \ \left(1-y_{i,j,m})\right)\\t_{j,m}+p_{j,m}\geq \ t_{i,m}\ +L\cdot \ y_{i,j,m}\\t_{i,m}\geq 0\forall \ i,m\\y_{i,j,m}\in \left\{0;1\right\}\forall \ i,j,m\\\end{array}}\right.

Il problema della Cooperativa di compensati

Una Cooperativa sovietica di compensati sottopose nel 1938 al giovane Leonid Kantorovič , professore universitario dell'Università di San Pietroburgo, un problema di schedulazione della produzione. Il problema consisteva nell'assegnare cinque tipi di legno ad otto macchine sfogliatrici in modo da massimizzare la produzione complessiva dei compensati. Il vincolo cui era soggetta la cooperativa era costituito dal fatto che le quantità da produrre di ciascuno tipo di legno, il mix produttivo, era fissato. Il mix produttivo richiedeva di produrre tanti compensati del tipo 1 quanti quelli del tipo 2, del tipo 3, del tipo 4 e del tipo 5. Nel 1939 venne pubblicata la monografia Mathematical methods of Organizing and Planning Production (Matematicheskie metody organizatsii i planirovaniia proizvodstva) nella quale L. Kantorovič forniva la soluzione del problema, soluzione che può considerarsi come la prima formulazione in termini di programmazione lineare di un problema di schedulazione.

Funzione obiettivo:

m a x Z

{\displaystyle maxZ}

maxZ

soggetta ai seguenti vincoli:

\left\{{\begin{array}{l}Z=\sum _{i=1}^{8}a_{i,1}\cdot \ h_{i,1}=...=\sum _{i=1}^{8}a_{i,5}\cdot \ h_{i,5}\\\sum _{k=1}^{5}h_{i,k}=1\qquad \forall \ i=1,...,8\\0\leq h_{i,k}\leq 1\qquad \forall \ i,k\\\end{array}}\right.

\left\{{\begin{array}{l}Z=\sum _{i=1}^{8}a_{i,1}\cdot \ h_{i,1}=...=\sum _{i=1}^{8}a_{i,5}\cdot \ h_{i,5}\\\sum _{k=1}^{5}h_{i,k}=1\qquad \forall \ i=1,...,8\\0\leq h_{i,k}\leq 1\qquad \forall \ i,k\\\end{array}}\right.

\left\{{\begin{array}{l}Z=\sum _{i=1}^{8}a_{i,1}\cdot \ h_{i,1}=...=\sum _{i=1}^{8}a_{i,5}\cdot \ h_{i,5}\\\sum _{k=1}^{5}h_{i,k}=1\qquad \forall \ i=1,...,8\\0\leq h_{i,k}\leq 1\qquad \forall \ i,k\\\end{array}}\right.

L'incognita del problema è rappresentata dal tempo di lavorazione, la variabile $h_{i,k}$ $h_{i,k}$ $h_{i,k}$ che indica il tempo espresso come frazione del giorno lavorativo, di utilizzo della macchina i-esima per produrre il compensato di tipo k. Il problema consiste proprio nel determinare la variabile tempo tale che il quantitativo di compensato prodotto sia massimo. La richiesta che la i-esima macchina venga impiegata per tutto il giorno lavorativo trova espressione nel vincolo $\sum _{k=1}^{5}h_{i,k}=1$ $\sum _{k=1}^{5}h_{i,k}=1$ $\sum _{k=1}^{5}h_{i,k}=1$ , mentre il parametro che caratterizza la produzione giornaliera di ogni macchina per ogni tipo di compensato è $a_{i,k}$ $a_{i,k}$ $a_{i,k}$ . Il prodotto $a_{i,k}\cdot \ h_{i,k}$ $a_{i,k}\cdot \ h_{i,k}$ $a_{i,k}\cdot \ h_{i,k}$ fornisce il quantitativo di compensato tipo k prodotto dalla macchina i-esima. La loro reciproca uguaglianza fa in modo che il quantitativo di un tipo di compensato eguagli quello degli altri.

Sistemi a coda

Gran parte della teoria della schedulazione assume come ipotesi di lavoro l'arrivo simultaneo dei lotti presso il centro di lavorazione, in altri termini si ipotizza che tutti i lotti siano pronti e disponibili ad incominciare le lavorazioni ad un preciso istante iniziale. Quando questa ipotesi non è applicabile o meglio ogniqualvolta i lotti arrivano in modo intermittente ed in momenti non noti a priori, il problema del loro sequenziamento ottimale viene affrontato in termini probabilistici. Il problema di arrivi casuali è inquadrato nella teoria delle code . Per i sistemi che generano code, cd sistemi a coda, particolar enfasi è posta sul criterio di selezione mediante il quale un lotto in attesa viene selezionato dalla coda ed inviato alla macchina che si è liberata della lavorazione precedente.

Schedulazione ottimale dei Progetti: il Metodo del Percorso Critico, CPM

Un progetto è definito come un insieme costituito da un certo numero di attività dette anche task che devono essere svolte con un dato ordine. In altri termini esistono vincoli di precedenza sulle attività, tipicamente un'attività non può iniziare prima che altre vengano ultimate. Ogni attività è altresì caratterizzata da un tempo di esecuzione. Il " metodo del percorso critico " o Critical Path Method, in breve " CPM ", permette di rispondere alle seguenti domande:

Qual è il tempo minimo richiesto per completare l'intero progetto?
Quali sono gli istanti di inizio e di fine delle singole attività?
Quali attività possono essere ritardate senza causare un ritardo all'intero progetto?
Per ridurre la durata del progetto su quali attività si dovrà intervenire?

Ad un progetto si associa una sua rappresentazione grafica costituita da un grafo orientato (diagramma reticolare): ogni attività è rappresentata da un arco i cui nodi estremi rappresentano l'inizio ed il termine dell'attività stessa. La durata del progetto è pari a $t_{f}-t_{0}$ $t_{f}-t_{0}$ $t_{f}-t_{0}$ dove $t_{f}$ $t_{f}$ $t_{f}$ è il tempo per completare al più tardi le attività che confluiscono nel nodo terminale. Posto convenzionalmente a zero l'istante d'avvio del progetto, $t_{0}=0$ $t_{0}=0$ $t_{0}=0$ , il problema di determinare il tempo minimo richiesto per completare interamente un progetto costituito da n nodi ed m attività si formalizza come segue

min\left\{t_{f}\right\}

min\left\{t_{f}\right\}

min\left\{t_{f}\right\}

soggetta ai seguenti vincoli:

\left\{{\begin{array}{l}t_{j}\geq t_{i}\ +p_{i,j}\\t_{i}\geq 0\forall \ i=1,...,n\\\end{array}}\right.

\left\{{\begin{array}{l}t_{j}\geq t_{i}\ +p_{i,j}\\t_{i}\geq 0\forall \ i=1,...,n\\\end{array}}\right.

\left\{{\begin{array}{l}t_{j}\geq t_{i}\ +p_{i,j}\\t_{i}\geq 0\forall \ i=1,...,n\\\end{array}}\right.

$t_{i}$ $t_{i}$ $t_{i}$ : tempo di inizio della o delle attività di cui il nodo i è diretto predecessore del nodo j. $t_{j}$ $t_{j}$ $t_{j}$ : tempo di fine della o delle attività che giungono al nodo j. $p_{i,j}$ $p_{i,j}$ $p_{i,j}$ : indica la durata dell'attività associata all'arco (i;j). Il vincolo $t_{j}\geq t_{i}\ +p_{i,j}$ $t_{j}\geq t_{i}\ +p_{i,j}$ $t_{j}\geq t_{i}\ +p_{i,j}$ impone che un'attività j non possa iniziare prima che le attività i che la precedono vengano terminate. Si osservi che il tempo di inizio di un'attività uscente da un nodo coincide con il tempo di fine delle attività entranti nel nodo stesso. L'obiettivo del modello consiste nel minimizzare la durata complessiva del progetto e la soluzione del problema lineare fornisce i tempi di inizio di tutte le m attività nel rispetto degli m vincoli di precedenza. Una tempificazione così fatta del progetto determina l'istante in cui avviare ogni attività in modo da minimizzare la durata complessiva del progetto. La soluzione contenuta nella funzione obiettivo corrisponde al tempo di attraversamento minimo e viene misurata lungo il cammino o percorso critico ; l'algoritmo identifica quali attività sono critiche nel senso che chiariremo tra breve. Il cammino critico è costituito da tutte e solo le attività che non possono essere ritardate senza causare un ritardo all'intero progetto e ad esse ci si riferisce come attività critiche. Introdotte la variabile ausiliaria di surplus, una per ogni vincolo di precedenza, $s_{i}\geq 0$ $s_{i}\geq 0$ $s_{i}\geq 0$ così definita

$s_{i}=t_{j}-t_{i}-p_{i,j}$ $s_{i}=t_{j}-t_{i}-p_{i,j}$ $s_{i}=t_{j}-t_{i}-p_{i,j}$

se $s_{i}>0$ $s_{i}>0$ $s_{i}>0$ allora l'attività non è critica in quanto esiste del tempo in eccesso: l'attività potrebbe venire ritardata proprio per un tempo pari a $s_{i}$ $s_{i}$ $s_{i}$ . Se $s_{i}=0$ $s_{i}=0$ $s_{i}=0$ il vincolo è saturo e l'attività risulta critica. Il problema lineare formulato in forma standard è intimamente legato alla geometria del grafo orientato: il problema conterrà un certo numero k di incognite connesso al numero di nodi e, un certo numero m di equazioni (vincoli di precedenza) legato alla numerosità delle attività elementari con cui è stato disaggregato il progetto. Il numero di incognite k è proporzionale al numero di nodi, poiché ogni nodo non può presentare più di due variabili $t_{i}$ $t_{i}$ $t_{i}$ e $t_{j}$ $t_{j}$ $t_{j}$ ; tenuto conto che il numero di variabili di surplus $s_{i}$ $s_{i}$ $s_{i}$ è pari esattamente ad m, si ha n+m ≤ k ≤ 2n+m. Ricordando che il numero di equazioni risulta pari ad m, in generale dunque sì è in presenza di un sistema di equazioni indeterminato avendosi un numero di incognite maggiore del numero di equazioni, k>m. Il sistema di vincoli possiede pertanto più di una di soluzione, $\infty ^{k-m}$ $\infty ^{km}$ $\infty ^{k-m}$ soluzioni. L' algoritmo del simplesso non esplorerà tutte le infinite soluzioni alla ricerca di quella ottimale, ma selezionerà solo quelle che costituiscono una soluzione di base ammissibile e che sono in numero finito. Le soluzioni di base ammissibili sono pertanto le soluzioni candidate a minimizzare il tempo di attraversamento: poiché tali soluzioni possiedono sempre almeno km componenti nulle; avendosi $p_{i,j}>0$ $p_{i,j}>0$ $p_{i,j}>0$ , rimane dimostrato che un grafo orientato presenta sempre almeno min (km;m) attività critiche. Il project manager, individuando le attività critiche, è in grado di riconoscere le attività che costituiscono il reale collo di bottiglia nell'esecuzione del progetto.

Programmazione dei turni del personale

La schedulazione o programmazione del personale si pone l'obiettivo di redigere tabelle orarie per il personale in forza lavoro al fine di soddisfare una data domanda (di risorse umane, di beni o di servizi) senza violare i regolamenti contrattuali stabiliti per legge, i regolamenti interni all'impresa, le preferenze stesse del personale o le loro abilità. Le variabili sono tipicamente costituite dalla dimensione della forza-lavoro ed il numero di lavoratori assegnati ad ogni turno. La funzione obiettivo è generalmente rappresentata dalla minimizzazione del costo della forza lavoro oppure dalla massimizzazione dell'efficienza e degli impieghi. I vincoli sono generalmente costituiti da regolamenti cogenti. La formulazione del problema in termini di programmazione lineare intera prevede di schematizzare i turni candidati mediante una matrice . Tale matrice viene chiamata matrice di turnazione e consiste in una tabella costituita da m righe ed n colonne. La forma della matrice è intimamente connessa con il tipo di problema di turnazione da risolvere. I problemi di schedulazione del personale possono essere classificati in uno dei seguenti tre gruppi. Il primo gruppo accoglie i classici problemi di turnazione ciclica ( cyclic staffing problem ) e consiste nell'organizzare i turni all'interno di uno tabella ciclica del tipo (k, m) in modo che il personale lavori per k periodi consecutivi seguiti da mk periodi di riposo. Generalmente un periodo rappresenta il giorno, sicché la notazione (5,7) tipica per i lavoratori giornalieri, indica un ciclo di sette giorni in cui ogni persona lavora 5 giorni consecutivi seguiti da due giorni di riposo. Al secondo gruppo di problemi appartiene la schedulazione dei giorni di riposo ( days-off scheduling ) nella quale si vuole determinare, in accordo ai regolamenti contrattuali, quando interporre i giorni di riposo tra i vari giorni lavorativi. Il terzo gruppo è costituito dalla schedulazione dei turni ( shift scheduling ) in cui è richiesto di garantire la continuità di servizio in fasce orarie di almeno dieci ore ed il servizio non può essere assicurato articolando periodi di lavoro da otto ore ossia organizzando fasce orarie del tipo 7-14/14-21. Il problema consiste nel determinare i tipi di turno (part-time di 6 ore, full-time, part-time di 4 ore, etc.) in modo che le risorse allocate rispettino una certa richiesta di prestazioni nelle diverse fasce orarie e che il numero di risorse impiegate sia minimo o minimo sia il corrispondente costo del lavoro.

In generale il problema di assegnare in modo equo i giorni festivi al personale non ha soluzione se il numero di turni presenti nel periodo in esame è un numero primo ed il numero di risorse a presidio di ogni turno è superiore a uno.

Esempio di modello base

In una matrice di turnazione le righe rappresentano $i=1,...,m$ ${\displaystyle i=1,...,m}$ $i=1,...,m$ intervalli di tempo o periodi: il problema consiste nel determinare il numero di risorse che deve essere presente in ciascun periodo in modo tale da soddisfare una certa richiesta di personale. Il numero di lavoratori necessari nel generico periodo $i$ ${\displaystyle i}$ $i$ si denota con $b_{i}$ $b_{i}$ $b_{i}$ . Ogni colonna della matrice rappresenta invece un possibile turno di assegnazione e consiste in una sequenza di 0 e 1 lunga $m$ ${\displaystyle m}$ $m$ . Il valore uno indica un periodo lavorativo, lo zero indica un periodo di riposo. Ad esempio la notazione $a_{ij}=1$ $a_{ij}=1$ $a_{ij}=1$ per il generico elemento della matrice di turnazione $A$ ${\displaystyle A}$ $A$ indica che il periodo i-esimo del turno j-esimo è lavorativo. Se il numero di schemi di turno possibile è pari ad $j=1,...,n$ ${\displaystyle j=1,...,n}$ $j=1,...,n$ ed $m$ ${\displaystyle m}$ $m$ sono i periodi in esame, la matrice di turnazione è una matrice di dimensione $m\times n$ $m\times n$ $m\times n$ .

Ad esempio considerando 7 periodi corrispondenti rispettivamente a lunedì, martedì, mercoledì, giovedì, venerdì, sabato e domenica, si vogliono valutare due tipi di turnazione: una turnazione full-time da 48 ore settimanali, l'altra turnazione di tipo part-time orizzontale costituita da 4 ore giornaliere su 5 giorni lavorativi per un totale di 20 ore settimanali. La matrice dei turni ammissibili assume dunque la forma

$A={\begin{pmatrix}1&0&1&1&1&1&1&1&0&0\\1&1&0&1&1&1&1&1&1&0\\1&1&1&0&1&1&1&1&1&1\\1&1&1&1&0&1&1&1&1&1\\1&1&1&1&1&0&1&1&1&1\\1&1&1&1&1&1&0&0&1&1\\0&1&1&1&1&1&1&0&0&1\\\end{pmatrix}}$ $A={\begin{pmatrix}1&0&1&1&1&1&1&1&0&0\\1&1&0&1&1&1&1&1&1&0\\1&1&1&0&1&1&1&1&1&1\\1&1&1&1&0&1&1&1&1&1\\1&1&1&1&1&0&1&1&1&1\\1&1&1&1&1&1&0&0&1&1\\0&1&1&1&1&1&1&0&0&1\\\end{pmatrix}}$ $A={\begin{pmatrix}1&0&1&1&1&1&1&1&0&0\\1&1&0&1&1&1&1&1&1&0\\1&1&1&0&1&1&1&1&1&1\\1&1&1&1&0&1&1&1&1&1\\1&1&1&1&1&0&1&1&1&1\\1&1&1&1&1&1&0&0&1&1\\0&1&1&1&1&1&1&0&0&1\\\end{pmatrix}}$

La variabile decisionale $x_{j}$ $x_{j}$ $x_{j}$ indica il numero di risorse da assegnarsi al turno di tipo $j$ ${\displaystyle j}$ $j$ e costituirà l'incognita a variabile intera del problema.

Il vincolo che richiede il numero minimo di personale in ogni periodo è del tipo

$\ {\vec {a}}^{1}\ \cdot x_{1}+{\vec {a}}^{2}\ \cdot x_{2}+\cdots +{\vec {a}}^{m}\cdot x_{m}\geq \ {\vec {b}}\$ $\ {\vec {a}}^{1}\ \cdot x_{1}+{\vec {a}}^{2}\ \cdot x_{2}+\cdots +{\vec {a}}^{m}\cdot x_{m}\geq \ {\vec {b}}\$ $\ {\vec {a}}^{1}\ \cdot x_{1}+{\vec {a}}^{2}\ \cdot x_{2}+\cdots +{\vec {a}}^{m}\cdot x_{m}\geq \ {\vec {b}}\$

avendo fatto ricorso alla notazione di vettore colonna.

Se il costo dell'assegnazione di una risorsa al turno j-esimo si denota con $c_{j}$ $c_{j}$ $c_{j}$ allora la funzione obiettivo che minimizza il costo del lavoro è della forma:

$z=min\sum _{j=1}^{m}c_{j}\cdot x_{j}$ $z=min\sum _{j=1}^{m}c_{j}\cdot x_{j}$ $z=min\sum _{j=1}^{m}c_{j}\cdot x_{j}$

Schedulazione degli equipaggi - Crew Scheduling

La schedulazione del personale trova ampia applicazione nelle imprese che operano nei trasporti quali ad esempio le compagnie aeree e quelle ferroviarie. Per le compagnie aeree il costo degli equipaggi (salari, benefits e spese) costituisce la seconda componente di costo in ordine di grandezza dopo il costo per il carburante. L'obiettivo del problema della schedulazione degli equipaggi ( crew scheduling problem ) consiste nel determinare per ogni equipaggio ( crew ) una sequenza di tratte ( pairing of flights ) in modo tale che tutti i piani di volo vengano coperti e che il costo totale degli equipaggi sia minimo. Con il termine sequenza di tratte si intende una sequenza di voli che incomincia e termina nel medesimo punto di partenza ( base di armamento ), ossia la sequenza fa in modo di riportare l'equipaggio all'aeroporto dove risiede e per tale motivo è chiamata tour. La sequenza di tratte ottimale specifica date e ore per ogni giorno in esame. La soluzione del problema, se necessario, può assegnare anche più di un equipaggio ad un medesimo volo ( deadheading ) al fine di trasportare un equipaggio sino ad un certo nodo della rete. Pertanto se si rimuove la possibilità di “deadheading” sarà necessario introdurre vincoli che tengono conto del numero di equipaggi disponibili in ogni base aerea. I piloti, i macchinisti, gli assistenti di volo, gli assistenti a bordo treno vengono così assegnati ad una sequenza di tratte in modo tale che l'equipaggio operi su almeno due tratte ed in modo che l'orario di partenza di un viaggio nella sequenza scelta non anticipi l'orario di arrivo del viaggio precedente nella sequenza in oggetto. Il costo di una sequenza di tratte può essere espresso per semplicità come l'intervallo di tempo intercorrente tra la prima partenza e l'ultimo arrivo. Inoltre poiché la durata di un turno lavorativo è regolamentato da specifiche e cogenti normative quali ad esempio il divieto per i piloti di volare per più di 8 ore in un periodo di 24 ore, il divieto per gli aerei di essere utilizzati per più di 14 ore in un giorno, una formulazione realistica del problema richiede di formulare i vincoli espressi dalla normativa sindacale, nazionale e delle compagnie aeree.

Miscellanea

Il problema della schedulazione degli equipaggi può essere considerato come un particolare utilizzo del problema del flusso massimo attraverso una rete. Nel problema del flusso massimo viene assegnata una rete (ad esempio una rete ferroviaria, una rete idraulica o una rete di comunicazione) che connette un certo numero di città (ie nodi); ogni arco (ie tratta) della rete viene caratterizzato con un numero che ne rappresenta la capacità di trasporto; il problema consiste nel determinare la quantità massima di flusso che dal nodo di partenza è possibile trasportare fino al nodo di destinazione tenendo conto dei vincoli di capacità su tutti gli archi. Il problema del flusso massimo in forma standard ha come problema duale il problema di flusso a costo minimo detto anche problema del taglio minimo, il teorema del flusso massimo e del taglio minimo afferma che il valore del flusso massimo è uguale alla capacità del minimo taglio. Sotto questo punto di vista il problema del flusso a costo minimo può vedersi come il problema dell'individuazione del collo di bottiglia di una rete : il collo di bottiglia corrisponde al taglio che presenta il costo minimo. Eliminare dalla rete gli archi di un taglio fa sì che nessun flusso possa più passare dal nodo di partenza alla destinazione. In un conflitto bellico l'interdizione mirata della capacità del nemico di muovere uomini, mezzi ed informazioni attraverso le reti di trasporto riveste valenza strategica, da cui il notevole interesse delle varie forze armate a questi ambiti di ricerca ^[1] . Poiché la disponibilità di una rete fisica di telecomunicazioni è vulnerabile ad attacchi, nel 1958 all'Agenzia governativa statunitense ARPA vennero assegnati diversi compiti tra i quali quello di progettare una rete militare finalizzata allo scambio sicuro delle informazioni. Il paradigma alla base di una comunicazione sicura doveva risiedere nella possibilità di rendere sempre possibile lo scambio di informazioni tra i terminali anche nel caso in cui un arco della rete fisica fosse andato distrutto: nell'eventualità doveva essere possibile ricorrere ad un “canale alternativo” la cui capacità massima di trasmettere dati ( capacità di canale ) potesse essere anche inferiore alla dimensione dei dati stessi ( datagramma ). Per superare il vincolo della capacità di canale, in ARPAnet fu ideato un protocollo di trasmissione basato su un meccanismo per frammentare il messaggio in pacchetti di dimensione ridotta ( commutazione di pacchetto ) per venire trasmessi ed instradati ognuno in modo indipendente ed infine per essere riassemblati nel nodo di destinazione.

Schedulazione dei trasporti

Distribuire beni significa servire un insieme di clienti per mezzo di una flotta di veicoli che sono caratterizzati da una certa capacità di trasporto (illimitata o limitata) e che sono localizzati presso uno o più depositi. I veicoli servono i punti vendita al dettaglio attraverso la rete stradale esistente. Per prima cosa lo spedizioniere determina i carichi per ciascuno veicolo ed il relativo percorso con l'obiettivo di minimizzare il numero di veicoli impiegati, in seconda istanza lo spedizioniere decide la sequenza nella quale i punti vendita verranno visitati al fine di minimizzare, o dal punto di vista temporale o spaziale, la lunghezza complessiva del percorso assegnato. Questi due tipi di problemi presuppongono che le unità di carico imballino la merce in colli di forma simmetrica e che questi vengano collocati a bordo del veicolo senza problemi di ingombro ossia può essere solo richiesto che la somma del peso dei beni non ecceda la capacità di trasporto del mezzo. I problemi di distribuzione che considerano l'orientazione dei colli e della loro unità individuale sono detti problemi di imballaggio ( packing problems ) ed hanno come obiettivo quello di minimizzare il numero di contenitori impiegati o quello di massimizzare i colli caricati. Esistono diversi modelli matematici a seconda delle proprietà basilari che il sistema di trasporto in esame gode; sebbene tali problemi siano certamente più semplici dei problemi reali, tuttavia possiedono il pregio di evidenziarne gli elementi essenziali. Il più semplice modello di trasporto è rappresentato dal ''problema del commesso viaggiatore'' , travelling salesman problem. Il cosiddétto vehicle routing problem introduce il fatto che ad ogni cliente è associata una domanda di beni ed il veicolo presenta una data capacità di carico. Se si considera una finestra temporale entro cui ogni cliente può essere visitato si giunge al vehicle routing problem with time windows. Il VRPTW è una generalizzazione del VRP ed è in grado di modelizzare numerose situazioni reali.

• Traveling Salesman Problem, TSP: dal deposito parte un solo veicolo. L'obiettivo consiste nel determinare il percorso di consegna ottimo dell'unico veicolo per visitare una ed una sola volta i clienti.

• Vehicle Routing Problem , VRP: un insieme di punti vendita/clienti viene servito da una flotta di veicoli dalla capacità di trasporto illimitata. I veicoli inizialmente sono localizzati presso un unico deposito assegnato. Ogni cliente viene servito da un solo veicolo. Ogni percorso, itinerario incomincia dal deposito, visita un insieme di clienti e ritorna al deposito. L'obiettivo consiste nel trovare per ogni veicolo il percorso di lunghezza minima in modo che il costo logistico totale sia minimo.

• Capacited Vehicle Routing Problem , CVRP: un insieme di clienti viene servito da una flotta di veicoli dalla capacità di carico limitata. I veicoli inizialmente si trovano presso il deposito assegnato. Ogni itinerario incomincia dal deposito, visita un insieme di clienti e ritorna al deposito senza violare il vincolo di capacità del vettore. Se si ammette la possibilità di ripartire tra più veicoli la domanda di beni del cliente i- esimo allora il modello si dice CVRP a domande suddivise ( split demands ). In tale circostanza un cliente può riceve più consegne la cui somma complessiva eguaglia la domanda del cliente.

• Vehicle Routing Problem with Backhauls, VRPB: Una variante del VRP contempla il backhauls: ad ogni veicolo non solo è richiesto di consegnare i beni dal deposito ai clienti ( linehaul ), ma è anche richiesto di prelevare da qualche cliente (backhaul ) della merce che deve essere riportata al deposito. In molte applicazioni pratiche i clienti linehaul hanno una priorità più alta dei clienti backhaul: i clienti backhaul di un itinerario vengono serviti solo dopo che tutti i clienti linehaul di quell''tinerario sono stati serviti.

• Vehicle Routing Problem with Pick-up and Delivery , VRPPD: ogni veicolo parte dal deposito trasportando una quantità di merce pari alla quantità che dovrà essere consegnata e fa ritorno al deposito con una quantità di resi pari alla quantità totale raccolta. I punti di prelievo della merce e di consegna della merce o del materiale di scarto non coincidono necessariamente con il deposito.

• Vehicle Routing Problem with Time Window constraints , VRPTW: esiste una finestra temporale [a, b] entro la quale il veicolo può servire il deposito ed ogni cliente. Il tempo di inizio servizio in ogni destinazione deve essere non inferiore ad a, il tempo di arrivo in ogni destinazione deve essere non superiore a b. Se il veicolo arriva a destinazione ad un tempo anteriore ad a, il veicolo dovrà attendere prima di poter iniziare a servire il cliente.

Schedulazione stocastica

I modelli di programmazione lineare per la schedulazione dei sistemi produttivi sopra descritti presentano tutti una connotazione deterministica. In tale modelli si assume implicitamente che

• il numero di lotti da sequenziare è assegnato e non varia,

• i tempi di lavorazione sono noti e non cambiano,

• gli istanti in cui i lotti sono disponibili per iniziare le lavorazioni (arrivi o ready time) sono noti e non variano,

• le macchine non si guastano mai e sono sempre disponibili lungo tutto l'orizzonte di pianificazione

Incertezza e imprevedibilità non vengono minimamente prese in considerazione. I sistemi reali invece sono caratterizzati da elementi di incertezza che rendono i sistemi in esame complessi. Nei sistemi reali si assiste ad un continuo arrivo nel tempo degli ordinativi così come all'incertezza legata all'impossibilità di misurare senza errore i tempi di lavorazione delle macchine. Le stesse macchine poi sono soggette a guasti, malfunzionamenti. Si dicono stocastici i problemi di schedulazione in cui i parametri del modello non sono noti con certezza e l'incertezza associata può essere descritta da distribuzioni di probabilità note. Ad esempio in un modello stocastico di schedulazione della produzione gli ordini arrivano in modo casuale nel tempo oi tempi delle lavorazioni e le disponibilità delle macchine sono conoscibili con un certo grado di incertezza. Nei modelli di schedulazione stocastica l'incertezza ed il caso vengono rappresentati in termini probabilistici.

Schedulazione dinamica

Se il sistema in esame presenta elementi di incertezza ossia il decisore non dispone di informazioni sulla probabilità di accadimento degli eventi, ma eventi imprevisti ed ineludibili possono accadere allora si parla di schedulazione dinamica . Si definiscono dinamici tutti quei problemi di schedulazione che contemplano l' accadimento di eventi in tempo reale . I modelli di schedulazione statici assumo che tutte le caratteristiche del problema sono note e fisse nel tempo e pertanto sono in grado di determinare soluzioni ottimali in anticipo: in questo senso la schedulazione della produzione rappresenta il nocciolo delle attività di pianificazione della produzione. I modelli di schedulazione così detti statici non sono capaci di far uso delle informazioni che giungono in tempo reale: gli imprevisti determinano variazioni nel piano in precedenza programmato tali da renderlo non più praticabile ( unfeasible ) o perlomeno non più ottimale. Nell'ambiente produttivo esempi di eventi che possono accadere in tempo reale sono rappresentati dall'arrivo di un lotto urgente, dal verificarsi di un guasto in una macchina o dall'indisponibilità di un operatore, dal cambiamento nelle date di consegna, dalla mancanza dei materiali o da non conformità di questi ultimi, dalla cancellazione di uno o più ordini di produzione, etc.

La schedulazione dinamica si differenzia a seconda dei diversi approcci adottati. Un primo approccio si basa nel non generare in anticipo alcuna schedula, ma piuttosto nel prendere decisioni in tempo reale: le regole di dispaccio ( dispatching rules ) giocano un ruolo fondamentale e consistono nel selezionare quale lotto lavorare tra un insieme di lotti, in attesa che la macchina divenga nuovamente libera. Le dispatching rules più conosciute sono Shortest Process Time (SPT), Earliest Due Date (EDD) e First Come First Served (FCFS). La loro semplicità d'uso deriva dal fatto che sono facilmente applicabili a molti contesti e richiedono un tempo di calcolo davvero modesto. Un approccio alternativo ammette una pianificazione anticipata e la schedula prevista viene poi di volta in volta corretta, ri-schedulata, in risposta agli eventi che si presentano nel futuro. Ad esempio gli ordini di produzione vengono schedulati ad intervalli regolari (politica di riesame periodico) e vengono determinati grazie agli algoritmi di schedulazione statica. La schedula determinata viene eseguita e non rivista sino a quando inizia il periodo successivo: nel momento del riesame la schedula precedentemente determinata viene ri-schedulata sulla base delle nuove informazioni raccolte. Stabilire il periodo di ri-schedulazione ( rolling time horizon ) risulta essere un compito piuttosto difficile.

Schedulazione intelligente

La schedulazione dinamica può adottare anche tecniche di intelligenza artificiale allorquando esista un'ampia varietà di decisioni che possono essere prese davanti al verificarsi di eventi imprevisti che accadono in tempo reale. I sistemi basati sull'intelligenza artificiale ( knowledge-based systems ) si concentrano nel catturare le competenze e le esperienze passate e deducono attraverso metodi inferenziali quali decisioni è raccomandabile vengano intraprese. Ad esempio si può far ricorso a tecniche di machine learning supervisionato (reti neuronali, support vector machines, etc.) al fine di migliorare le prestazioni della schedulazione dinamica basata sulle regole di dispaccio. Proprio perché tra le regole di dispaccio non esiste una regola migliore di un'altra in senso assoluto, il ricorso alle tecniche di machine learning risulta essere promettente. L'approccio del machine learning supervisionato si basa sulla simulazione, su esempi noti ed il suo obiettivo consiste nel selezionare la miglior regola di dispaccio per una macchina a seconda delle condizioni che si possono presentare nel sistema produttivo. Le tecniche di programmazione matematica svolgono una sequenza di istruzioni esplicite e specificate per determinare la schedula corretta/ottimale, il machine learning invece determina quale regole di dispaccio sia migliore sulla base della prestazione da questa ottenuta in casi noti e/o simulati (il cd training set ). Ad esempio come misura di prestazione si può scegliere la mean tardiness (il ritardo medio), successivamente si introduce quale varietà di azioni correttive un insieme di regole di dispaccio alternative. Si definiscono poi un certo numero di condizioni di funzionamento del sistema produttivo che costituiranno i parametri di input per il machine learning. Il funzionamento del sistema produttivo viene infine simulato al variare delle diverse combinazioni che questi parametri generano. La misura di prestazione adottata determinerà quale regola di dispaccio sia preferibile tra tutte quelle introdotte.

La risoluzione dei problemi di schedulazione

Metodologia tipica adottata in un processo di ottimizzazione

Una volta inquadrato il problema in una delle casistiche sopra esposte (problema a macchina singola, macchine parallele, etc) ed aver formulato il problema mediante un modello matematico, si procede alla risoluzione di quest'ultimo facendo ricorso a programmi informatici specifici. Il modello matematico viene dapprima tradotto nel linguaggio di modellizzazione proprio del programma adottato, esempi di sistemi di modellazione algebrico sono PuLP di Phyton, AMPL , FlopC++ o GAMS. Infine il modello viene risolto con un risolutore specifico in base alla categoria di appartenenza del problema di ottimizzazione (programmazione lineare intera, programmazione lineare, programmazione non lineare, programmazione stocastica, etc.). Esempi di risolutori di problemi lineari sono COIN-OR LP, CPLEX . Esistono anche risolutori che hanno i fogli elettronici di Excel come ambiente nel quale scrivere il modello matematico. Microsoft Excel contiene ad esempio un risolutore quale componente aggiuntivo denominato Risolutore ( Solver sviluppato da Frontline System Inc.) grazie al quale un utilizzatore può scrivere il modello matematico di schedulazione direttamente in Excel e risolverlo determinando la soluzione ottimale. Tuttavia i problemi che possono essere trattati sono ostacolati dal fatto che la capacità di calcolo del Risolutore è artificialmente limitata ad un certo numero di variabili (200 celle variabili, 2018). Esiste poi un software open source, OpenSolver, in grado di risolvere problemi di ottimizzazione in ambito lineare, intero e non lineare in Excel che non ammette un numero massimo di variabili. OpenSolver utilizza COIN-OR CBC per generare la soluzione in Excel. Il metodo del simplesso che risolve i problemi di programmazione lineare presenta una complessità computazionale che non è polinomiale, questo significa che al crescere della complessità del problema, il tempo necessario per eseguire l'algoritmo e lo spazio di memoria occupato in un calcolatore cresce in modo esponenziale. Un Centro di Elaborazione Dati , in gergo Data Center , è capace di offrire un'enorme potenza di calcolo e la sua fruibilità via Web quale servizio di cloud computing fornirà sempre più impulso alla risoluzione dei problemi di schedulazione attraverso i metodi esatti .

Una prospettiva storica

Correva l'anno 1939 quando L. Kantorovich presentava le sue idee matematiche per perseguire il perfezionamento dell'organizzazione della pianificazione e della produzione , era il 1947 quando G. Dantzig propose il metodo del simplesso per risolvere i problemi di programmazione lineare includendo quindi i problemi di schedulazione. Tra gli inizi degli anni '50 del ventesimo secolo ed il volgere degli anni '90 la diffusione degli algoritmi di risoluzione basati su metodi esatti (si ricordi il metodo del simplesso già citato) sono stati penalizzati dalla capacità di calcolo degli elaboratori all'epoca disponibile: fece così seguito il ricorso sempre più esteso ad algoritmi euristici che raggiunsero il loro apice negli anni '90.

Note

^ Fundamentals of a method for evaluating rail net capacities, Archiviato il 20 settembre 2015 in Internet Archive .. US Airforce PROJECT RAND.

Bibliografia

Richard Bellman, Mathematical aspects of scheduling theory , USA: RAND Inc., 1955
Kenneth R. Baker, Introduction to sequencing and scheduling , USA: John Wiley & Sons Inc., 1974
Simon French, Sequencing and scheduling: an introduction to the Mathematics of the Job-Shop , Great Britain: Ellis Horwood Limited, 1987
Paolo Brandimarte, Agostino Villa, Gestione della produzione industriale , Torino: UTET Libreria, 1995
Richard W. Conway, William L. Maxwell, Louis W. Miller, Theory of scheduling , USA: Dover Publications Inc., 2003
Michael L. Pinedo, Planning and Scheduling in Manufacturing and Services , USA: Springer, 2007
M. Bazargan, Airline Operations and Scheduling , USA: Ashgate, 2010
Jacek Blazewicz, Moshe Dror, Jan Weglarz, Mathematical programming formulations for machine scheduling: A survey , North Holland: European Journal of Operational Research 51, 1991
Nasser A. El-Sherbeny, Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods , Journal of King Saud University, 2009
Djamila Ouelhadj, Sanja Petrovic, A survey of dynamic scheduling in manufacturing systems , Springer Science+Business Media, 2008

Collegamenti esterni

( EN ) Fundamentals of a Method for evaluating Rail Net Capacities ( PDF ), su dtic.mil . URL consultato il 5 aprile 2017 .
( EN ) Improving Production Scheduling with Machine Learning , su researchgate.net . URL consultato il 12 febbraio 2018 .

[1] Fundamentals of a method for evaluating rail net capacities, Archiviato il 20 settembre 2015 in Internet Archive .. US Airforce PROJECT RAND.

[1]