CAPITOLUL II

 

 

INTRODUCERE N OPTIMIZAREA COMBINATORIAL

 

 

1. Obiectul optimizrii combinatoriale

 

Combinatorica este un domeniu reprezentativ al matematicilor care, n esen, se ocup cu studiul aranjamentelor obiectelor unei mulimi finite, conforme unei structuri date. n problemele combinatoriale, prioritare sunt chestiunile de existen i de numrare:

 

     exist un anumit tip particular de aranjament?

     cte asemenea aranjamente se pot forma?

 

Caracteristic problemelor combinatoriale este faptul c numrul acestor aranjamente este finit.

Dac aranjamentele unei probleme combinatoriale pot fi comparate pe baza unui criteriu de apreciere apare o problem de optimizare combinatorial:

 

     care este cel mai bun aranjament din punctul de vedere al criteriului respectiv?

 

Exemplul 1.1 S considerm un graf finit i simplu G = (V,E) n care V este mulimea nodurilor iar E este mulimea muchiilor.Un arbore n graful G este un subgraf H = (V,A) , A Ì E , cu aceleai noduri ca i G, care, de sine stttor, este un graf conex i fr cicluri (vezi figura 1.1 n care muchiile arborelui au fost ngroate)

 

Se pun urmtoarele chestiuni:

 

     conine G cel puin un arbore?

     ci arbori distinci se pot forma?

 

 

n cazul de fa obiectele de lucru sunt muchiile

grafului G. Un aranjament al acestor obiecte este

o submulime de muchii A Ì E cu proprietile:

 

 

     orice nod al grafului G este extremitate pentru cel puin o muchie din A;

     subgraful H = (V,A) este conex i fr cicluri.

 

Urmtorul rezultat stabilete n ce condiii exist aranjamentele descrise:

 

Graful G are arbori dac i numai dac este conex.

 

Amintim doar n treact faptul c exist o formul care stabilete numrul arborilor distinci din G.

 

S presupunem mai departe c fiecrei muchii eE i s-a asociat un cost c(e) ³ 0. Definim costul unui arbore H = (V,A) ca fiind suma costurilor muchiilor alctuitoare:

 

Rezult n final urmtoarea problem de optimizare combinatorial a crei rezolvare va fi prezentat n seciunea 3:

 

S se determine n graful G arborele H* de cost minim.

 

Exemplul 1.2 Muchiile grafului G din exemplul 1.1 pot fi aranjate i n alte moduri. Astfel, un cuplaj n G este o submulime C Ì E de muchii dou cte dou neadiacente. Existena acestor noi aranjamente este o chestiune banal ntruct orice muchie din G este un cuplaj. Interesante sunt problemele de optimizare care se pun n acest context:

 

        s se determine cuplajul C* cu cele mai multe muchii ( cuplajul maxim )

 

sau, n cazul n care muchiile din G sunt ponderate:

 

        s se determine cuplajul C* de pondere maxim.

 

(ca mai sus, ponderea unui cuplaj este dat de suma ponderilor muchiilor din cuplaj)

 

Este foarte important de menionat faptul c problemele de optimizare combinatorial provin n marea lor majoritate din diverse domenii de activitate, n special economic: astfel problema arborelui de cost minim din exemplul 1.1 modeleaz o larg varietate de situaii practice din domeniul reelelor de comunicaii (reele de calculatoare, de drumuri, televiziune prin cablu etc)

 

Optimizarea combinatorial are ca obiect rezolvarea problemelor specifice adic elaborarea de metode i algoritmi de gsire efectiv a celui mai bun aranjament din mulimea finit a tuturor aranjamentelor posibile.n continuare pentru aranjamentele unei probleme combinatoriale vom folosi termenul de soluie.

 

La prima vedere, s-ar prea c obiectul optimizrii combinatoriale este banal: Ce mare lucru este s gseti cel mai bun element dintr-o mulime finit?

n realitate, listarea tuturor soluiilor unei probleme combinatoriale, n vederea selectrii soluiei optime, este aproape imposibil de fcut deoarece numrul lor, dei finit, este de regul astronomic de mare chiar i n cazul unor probleme de talie moderat.

 

Exemplul 1.3 Pentru a nelege mai bine despre ce este vorba s considerm o alt problem tipic de optimizare combinatorial, problema comisvoiajorului:

Un comisvoiajor situat n localitatea 0 trebuie s viziteze n localiti 1,2,,n n final ntorcndu-se de unde a plecat. Cunoscnd distanele dintre localiti (sau costurile deplasrilor ntre localiti) el dorete s gseasc traseul cu lungimea total minim (sau costul total minim). Este clar c numrul total al traseelor posibile este n! , un traseu fiind perfect determinat de ordinea (permutarea) n care vor fi vizitate cele n localiti. O dat fixat aceast ordine calculul lungimii (costului) traseului corespunztor este o banal operaie de adunare a lungimilor (costurilor) tronsoanelor care compun traseul.

n cazul particular a n=20 de localiti de vizitat, cu un calculator n stare s examineze un miliard de trasee pe secund, gsirea traseului optim ar dura circa 800 de ani iar dac, n loc de 20 de localiti, am avea cu una mai mult, cutarea ar dura n jur de 16800 de ani!!

 

n lumina acestui exemplu, determinarea efectiv a unui anumit element dintr-o mulime finit (dar foarte numeroas㔅) de posibiliti este o chestiune serioas: am dori s gsim acest element n timp util i bineneles cu un efort de calcul rezonabil.

n termeni mai precii, am dori ca timpul de rezolvare a unei asemenea probleme s depind polinomial de dimensiunile problemei.

 

Pentru unele probleme de optimizare combinatorial acest lucru este posibil; despre aceste probleme vom spune c sunt uoare. Problema arborelui de cost minim sau problema cuplajului maxim (de pondere maxim) ,descrise n exemplele 1.1 i 1.2, sunt dovedite a fi probleme uoare.

 

Pentru marea majoritate a problemelor combinatoriale, gsirea soluiei optime n timp polinomial nu este nc posibil, altfel spus metodele exacte cunoscute necesit un timp de rulare care crete exponenial o dat cu creterea dimensiunilor problemei rezolvate. Mai mult exist bnuiala c, datorit structurii lor interne, nici nu va fi posibil vreodat elaborarea unor metode exacte de rezolvare cu comportament polinomial!

Din clasa acestor probleme, socotite grele, face parte i problema comisvoiajorlui din exemplul 1.3.

 

Din cele de mai sus nu trebuie neles c problemele grele sunt inabordabile. n dimensiune relativ moderat aceste probleme pot fi soluionate exact n timp rezonabil. Folosind metode de cutare din ce n ce mai sofisticate care exploateaz eficient structura combinatorial intern au putut fi rezolvate cu succes i probleme de dimensiuni apreciabile.Totui, nu se poate spune c aceste metode, orict de sofisticate ar fi ele, sunt n stare s fac fa oricrei probleme de acelai fel i mai mult, pot avea comportamente radical diferite pe probleme asemntoare i de aceeai talie.

 

Avnd n vedere aceste observaii, de mare importan, mai cu seam practic, sunt metodele i algoritmii care determin n timp polinomial o soluie acceptabil(suboptimal). Pentru aceste procedee, numite generic euristici, aprecierea eficacitii lor va fi dat de distana dintre soluia suboptimal i cea optim veritabil! Am putea aprecia c o anumit euristic este bun dac valoarea suboptimal a criteriului de performan ar fi, de exemplu, de cel puin 90% din valoarea optim!

Cteva modaliti de rezolvare a problemei comisvoiajorului sunt date n seciunea 4.

 

Cele mai multe probleme de optimizare combinatorial sunt modelate cu ajutorul teoriei grafurilor; exemplul1.1 este edificator n acest sens. Mai toate pot fi descrise alternativ prin programe liniare cu variabile ntregi, n special bivalente, de unde strnsa legtur dintre optimizarea combinatorial i programarea n numere ntregi.

 

Exemplul 1.4 Relum problema cuplajului maxim din exemplul 1.2. Atam fiecrei muchii eE o variabil boolean xe cu semnificaia:

 

 

Pentru fiecare nod v V, fie E(v) mulimea muchiilor din G care au o extremitate n v. Problema cuplajului maxim este perfect descris de programul bivalent:

 

 

 

2. Domenii de aplicare ale optimizrii combinatoriale

 

ntre problemele de optimizare combinatorial se gsesc:

 

        problema drumului de valoare minim ntre dou noduri ale unui graf;

        problema fluxului maxim;

        problema de afectare.

 

deja studiate n cursul Bazele Cercetrii Operaionale [10]. Ele intr, alturi de problema arborelui de cost minim n categoria problemelor uoare.

 

Lista problemelor grele este impresionant i se mbogete continuu. n afara problemei comisvoiajorului mai putem aminti urmtoarele probleme mai reprezentative:

 

2.1 Problema croirii n multe domenii cum ar fi industria mobilei, a sticlei, a hrtiei, a confeciilor, industria metalurgic apar frecvent probleme de debitare (sau croire) a unor repere din supori mai mari. Importana economic a acestor probleme rezid n dependena direct a reducerii consumului de materiale de utilizarea unor scheme eficiente de croire.

 

De obicei, clasificarea problemelor de croire se face dup dimensiunile relevante ale reperelor: avem probleme unidimensionale, bidimensionale sau tridimensionale. n croirea unidimensional de care ne vom ocupa mai mult, reperele se difereniaz printr-o singur dimensiune chiar dac ele au mai multe. Cazul tipic este ecela al debitrii unor bare de difrite lungimi din bare mai mari.Iat i o situaie concret: o firm produce un carton special n rulouri avnd o anumit lime. Clienii solicit rulouri avnd aceeai lungime ca i ruloul standard dar de limi mai mici. n acest caz reperele ca i suporii sunt bidimensionali dar relevant este o singur dimensiune limea.

 

Aspectul combinatorial al unei probleme de croire este dat de modalitile de tiere ale unui suport n repere, modaliti numite reete de croire.Chestiunea de optimizare const n a determina de cte ori una sau alta dintre reetele de croire trebuie folosit pentru producerea unor cantiti specificate de repere astfel nct numrul total de supori consumai s fie minim.

 

Problema de croire unidimensional va f studiat mai n amnunt n seciunea 6 din capitolul III.

2.2 Problema general a ordonanrii Elementele primare sunt:

 

      o mulime de utilaje;

      o mulime de repere (joburi) de realizat (ndeplinit).

 

Realizarea unui reper necesit efectuarea unei secvene de operaii pe (unele din) utilajele date.Ordinea de parcurgere a utilajelor poate fi aceeai pentru toate reperele sau poate diferi de la un reper la altul.Fiecare operaie necesit un anume timp, presupus cunoscut, i dou operaii distincte, executabile pe un acelai utilaj, nu pot fi programate simultan.Uneori pentru unele repere sunt impuse termene de livrare.

n aceste ipoteze,cum trebuie organizat lansarea reperelor n execuie astfel nct:

 

      timpul total de inactivitate al utilajelor s fie minim

sau

      durata de execuie a tuturor reperelor s fie minim

sau

      numrul reperelor al cror termen de livrare este depit s fie ct mai mic etc.

 

Exist o mare varietate de tipuri de probleme de ordonanare care se nscriu n acest enun general. Modelarea lor - prin programare n numere ntregi sau prin grafuri - este n general dificil, ca s nu mai vorbim de rezolvarea lor "exact", imposibil de realizat n timp rezonabil, chiar i atunci cnd numrul reperelor i al utilajelor este relativ mic. Ca urmare, au fost elaborate euristici de rezolvare suboptimal, marea lor diversitate fiind explicat prin aceea c ele ncearc s exploateze particularitile structurii acestor probleme, particulariti care pot s difere radical de la o problem la alta.

Unele cazuri particulare vor fi studiate n seciunea 5 a acestui capitol.

 

2.3 Problema alegerii traseelor O firm trebuie s satisfac un numr de cereri de aprovizionare ntr-o anumit perioad. Livrrile se fac de la un anumit depozit i sunt operate cu mai multe de mijloace de transport, fiecare cu o capacitate limitat. Fiecare vehicul pleac ncrcat de la depozit, viziteaz unul sau mai muli clieni, crora le livreaz comenzile fcute dup care, complet descrcat, se ntoarce la depozit pentru a fi eventual rencrcat. Problema care se pune n acest context este aceea de a stabili traseele de vizitare ale clienilor astfel nct distana total parcurs de vehicule s fie minim.

 

O posibilitate de rezolvare suboptimal este descris n seciunea 6 din acest capitol.

2.4 Problema orariilor ntr-o universitate trebuie programat activitatea de nvmnt pe urmtorul semestru. Se cunosc:

 

      numrul cursurilor care trebuie inute;

      numrul claselor disponibile;

      profesorii abilitai s in cursurile.

 

Cum trebuie fcut repartizarea profesorilor pe cursuri i a cursurilor pe clase astfel nct:

 

      dou cursuri diferite s nu fie programate n aceeai clas i n acelai timp;

      cursurile s fie atribuite profesorilor de specialitate;

      doi profesori cu aceeai specialitate s nu fie repartizai pe acelai curs.

 

O asemenea repartizare complex se numete orar i pn aici s-a formulat doar o problem de existen. "Optimizarea" elaborrii unui orar este o chestiune delicat existnd multe criterii de apreciere care nu ntotdeauna sunt concordante. Din punctul de vedere al studenilor un orar este "bun" dac minimizeaz totalul deplasrilor zilnice de la o clas la alta. Att pentru studeni ct i pentru profesori conteaz numrul "ferestrelor" adic al intervalelor de timp dintre dou activiti zilnice consecutive care ar trebui s fie ct mai mic, etc.

 

2.5 O problem de comunicaii prin satelit Zilnic, un mare volum de informaii TV, radio sau telefon se transmite prin satelii. Utilizarea sateliilor a devenit imperios necesar pentru asigurarea transmiterii informaiilor la mare distan. n mare, un satelit de comunicaii este un "releu": el preia semnalul unei staii terestre de emisie i l retransmite altei staii, de recepie.Dispozitivul de la bordul satelitului care realizeaz legtura dintre cele dou staii se numete transponder sau conector; sateliii moderni au pn la 24 de conectoare. Una din tehnologiile avansate de operare a sistemelor de comunicaii prin satelit este SS/TDMA (satellite switched time division multiple access) ; n cadrul acesteia fiecare conector de la bordul satelitului este atribuit - pentru un interval de timp - unei perechi de zone terestre (staii de emisie - recepie). Un set complet de atribuiri se va numi n continuare mod de conectare. Atribuirile ce compun un mod de conectare se efectueaz simultan de la bordul satelitului. O secven de moduri de conectare care permite realizarea unui program de legturi pe o perioad de timp se numete structur de conectare.

 

O problem important care apare n legtur cu tehnologia SS/TDMA este planificarea eficient n timp a momentelor de realizare ale atribuirilor ce compun o structur de conectare.

 

Trecem acum la formalizarea problemei. "Cererea" corespunztoare unei structuri de conectare poate fi reprezentat printr-o matrice:

 

D = [dij] 1£ i,j £ n

numit matrice de trafic unde:

 

n º numrul total de zone terestre ntre care trebuie realizate legturile;

 

dij º "lungimea" trenului de date necesar a fi transmis din zona i n zona j, lungime exprimat de regul prin timpul necesar transmiterii trenului de date respectiv.

 

Transmiterea acestor date implic o programare n timp a conectorilor de pe satelit pe diferite perechi de zone. Aceasta nseamn descompunerea matricii de trafic D ntr-un numr de matrici de aceeai dimensiune cu ea, numite matrici de conectare:

 

cu urmtoarele proprieti:

 

      pe fiecare rnd sau coloan din Dk exist cel mult un element nenul (altfel spus, n Dk exist cel mult n elemente nenule, oricare dou nesituate pe acelai rnd sau coloan. Aceasta revine la a spune c fiecare conector este atribuit la cel mult o pereche de zone;

      suma celor q matrici de conectare este egal cu matricea de trafic dat:

 

 

Rezult imediat c descompunerea matricii D n matrici cu proprietile de mai sus este posibil numai dac q ³ n.

 

Criteriul de performan ce trebuie avut n vedere n primul rnd este transmiterea datelor ntre diferitele zone n timpul cel mai scurt. Este clar c timpul necesar transmiterii datelor corespunztoare unui mod de conectare este dat de cea mai mare component a matricii de conectare aferente, astfel c timpul total asociat descompunerii (D1,D2,...,Dq) este:

 

 

Cu aceste pregtiri se obine urmtoarea problem de optimizare combinatorial:

 

S se determine o descompunere (D1,D2,...,Dq) a matricii de trafic D n matrici de conectare astfel nct timpul total de transmisie T s fie minim.

 

Se observ c dac q > n anumite trenuri de date dij din D vor fi fragmentate i transmise pe parcursul mai multor moduri de conectare. Impunnd condiia ca fiecare tren de date s fie transmis ntr-un singur mod de conectare rezult problema:

 

S se descompun matricea de trafic D n n matrici de conectare D1,D2,...,Dn

astfel nct timpul total de transmisie T s fie minim.

 

 

3. Problema arborelui de cost minim

 

Dat n seciunea 1 ca un prim exemplu de problem de optimizare combinatorial, problema arborelui de cost minim are numeroase aplicaii practice. Contextul general este urmtorul: un numr de puncte trebuie conectate ntre ele pentru facilitarea transmiterii unui anumit serviciu (telefon, TV, calculator) ntre puncte exist legturi poteniale a cror realizare implic un anumit cost. Problema care apare este aceea de a vedea ce legturi vor fi efectiv realizate stfel nct:

 

   oricare dou puncte s fie conectate direct sau indirect n vederea utilizrii serviciului;

   suma costurilor legturilor realizate s fie minim.

 

Exemplul 3.1 [6] Centrul regional de calculatoare X trebuie s instaleze un numr de linii speciale de comunicaii care s lege cinci utilizatori la un nou computer. Deoarece instalarea reelei este costisitoare conducerea centrului dorete ca lungimea total a liniilor instalate s fie ct mai mic. Dei computerul central poate fi conectat direct cu toi utilizatorii ar fi mai economic s fie instalate linii directe doar ctre unii, ceilali intrnd n reea prin legarea lor la utilizatorii deja conectai.Reeaua legturilor posibile este vizualizat prin graful din fig 3.1. Valorile numerice nscrise pe muchii reprezint distane n km.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Exemplul 3.2 Prefectura judeului X i-a fixat ca obiectiv modernizarea reelei drumurilor care leag ntre ele localitile 1,2,,8 reea vizualizat n fig. 3.2. Pe fiecare muchie este nscris o valoare numeric reprezentnd costul modernizrii tronsonului respectiv (n milioane lei). Din cauza bugetului limitat, prefectura dorete ca ntr-o prim etap s modernizeze numai unele drumuri astfel nct:

 

   ntre oricare dou localiti s se poat circula pe tronsoane modernizate;

   costul ntregii operaii de modernizare parial s fie minim.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figura 3.2

 

Rezolvarea problemelor de acest tip se face cu ajutorul unui algoritm foarte simplu, datorat lui Kruskal:

 

   selectarea muchiilor care vor forma arborele cutat se va face n ordinea cresctoare a costurilor;

   presupunnd c muchiile e1 , e2 ,, ek au fost deja selectate, urmtoarea muchie ek + 1 va fi astfel aleas nct s nu formeze ciclu cu (unele din) muchiile e1 , e2 ,, ek.

 

Este clar c procedura se oprete dup un numr finit de pai. Dac numrul total de muchii selectate este n 1, n fiind numrul nodurilor din graful original, s-a gsit un arbore de cost minim; altminteri, graful dat nu este conex!

 

Exemplul 3.3 Vom aplica algoritmul lui Kruskal n graful conex din fig. 3.1. Exist trei muchii cu costul minim 20;ele nu formeaz un ciclu astfel c ele pot fi selectate n orice ordine, de exemplu: {0,1} , {2,3} , {2,5}. Mai departe a fost aleas muchia {0,3} urmat de {3,4}; muchia {3,5}a fost respins deoarece forma un ciclu cu muchiile {2,3} i {2,5} deja selectate! Procedura s-a oprit deoarece graful are ase noduri i au fost alese cinci muchii.Arborele cu costul minim 120 este reprezentat n fig.3.3

 

Figura 3.3

 
 

 

 

 


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. Problema comisvoiajorului

 

Un comisvoiajor are de vizitat un numr de orae, la sfritul voiajului el ntorcndu-se n localitatea de plecare. Deplasarea dintr-o localitate n alta presupune anumite cheltuieli (sau distane de parcurs sau durate de mers).

 

In ce ordine trebuiesc vizitate oraele astfel nct costul total al deplasrii (sau lungimea traseului sau durata cltoriei) s fie minim?

 

Astfel enunat, problema comisvoiajorului (notat pe scurt TSP de la Travelling Salesman Problem) este una din cele mai grele probleme de optimizare combinatorial. Pe lng importana teoretic, ea are numeroase aplicaii practice. De exemplu, stabilirea celor mai "economice" trasee turistice ntr-un mare ora sau zon istoric (din punctul de vedere al costurilor sau distanelor) este o probem a comisvoiajorului. De asemenea, stabilirea ordinii n care un numr de operaii (joburi) vor fi executate pe un utilaj, astfel nct suma timpilor de pregtire ai utilajului s fie ct mai mic, este o problem de acelai tip.

 

4.1 Modelul matematic al problemei comisvoiajorului

 

S notm cu 0,1,...,n oraele problemei, 0 fiind oraul din care comisvoiajorul pleac i n care revine la terminarea cltoriei. Fie cij costul deplasrii din localitatea i n localitatea j ¹ i; punem cij = ¥ dac nu exist legtur direct ntre i i j sau n cazul i = j. Un traseu va fi descris cu ajutorul variabilelor bivalente :

 

 

Urmeaz a fi minimizat funcia:

(4.1.1)

Din orice ora i, comisvoiajorul trebuie s se ndrepte ctre o alt localitate, astfel c:

 

(4.1.2)

 

In orice ora ar ajunge, comisvoiajorul vine dintr-o localitate anterior vizitat, aa c:

 

(4.1.3)

 

Observm c ansamblul (4.1.1) - (4.1.3) constituie modelul matematic (PA) al unei probleme generale de afectare. O examinare mai atent a problemei arat c restriciile (4.1.2) i (4.1.3) nu definesc numai trasee ce trec prin toate oraele (o singur dat!) ci i "reuniuni" de circuite disjuncte mai mici! Astfel, ntr-o problem cu 7 orae 0,1,...,6 ansamblul:

 

x03 = x35 = x50 = x21 = x14 = x46 = x67 = x72 = 1 , xij = 0 n rest

 

satisface restriciile (4.1.2) i (4.1.3) dar nu constituie un traseu complet aa cum se vede din figura 4.1

 

 

 

Fig. 4.1

 

Pentru evitarea ecestui neajuns asociem oraelor 1,2,...,n , diferite de localitatea de plecare i sosire 0, variabilele y1,y2,...,yn i introducem inegalitile:

 

yi - yj + nxij £ n - 1 i , j = 1,2,...,n ; i ¹ j (4.1.4)

 

In principiu noile variabile pot lua orice valoare real. Vom arta c dac x = (xij) determin un traseu complet atunci exist valori numerice y1,y2,...,yn care mpreun cu xij satisfac relaiile (4.1.4). Intr-adevr, definim yi ca fiind numrul de ordine al localitii i n cadrul traseului determinat de x. Pentru i ¹ j dou situaii sunt posibile:

 

      localitatea j nu urmeaz imediat dup localitatea i. Atunci xij = 0 i (4.1.4) devine yi - yj £ n - 1 ceeace este adevrat avnd n vedere semnificaia acordat valorilor y1,y2,...,yn.

      localitatea j urmeaz imediat dup localitatea i. Atunci yj = yi + 1 , xij = 1 i (4.1.4) se verific cu egalitate.

 

S presupunem acum c z = (xij) definete o reuniune de "subtrasee" disjuncte. Alegem unul care nu trece prin localitatea 0 i fie k numrul deplasrilor cel compun. Presupunnd c ar exista valori numerice y1,y2,...,yn care s satisfac (4.1.4) nsumm pe acelea corespunztoare deplasrilor de la un ora la altul din subtraseul ales. Obinem nk £ (n - 1)k ceeace este evident fals.

 

In concluzie, ansamblul (4.1.1) - (4.1.4) constituie modelul "corect" al problemei comisvoiajorului. Este vorba de un program mixt ce utilizeaz att variabile ntregi (bivalente) ct i variabile care pot lua orice valoare. In continuarea unei observaii anterioare, putem spune c problema comisvoiajorului (TSP) este o problem de afectare (PA) (ansamblul (4.1.1) - (4.1.3)) cu restriciile speciale (4.1.4).

 

In consideraiile de mai sus costurile cij nu sunt "simetrice" adic este posibil ca cij ¹ cji. Problema simetric a comisvoiajorului se caracterizeaz prin cij = cji; aceasta se ntmpl dac , de exemplu, cij sunt distane sau timpi de parcurgere.

Un caz particular al problemei simetrice este aa numita problem euclidian a comisvoiajorului n care distanele cij satisfac inegalitatea triunghiului :

 

cik £ cij + cjk (") i,j,k.

 

4.2 Un algoritm exact de rezolvare a problemei comisvoiajorului

 

Urmtorul algoritm, de tip B&B, reduce rezolvarea TSP la rezolvarea unei liste de probleme de afectare. El s-a dovedit suficient de robust pentru probleme asimetrice cu un numr moderat de orae. Principalul dezavantaj l reprezint faptul c numrul problemelor de afectare de rezolvat este impredictibil i poate fi imens n cazul situaiilr reale.Algoritmul este datorat lui Eastman. Ca orice procedur de tip B&B, el utilizeaz:

 

      o "locaie" xCMB care va reine "cel mai bun" traseu gsit de algoritm pn la un moment dat;

      o variabil zCMB care reine costul traseului memorat n xCMB;

      o list L de probleme de afectare asemntoare problemei (PA) i care difer de problema (PA) iniial prin anumite costuri cij schimbate n ¥;

 

La start:

 

      xCMB poate fi locaia "vid" n care caz zCMB = ¥ sau reine un traseu arbitrar ales sau generat printr-o metod euristic, xCMB fiind iniializat cu costul aferent acestui traseu;

      lista L cuprinde numai problema (PA) iniial, determinat de (4.1.1) - (4.1.3);

 

Pasul 1. Dac lista L este vid Stop. Altminteri, selecteaz o problem din lista L . Problema aleas se terge din L . Se trece la:

Pasul 2. Se rezolv problema selectat. Dac valoarea funciei obiectiv este ³ zCMB se revine la pasul 1. Altminteri, se trece la:

Pasul 3. Dac soluia optim este un traseu complet se actualizeaz xCMB i zCMB dup care se revine la pasul 1. Altminteri se trece la:

Pasul 4. (Soluia optim nu este un traseu ci o reuniune de "subtrasee mai mici"). Din soluia optim se selecteaz circuitul cu cel mai mic numr de arce. Pentru fiecare arc (i,j) din circuitul ales (pentru care xij = 1) se adaug la lista L problema obinut din cea rezolvat punnd cij = ¥. Se revine la pasul 1.

 

Observaii: 1) Raiunea pasului 4 este clar: dac i j k ... l i este circuitul selectat este clar c n traseul optim vom avea:

xij = 0 sau xjk = 0 sau ... sau xli = 0.

In consecin, vom cuta traseul optimal printre cele n care xij = 0 i dac nu este acolo printre cele n care xjk = 0 .a.m.d. Limitarea la traseele n care xij = 0 se face efectund schimbarea cij = ¥.

 

2) La pasul 4, n lista L vor apare attea probleme cte arce are circuitul selectat; de aceea se alege circuitul cu cel mai mic numr de arce!

 

In raport cu termenii generali ai unei metode B&B, ramificarea are loc la pasul 4 n timp ce mrginirea se efectueaz la pasul 2.

 

Exemplul 4.2.1 Se consider problema asimetric a comisvoiajorului cu cinci orae, definit de urmtoarea matrice a costurilor:

 

 

Orae

0

1

2

3

4

 

0

¥

10

25

25

10

 

1

1

¥

10

15

2

 

2

8

9

¥

20

10

 

3

14

10

24

¥

15

 

4

10

8

25

27

¥

 

Tabelul 4.1

 

Start. Se pleac cu traseul 0 1 2 3 4 0, care se reine n xCMB i al crui cost este zCMB = 10 + 10 + 20 + 15 + 10 = 65. Lista L a problemelor de afectare ce urmeaz a fi rezolvate cuprinde numai problema iniial (PA).

 

Iteraia 1. Se terge (PA) din lista L i se rezolv. Se obine soluia optim:

 

x04 = x40 =x12 = x23 = x31 = 1 , xij = 0 n rest

 

ce corespunde reuniunii urmtoarelor subtrasee:

 

0 4 0 i 1 2 3 1

 

Selectm subtraseul 0 4 0 i adugm la L problemele PA1 i PA2 derivate din PA nlocuind c04 respectiv c40 cu ¥ .

 

Iteraia 2. Selectm problema PA1 i o rezolvm. Lista L va cuprinde mai departe numai problema PA2. Pentru PA1 se gsete soluia optim:

 

x03 = x12 = x24 = x31 = x40 = 1 , xij = 0 n rest.

 

care corespunde traseului complet 0 3 1 2 4 0. Costul su este 65 = zCMB. Nu am gsit deci un traseu mai bun dect cel pe care-l avem n xCMB.

 

Iteraia 3. Rezolvm problema PA2, singura rmas n L .Se obine soluia optim:

x04 = x12 = x23 = x30 = x41 = 1 , xij = 0 n rest

 

care corespunde traseului 0 4 1 2 3 0 . Costul noului traseu este 62 < zCMB ,drept care l reinem n xCMB i actualizm zCMB = 62.

Deoarece lista L este acum vid traseul reinut n xCMB este optim.

 

4.3 Metode euristice de rezolvare aproximativ a problemei comisvoiajorului

 

De obicei, soluia optim a unei TSP este foarte greu de gsit (dac nu chiar imposibil de gsit) atunci cnd numrul oraelor de vizitat este mare (peste 50). Pentru determinarea unei soluii mcar acceptabile au fost elaborate mai multe procedee euristice. Aceste procedee merit atenie din dou puncte de vedere:

 

      se poate da un "certificat de garanie" pentru soluia obinut n sensul c este posibil evaluarea "deprtrii" maxime de soluia optim;

      soluia aproximativ este gsit cu un efort de calcul relativ moderat i ntr-un timp rezonabil, aceasta nsemnnd c cei doi parametri depind polinomial de dimensiunea problemei (adic numrul de orae);

In multe situaii practice, procedeele euristice au condus chiar la soluia optim dar acest lucru a fost confirmat numai prin aplicarea unui algoritm exact.

In principiu, o metod euristic construiete o soluie prin tatonare, din aproape n aproape, fcnd la fiecare pas, cea mai bun alegere posibil. Din nefericire, aceast "schem" nu conduce, de regul, la cea mai bun alegere global.

In continuare, vom prezenta mai multe euristici pentru rezolvarea problemei euclidiene a comisvoiajorului, adic a problemei n care cij sunt distane ce satisfac:

 

      condiia de simetrie: cij = cji:

      inegalitatea triunghiului cik £ cij + cjk;

 

Euristica E1 (mergi la cel mai apropiat vecin)

 

      se pleac din localitatea 0 ctre localitatea cea mai apropiat;

      din ultima localitate vizitat se pleac ctre cea mai apropiat localitate nevizitat; n caz c nu mai exist localiti nevizitate se revine n locul de plecare;

 

Exemplul 4.3.1 S considerm cele 13 orae din reeaua laticial din figura 4.2; distanele dintre orae sunt date n tabelul 4.2.

 

Aplicnd euristica descris se obine traseul din figura 4.3 cu lungimea 5099.

 

 

 

 

 

 

 

 

 

 

 

Figura 4.2 Figura 4.3

 

Localitatea

0

1

2

3

4

5

6

7

8

9

10

11

12

 

0

¥

100

141

360

500

400

1000

1019

1204

806

632

1004

1204

 

1

 

¥

100

282

447

412

1004

1004

1140

721

538

905

1170

 

2

 

 

¥

223

360

316

905

905

1063

670

509

900

1140

 

3

 

 

 

¥

200

360

854

806

860

447

300

707

921

 

4

 

 

 

 

¥

300

670

608

707

400

360

761

900

 

5

 

 

 

 

 

¥

600

632

943

700

632

1044

1200

 

6

 

 

 

 

 

 

¥

200

806

921

1000

1345

1341

 

7

 

 

 

 

 

 

 

¥

608

781

894

1204

1166

 

8

 

 

 

 

 

 

 

 

¥

509

728

824

640

 

9

 

 

 

 

 

 

 

 

 

¥

223

424

500

 

10

 

 

 

 

 

 

 

 

 

 

¥

412

632

 

11

 

 

 

 

 

 

 

 

 

 

 

¥

360

 

12

 

 

 

 

 

 

 

 

 

 

 

 

¥

 

Tabelul 4.2

 

Euristica E2 (Ajustare local)

 

      se pleac de la un traseu complet, determinat fie "la ntmplare" fie printr-o alt euristic;

      se caut dou arce (u,v) i (x,y) ale traseului care se ncrucieaz - ca n figura 4.4 a) - i se compar distanele cuv + cxy cu cux + cvy. Dac cuv + cxy > cux + cvy se nlocuiesc arcele (u,v) i (x,y) cu (u,x) i (v,y) obinndu-se un traseu de lungime mai mic (vezi figura 4.4 b));

      procedura se oprete n momentul n care nu mai exist situaii similare cu cea descris;

 

 

 

 

 

 

 

Figura 4.4 a) Figura 4.4 b)

 

Exemplul 4.3.2 Pentru ilustrare s considerm traseul obinut din euristica E1. In figura 4.3 este vizibil ncruciarea arcelor (10,11) i (12,0). Deoarece:

 

c10,11 + c12,0 = 424 +1264 = 1688 > 1636 = 632 + 1004 = c10,12 + c11,0

 

un traseu mai scurt se obine folosind arcele (10,12) i (11,0) aa cum se arat n figura 4.5 a).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

a)                                                                                                                                                                  b)

Figura 4.5

 

Lungimea noului traseu este: 5099 - (1688 - 1636) = 5047.

Rezolvnd analog ncruciarea nou aprut a arcelor (1,2) i (11,0) - vezi figura 4.5 a) - n care:

 

c1,2 + c11,0 = 100 + 1004 = 1104 > 1046 = 141 + 905 = c0,2 + c11,1

 

se obine traseul din figura 4.5 b) cu lungimea: 5047 - (1104 - 1046) = 4989.

Deoarece n noul traseu nu mai apar ncruciri euristica E2 se oprete.

 

Urmtoarele procedee sunt "mai performante" dar necesit i un efort de calcul "mai mare".

 

Euristica E3

 

      Se determin un arbore H de lungime minim (aceasta este o problem "uoar" rezolvabil de exemplu cu algoritmul lui Kruskal, vezi seiunea 3);

      fiecare muchie a arborelui H e nlocuiete cu dou muchii de aceeai lungime. Se obine un multigraf H' n care fiecare nod are grad par. Conform teoremei lui Euler n H' exist un ciclu eulerian; cu alte cuvinte, este posibil s se viziteze oraele astfel nct fiecare muchie a multigrafului H' s fie parcurs o singur dat.

Fie:

0 x y ¼ u v 0 (4.3.1)

 

succesiunea n care muchiile multigrafului H' au fost parcurse. Lungimea acestui "traseu" este de dou ori mai mare dect lungimea arborelui minimal H. In aceast secven, unul sau mai multe orae apar de mai multe ori. Vom proceda atunci la urmtoarea operaie de scurtcircuitare:

 

      n succesiunea (4.3.1) se determin prima triplet de orae succesiv vizitate

 

i j k

 

cu proprietatea c oraul j "din mijloc" mai apare ulterior n succesiune. Se nlocuiete secvena i j k cu arcul i k. Prin aceast scurtcircuitare:

 

      fiecare ora continu s fie vizitat cel puin o dat;

      noul traseu este mai scurt pentru c cij + cjk ³ cik;

 

Operaia de scurtcircuitare se repet pn cnd n secvena (4.3.1) "actualizat" fiecare ora, cu excepia localitii 0 apare o singur dat.

Se poate demonstra c lungimea traseului obinut prin aceast euristic este cel mult de dou ori mai mare dect lungimea traseului optim (n practic lucrurile stau ns mai bine...)

 

 

 

 

 

 

 

 

 

 

 

 

 

Figura 4.6

 

Exemplul 4.3.3 In figura 4.6 este vizualizat un arbore minimal H pentru graful din figura 4.2. Un ciclu eulerian n multigraful H', dedus din H prin "dublarea" muchiilor acestuia, arat astfel:

 

0 1 2 3 4 5 6 7 6 5 4 3 10 9 8 9 10 11 12 11 10 3 2 1 0

 

n succesiunea 0 1 2 de lungime c01 + c12 = 100 + 100 = 200 oraul 1 mai este vizitat "n final". Conform celor de mai sus, vom nlocui aceast succesiune cu arcul direct 0 2 de lungime 141 < 200. Rezult traseul:

 

0 2 3 4 5 6 7 6 5 4 3 10 9 8 9 10 11 12 11 10 3 2 1 0

 

Mai departe succesiunea 0 2 3 de lungime 141 + 223 = 364 se nlocuiete cu arcul direct 0 3 cu lungimea 360, pentru c prin oraul 2 se mai trece o dat!

Continund procesul de scurtcircuitare se obine n final traseul complet:

 

0 7 6 5 4 8 9 12 11 10 3 2 1 0

 

vizualizat n figura 4.7; lungimea sa este 5330. Rezolvnd "ncruciarea" arcelor (0,7) i (5,4) se obine traseul mai scurt din figura 4.8 cu lungimea 5019.

 

 

 

 

 

Figura 4.7 Figura 4.8

 

Menionm faptul c euristica descris poate da rezultate diferite, unele mai bune altele mai puin bune, funcie de alegerea arborelui minimal H i a ciclului eulerian n multigraful asociat H'.

 

Euristica E4

 

Aceast procedur, datorat lui Cristofides, este o rafinare a euristicii precedente. Deoarece suma gradelor nodurilor din arborele H este par, numrul nodurilor de grad impar este par! Folosind numai aceste noduri i muchiile dintre ele vom determina cuplajul C de pondere minim, ponderile muchiilor luate n calcul fiind distanele dintre extremiti.

Fie H' graful rezultat din H prin adugarea muchiilor cuplajului C, cu meniunea c dac ntre dou noduri avem o muchie n H i o alta n C, graful H' va avea ntre nodurile respective dou muchii.Prin construcie, n H' fiecare nod are grad par, astfel c H' are un ciclu eulerian. Plecnd de aici i utiliznd tehnica scurtcircuitrii se ajunge la un traseu complet.

 

Se poate arta c lungimea acestui traseu nu depete 3/2 din lungimea traseului optim.

 

Exemplul 4.3.4 Relum problema euclidian a comisvoiajorului definit n figura 4.2 i tabelul 4.2. Un arbore minimal cu lungimea 3527 apare n figura 4.6. Nodurile din H de grad impar sunt 0, 3, 7, 8 i 12. Prin simpla inspecie (sau utiliznd un algoritm de determinare a cuplajului de pondere minim n subgraful complet ale crui noduri sunt 0, 3, 7, 8 i 12) se constat c muchiile {0,3} , {7,8} i {10,12} au cea mai mic pondere total: c03 + c78 + c10,12 = 360 + 608 + 632 = 1600. Adugnd cele trei muchii la arborele H se obine graful H' din figura 4.9. Vizitnd oraele 0,1,...,12 n ordinea:

 

0 1 2 3 4 5 6 7 8 9 10 11 12 10 3 0

 

toate muchiile grafului H' vor fi parcurse o singur dat. "Scurtcircuitnd" secvenele 2 3 4 i 9 10 11 se obine un traseu complet cu lungimea 4853. Invitm cititorul s se conving prin desen c n acest traseu arcele (9,11) i (12,10) respectiv (1,2) i (3,0) se ncrucieaz. Rezolvnd i aceste ncruciri se obine n final traseul din figura 4.10 cu lungimea 4672.

Ca i euristica precedent i E4 poate conduce la rezultate diferite, funcie de alegerea arborelui minimal H, al cuplajului C i al ciclului eulerian n (multi)graful H'.

 

 

 

 

 

 

 

 

 

 

 

 

 


Figura 4.9 Figura 4.10

 

 

5. Introducere n problema ordonanrii

 

5.1 Problema ordonanrii. Aspecte generale

 

Considerm un proces tehnologic n care, asupra unor obiecte (materie prim, semifabricate) denumite generic repere, se efectueaz o serie de transformri cantitative i/sau calitative n vederea obinerii unor produse (acestea pot fi produse finite sau semifabricate mai complexe ce devin repere n alte procese tehnologice). Transformrile (prelucrrile) pe care le sufer un reper n diferitele faze ale procesului tehnologic se execut pe utilaje specializate. Pentru precizia limbajului vom numi operaie totalitatea aciunilor de prelucrare efectuate asupra unui reper pe un anumit utilaj. In principiu, un utilaj poate executa operaii aferente mai multor repere dar, la un moment dat, nu poate executa dect o singur operaie.

Efectuarea unei operaii presupune utilizarea unor resurse materiale sau bneti; avem n vedere n primul rnd durata operaiei care se "extrage" din fondul de timp productiv al utilajului pe care se execut operaia respectiv.

 

In contextul descris, problema ordonanrii reperelor pe utilaje nseamn programarea n timp a operaiilor necesare obinerii diferitelor produse din nomenclatorul procesului tehnologic studiat, adic stabilirea ordinii i a termenelor la care urmeaz a fi efectuate aceste operaii.

 

In elaborarea unui program concret de lansare n fabricaie trebuie s se in seama de un mare numr de factori cei mai muli fiind specifici procesului tehnologic studiat. Vom meniona pe cei mai importani fr pretenia de epuizare a subiectului.

 

      Cu puine excepii, planificarea nu se refer la repere individualizate ci la loturi de repere. n aceast situaie, este posibil ca dup ce o anumit operaie a fost executat pe o parte a unui lot de repere, utilajul s fie eliberat i pregtit pentru o operaie ce se efectueaz pe reperele altui lot, restul reperelor din lotul anterior urmnd a fi prelucrat mai trziu. Deoarece n procesul de modelare un lot de repere identice este asimilat cu un singur reper (dar cu o durat de execuie proporional cu mrimea lotului), situaia descris mai sus este echivalent cu ntreruperea unei operaii i reluarea ei la un moment ulterior. In consecin, lansarea n execuie a reperelor pe utilaje poate fi conceput cu acceptarea sau neacceptarea ipotezei de ntrerupere a operaiilor.

 

      Ordinea n care se execut cel puin unele din operaiile aferente unui reper este esenial n foarte multe cazuri practice. Ca i n analiza drumului critic, condiionrile dintre operaiile unui reper pot fi complet descrise cu ajutorul relaiei de preceden direct: operaia a precede direct operaia b dac b poate fi executat imediat dup terminarea operaiei a. Putem vizualiza structura tehnologiei de fabricaie a unui reper printr-un graf orientat ale crui noduri sunt operaiile reperului n cauz, arcele reprezentnd precedenele directe dintre operaii.

Din punctul de vedere al ordinii n care se execut operaiile, problemele de ordonanare implicnd utilizarea a cel puin dou maini se clasific n trei categorii:

 

1) ordinea n care se execut operaiile oricrui reper este neesenial (open shop);

2) toate reperele parcurg utilajele ntr-o aceeai ordine (flow shop);

3) fiecare reper parcurge utilajele ntr-o anumit ordine definit de tehnologia de fabricaie a reperului (job shop);

 

      In practic, pentru orice reper (sau lot de repere) exist un termen de predare (livrare) la care toate operaiile trebuiesc ncheiate; n consecin, un program concret de lansare n execuie va fi apreciat ca admisibil dac operaiile fiecrui reper sunt ncheiate naintea termenului de predare.

 

      De cele mai multe ori, pentru a fi siguri c termenele de predare vor fi respectate, planificatorii i fixeaz pentru fiecare reper (sau lot de repere) un termen "intern" de predare care devanseaz mai mult sau mai puin, funcie de specificul situaiei concrete, termenele de livrare. Exist i alte raiuni care impun asemenea termene, ca de exemplu eliberarea utilajului la o anumit dat n vederea executrii altor comenzi. Aceste termene "interne", denumite de obicei termene impuse, sunt foarte utile n aprecierea diferitelor programe posibile de lansare n execuie n sensul c un program va fi socotit mai bun dect altul dac ntrzierile fa de termenele impuse vor fi mai mici fie pe total fie individual.

 

      Intr-o situaie concret, toate programele admisibile de ordonanare raporteaz termenele de execuie ale operaiilor la un acelai moment de referin: zero sau o dat calendaristic. Deseori se ntmpl ca unele din utilajele necesare prelucrrii reperelor situaiei s nu fie disponibile la momentul de referin, fiind antrenate n executarea altor comenzi. In raport cu momentul de referin ales de planificator, fiecare utilaj va avea un termen de eliberare de la care el devine disponibil (accesibil) i un program viabil (realist) de ordonanare trebuie s in seama de aceste termene.O chestiune similar se pune i n cazul reperelor care nu ntotdeauna sunt disponibile la momentul de referin ci la anumite termene minime de lansare n execuie.

 

      De obicei, pentru a executa o anumit operaie, utilajul desemnat trebuie pregtit (reglat). Exist cazuri n care timpul de pregtire este apreciabil i trebuie luat n considerare n elaborarea unui program realist de ordonanare. Lucrurile se complic foarte mult dac avem n vedere faptul c timpul de pregtire nu depinde numai de operaia ce urmeaz a fi executat ci i de operaia anterior executat pe acelai utilaj.

 

      Este posibil ca, pentru executarea unei operaii, s fie disponibile mai multe utilaje, fie identice, fie neidentice ca performan. Este clar c, n al doilea caz, durata efectiv de execuie a operaiei depinde de performanele utilajului desemnat.

 

Cu toate c lista factorilor restrictivi ar putea fi continuat, situaiile concrete de ordonanare implic un numr enorm de programe admisibile. Se impune alegerea unui criteriu de performan care s clasifice aceste programe. Criteriile pot diferi de la o situaie la alta i chiar pentru una i aceeai situaie se pot formula criterii independente (care s conduc la soluii diferite). Vom cita, cu titlu informativ, cteva din criteriile de performan ce pot fi avute n vedere:

 

      minimizarea termenului la care toate operaiile de prelucrare ale reperelor sunt ncheiate;

      minimizarea sumei ntrzierilor fa de termenele impuse;

      minimizarea celei mai mari ntrzieri fa de termenele impuse;

      minimizarea numrului de repere ntrziate (fa de termenele impuse);

      minimizarea sumei timpilor de pregtire - n cazul mai multor repere i a unui singur utilaj;

 

Este clar c din combinarea factorilor mai sus amintii i a criteriilor de performan adecvate rezult o mare varietate de probleme de ordonanare. Cercetrile n domeniu - unele de ordin exclusiv "bibliografic" - au condus la identificarea a peste 3000 de probleme diferite.

Pentru uurarea activitii de inventariere i clasificare a problemelor de ordonanare a fost introdus eticheta a / b / g n care:

 

      a este un cmp ce conine informaii privind numrul i caracteristicile utilajelor precum i ordinea de parcurgere a acestora;

 

      b este un cmp ce coine informaii privitoare la operaii: termene impuse, termene de livrare,termene de eliberare ale utilajelor, precedenele dintre operaii (dac exist), posibilitatea de a intrerupe operaiile etc;

 

      g este un cmp care specific criteriul de performan utilizat;

 

In marea lor ,majoritate, problemele de ordonanare sunt dificile n sensul c soluia optim este foarte greu de gsit dac nu chiar imposibil de gsit n timp rezonabil chiar i pentru probleme de gabarit "moderat". Acesta este i motivul (a cta oar?) pentru care n asemenea situaii se ncearc o rezolvare "aproximativ" bazat pe metode euristice.

 

5.2 Ordonanarea pe o main

 

Un numr de repere (joburi) codificate 1,2,...,n trebuiesc lansate n execuie pe un singur utilaj.

1) Fiecrui reper i sunt asociate urmtoarele date:

 

      durata pj;

      termenul impus dj;

      termenul minim de lansare n execuie rj;

      termenul de livrare ;

      timpul de pregtire pij al utilajului pentru trecerea de la jobul i la jobul j;

 

Este clar c rj + pj £ dj £ . Unele dintre aceste date pot fi ignorate ntr-un caz concret sau altul; n orice caz "obligatorii" sunt duratele i n cele mai multe cazuri termenele impuse.

 

2) In ansamblul lor joburile pot fi:

 

      independente, putnd fi lansate n fabricaie n orice ordine;

      intercondiionate;

 

3) Joburile pot fi executate:

 

      cu ntrerupere;

      fr ntrerupere;

 

4) Fiecrui job i se ataeaz o variabil Cj reprezentnd momentul terminrii execuiei sale.

Not: toate termenele impuse, de livrare, de terminare sunt raportate la un acelai moment de referin 0 astfel c toate sunt exprimate prin numere reale nenegative.

 

5) Calitatea unui program de lansare n execuie a joburilor poate fi evaluat prin mai multe criterii de performan.

 

a) de tip loc ngust:

 

      minimizarea ntrzierii maxime:

      minimizarea costului maxim datorat ntrzierilor:

unde fj(Cj) este o funcie nedescresctoare n variabil Cj cu fj(Cj) = 0 dac Cj £ dj;

 

b) de tip aditiv:

 

      minimizarea sumei costurilor datorate ntrzierilor: ;

      minimizarea sumei ponderate a termenelor de terminare: ;

      minimizarea sumei ntrzierilor efective: ;

      minimizarea numrului de joburi ntrziate: unde

;

 

c) care depind nu numai de caracteristicile individuale ale joburilor dar i de ordinea n care sunt lansate n execuie: ;

 

6) Codificarea a / b / g va avea, pentru problemele de ordonanare pe o main, urmtoarea alctuire:

      a = 1;

      indicatorul b va avea trei cmpuri b º ( ¾ , ¾ , ¾ ). In primul cmp se trec datele opionale rj,dj,,pij luate n considerare. In al doilea cmp se specific existena intercondiionrilor prin simbolul p. In ultimul cmp se indic posibilitatea ntreruperii execuiei unui job prin simbolul P.

      indicatorul g specific funcia de optimizat.

 

7) Se observ uor c prin combinarea tuturor elementelor amintite mai sus se obine o mare varietate de situaii de ordonanare pe o main. Problemele asociate acestor situaii se mpart n:

 

      probleme uoare: probleme pentru care se cunosc metode exacte de rezolvare ce determin soluia optim n timp polinomial;

      probleme grele: probleme pentru care metodele exacte de rezolvare cunoscute nu sunt polinomiale. Pentru rezolvarea aproximativ a acestor probleme se utilizeaz diferite euristici.

      probleme nedecise.

 

Cteva probleme de ordonanare "uoare" ,mpreun cu metodele adecvate de rezolvare, vor fi prezentate n continuare.

 

1) 1 / dj / Lmax In aceast problem se cunosc termenele impuse i se cere ordonarea reperelor astfel nct s se minimizeze ntrzierea maxim.

 

Soluia optim se obine aplicnd regula : are prioritate jobul cu termenul impus cel mai mic.

 

Exemplul 5.2.1 Pentru situaia cu datele:

Reper

1

2

3

4

5

6

7

Durata pj

3

4

4

6

9

11

15

Termene impuse dj

22

28

36

21

15

35

31

 

Tabelul 5.1

 

durata de execuie a tuturor reperelor este 3 + 4 + 4 + 4 + 6 + 9 + 11 + 12 = 52 uniti de timp indiferent de ordinea n care sunt lansate n prelucrare; ordinea n care se minimizeaz ntrzierea maxim este 5 4 1 2 7 6 3.

 

 

Reper j

5

4

1

2

7

6

3

Moment de terminare Cj

9

15

18

22

37

48

52

Intrziere fa de termenul impus

-

-

-

-

6

13

16 = Lmax

Tabelul 5.2

 

2) 1 / dj , p / Lmax Noua problem difer de precedenta prin existena unor relaii de preceden ntre unele operaii. Ea se rezolv foarte simplu prin regula: dintre reperele nc neprogramate i fr succesori direci se programeaz "cel mai trziu" reperul cu cel mai mare termen impus.

 

3) 1 / - / S wjCj In aceast situaie, se urmrete minimizarea sumei ponderate a termenelor de terminare. Reperele vor fi lansate n ordinea n care rapoartele pj/wj formeaz un ir nedescresctor.

 

 

 

Exemplul 5.2.2

 

Reper j

1

2

3

4

 

 

 

Durata pj

15

28

6

10

 

programul

 

Ponderea wj

3

7

1

5

Þ

optim de

4 2 1 3

pj/wj

5

4

6

2

 

lansare

 

 

Tabelul 5.3

 

4) 1 / / Fa de prima problem, acum se dau termene de livrare care, spre deosebire de termenele impuse, trebuiesc respectate. In plus, se urmrete minimizarea sumei termenelor de terminare ale operaiilor. Urmtorul algoritm rezolv problema indicnd, dac este cazul, incompatibilitatea ei.

Vom nota cu S mulimea reperelor neprogramate.

 

Start S = {1,2,...,n}

Pasul 1. Se determin mulimea: C = {k S } Dac C este vid Stop. Altminteri:

Pasul 2. Se selecteaz reperul k* C cu cea mai mare durat: i se programeaz cel mai trziu.

Pasul 3. Se face actualizarea S = S \ {k*} i se revine la pasul 1.

Deoarece la fiecare iteraie se programeaz un reper, algoritmul se oprete dup n - 1 iteraii.

 

Exemplul 5.2.3 In tabelul 5.4 se dau urmtoarele date privitoare la opt repere.

 

 

 

Reper

1

2

3

4

5

6

7

8

 

Durata

10

7

4

8

5

2

9

5

 

Termene de livrare

35

50

61

59

15

55

19

28

 

Tabelul 5.4

 

(aa cum s-a mai spus, termenele de livrare sunt raportate la momentul de referin 0)

 

Start S = {1,2,3,4,5,6,7,8}

 

Iteraia 1.

 

Pasul 1. =50 Þ C = {2,3,4,6};

Pasul 2. = 8 = p4 Þ se programeaz la sfrit reperul 4;

Pasul 3. S = {1,2,3,5,6,7,8}.

 

Iteraia 2.

Pasul 1. =50 - 8 = 42 Þ C = {2,3,6};

Pasul 2. = 7 = p2 Þ se programeaz la sfrit reperul 2;

Pasul 3. S = {1,3,5,6,7,8}.

 

 

Iteraia 3.

Pasul 1. =42 - 7 = 35 Þ C = {1,3,6};

Pasul 2. = 10 = p1 Þ se programeaz la sfrit reperul 1;

Pasul 3. S = {3,5,6,7,8}.

 

.a.m.d. Dup apte iteraii se obin rezultatele sintetizate n urmtorul tabel:

 

Reper j

6

5

7

3

8

1

2

4

Durata pj

2

5

9

4

5

10

7

8

Termen de ncepere

0

2

7

16

20

25

35

42

Termen de terminare Cj

2

7

16

20

25

35

42

50

Termen de livrare

55

15

19

61

28

35

50

59

S Cj

2

9

25

45

70

105

147

197

Tabelul 5.5

 

4)Alte exemple de probleme "uoare" sunt 1 / dj / S Uj n care se minimizeaz suma joburilor ntrziate sau 1 / dj / S wjCj n care se minimizeaz suma ponderat a termenelor de terminare.

 

Problema 1 / rj , dj / Lmax este recunoscut a fi o problem "dificil". Dac se compar noua situaie cu cea din problema "uoar" 1 / dj / Lmax se constat c "dificultatea" rezolvrii se datoreaz prezenei termenelor de disponibilitate rj. Aici este interesant de menionat faptul c dac este permis ntreruperea operaiilor, problemele 1 / rj , dj,P / Lmax sau fmax i chiar 1 / rj , dj, p, P / Lmax sau fmax sunt "uoare".

Deasemenea dificil este i problema 1 / dj / S Tj n care se minimizeaz suma ntrzierilor efective.

Despre problema 1 / rj, p,`dj, P / S Cj nu se poate spune, n prezent, dac este uoar sau dificil.

 

5.3 Ordonanarea n flux pe dou maini

 

Ordonanarea n flux (Flow shop) este o problem grea cu foarte puine excepii. Una dintre aceste excepii este ordonanarea pe dou maini. Problema este urmtoarea:

 

Un numr de repere 1,2,...,n sunt prelucrate fiecare nti pe utilajul U1 i apoi pe utilajul U2. Se cunosc duratele operaiilor pe fiecare din cele dou utilaje. Se cere determinarea ordinii de lansare n execuie astfel nct durata realizrii tuturor reperelor s fie minim.

Pentru rezolvarea problemei se utilizeaz urmtorul algoritm, datorat lui Johnston.

 

Pasul 1. Se determin minimul duratelor tuturor operaiilor.

      dac acest minim reprezint durate unei operaii efectuate pe utilajul U1 atunci reperul corespunztor se programeaz la nceput, bineneles dup reperele anterior programate "la nceput";

      dac minimul reprezint durata unei operaii efectuate pe utilajul U2 reperul corespunztor se programeaz la sfrit, dar naintea celor deja programate "la sfrit";

 

Pasul 2. Se elimin din list reperul programat i se reia pasul 1.

 

Observaie In cazul n care minimul calculat n pasul 1 nu este unic, putem avea trei situaii:

 

      minimul este egal cu durata unei operaii pe primul utilaj dar i cu durata unei operaii pe al doilea utilaj. Reperul corespunztor operaiei de pe primul utilaj se programeaz la nceput iar reperul corespunztor celeilalte operaii, la sfrit.

      minimul este egal cu duratele a dou operaii de pe primul utilaj. Se va plasa mai n fa reperul a crui operaie pe al doilea utilaj dureaz mai puin.

      minimul este egal cu duratele a dou operaii pe al doilea utilaj. Se va plasa mai la sfrit reperul a crui operaie pe primul utilaj dureaz mai puin.

 

Exemplul 5.2.4 Aplicnd algoritmul descris problemei cu datele din tabelul 5.6

 

Reper j

1

2

3

4

5

6

Durata operaiei pe utilajul U1

 

4

 

8

 

3

 

6

 

7

 

5

Durata operaiei pe utilajul U2

 

6

 

3

 

7

 

2

 

8

 

4

 

Tabelul 5.6

se obine urmtorul program optim de lansare: 3 1 5 6 2 4. Programarea n timp a execuiei rezult din diagrama:

 

 

Utilaj U1

R3

R1

R5

R6

R2

R4

 

 

Utilaj U2

 

R3

R1

R5

R6

R2

 

R4

 

Termenele de ncepere ale diferitelor operaii

0

3

7

10

14

16

19

24

27

28

31

33

 

Figura 5.1

 

Timpul total de prelucrare al tuturor reperelor este de 35 de uniti de timp.

 

Problema general de ordonanare Job shop este de departe cea mai complicat. Un numr de repere 1,2,...,m se prelucreaz pe n utilaje 1,2,...,n fiecare reper parcurgnd utilajele ntr-o anumit ordine dictat de tehnologia de fabricaie. Se presupun cunoscute duratele operaiilor. Reamintim c un utilaj nu poate procesa la un moment dat dect un singur reper. Nu exist restricii privind ordinea n care se execut operaiile de prelucrare ale diferitelor repere pe un acelai utilaj. Cum trebuiesc lansate reperele pentru ca timpul total de prelucrare s fie minim?

 

Spaiul limitat nu ne ngduie s zbovim asupra acestei probleme care ea singur poate constitui subiectul unei cri de sine stttoare!

 

 

6. Problema stabilirii traseelor de transport

 

ntr-o form simplificat, problema stabilirii traseelor de transport ( pe scurt problema STT) se enun astfel:

 

O firm urmeaz s livreze un produs mai multor clieni P1 , P2 ,..., Pn n cantitile q1 , q2 ,...,qn. Livrrile se fac de la un depozit al firmei, notat P0 , folosindu-se pentru aceasta un parc de mijloace de transport de diferite capaciti.Fie T1 ,T2 ,...,Tm tipurile acestor vehicule difereniate att prin capacitile lor c1 , c2 ,..., cm ct i prin numrul s1 , s2 ,..., sm de uniti disponibile pentru efectuarea transporturilor.Prin contract, cererea fiecrui client trebuie onorat la un singur transport. Fiecare vehicol inclus n programul de livrri pleac de la depozitul P0 ncrcat sau nu la capacitatea maxim, viziteaz succesiv un numr de clieni i dup ce se golete se ntoarce la depozit pentru o eventual nou ncrcare i trimitere pe teren. n acest context, se pune problema de a stabili traseele de vizitare ale clienilor precum i tipul si numrul de mijloace de transport necesare satisfacerii tuturor cererilor astfel nct distana total parcurs s fie minim.

 

Problema STT este una din cele mai complexe probleme de optimizare combinatorial. Ea este o generalizare a problemei comisvoiajorului; Intr-adevr, dac ar exista un singur mijloc de transport a crui capacitate acoper suma tuturor cererilor clienilor atunci STT se reduce la determinarea ordinii n care clienii sunt vizitai astfel nct distana total parcurs s fie minim (vezi fig. 6.1)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Au fost propuse un numr de metode exacte de rezolvare a problemei STT dar eficacitatea lor - pe probleme reale, de dimensiuni mari - este destul de redus. Mult mai atractive s-au dovedit metodele euristice, capabile s ofere n timp util i cu un efort de calcul rezonabil soluii acceptabile. Un exemplu de metod de rezolvare aproximativ este procedura Clarke - Wright [ ], descris succint n continuare.

 

1) La nceput se consider c fiecare client este aprovizionat direct de la depozit cu un mijloc de transport special detaat s fac acest lucru. (vezi fig. 6.2)

 

 

 

 

 

 

 

 

 

 

 

 

 

2) n continuare se ncearc concatenarea acestor trasee n scopul reducerii distanei totale. S examinm fig 6.3a):

 

 

 

 

 

 

 

 

 


Figura 6.3

 

n care apar dou trasee de lungimiD , D'. n fiecare traseu s-au pus n eviden doi clieni Pi , Pj vecini cu depozitul P0 (relativ la un traseu dat un client se va numi vecin cu P0 dac el este fie primul fie ultimul client vizitat; doi clieni se vor zice vecini dac n traseul dat ei sunt vizitai consecutiv) Concatenarea este ilustrat n fig. 5.3b). Din figur se vede c lungimea traseului rezultat este egal cu:

 

(D - di) + dij + (D' - dj) = D + D' - (di + dj - dij) = D + D' - sij (6.1)

unde:

sij = di + dj - dij

 

dij fiind distana dintre Pi i Pj. Mrimile sij , 1 £ i ¹ j £ n se numesc generic reduceri. Este evident c:

sij ³ 0 i sij = sji

 

Din (6.1) rezult atunci c, prin concatenarea a dou trasee distana total parcurs se micoreaz.

 

3) Revenind la fig 6.3a) fie Q i Q' totalurile cererilor clienilor de pe cele dou trasee. Cum fiecare traseu este deservit de un singur mijloc de transport este clar c pe cele dou trasee sunt fixate dou vehicole ale cror capaciti de transport - eventual diferite - acoper cantitile Q i Q'. Pe traseul din fig. 6.3b) va trebui transportat cantitatea Q + Q' i aceasta de ctre un singur vehicol! n concluzie concatenarea celor dou trasee este admisibil numai dac se dispune de un mijloc de transport a crui capacitate acoper sum Q + Q'.

 

4) Deoarece la un moment dat pot exista mai multe concatenri admisibile, are prioritate aceea care produce cea mai mare reducere a distanei totale de parcurs.

 

5) Procesul se oprete n momentul n care nu mai exist concatenri admisibile.

 

 

 

 

 

 

 

 

 

 

 

 


 

Exemplu 6.1 Se consider reeaua din fig. 6.4. Cantitile comandate qi , distanele di de la depozitul P0 la clienii Pi distanele dij dintre clieni i reducerile sij = di + dj - dij sunt indicate n tabelul 6.1. Firma are disponibile numai vehicole cu capacitatea de 6000 uniti.

 

Client

Pi

Cerere

qi

Distana

di:P0 - Pi

Trasee

Cant. circulat

pe un traseu

P1

P2

P3

P4

P5

P6

P7

P1

1100

316

1

1100

*

316

224

247

608

88

640

1

539

0

632

50

849

P2

1300

224

2

1300

 

*

363

400

212

424

48

400

40

500

167

640

P3

1200

539

3

1200

 

 

*

635

316

197

566

215

640

622

500

P4

1200

412

4

1200

 

 

 

*

320

316

367

361

771

224

P5

1900

224

5