Extras din referat
Mai puţin formal, un proces de planificare a sarcinilor pe maşini (sau proces de
ordonanţare pe maşini) constă în determinarea ordinii optime în care sarcinile dintr-o
coadă1 trebuie introduse în lucru pe resursele limitate ca număr şi timp alocat ale sistemului,
numite maşini. Sarcinile sunt formate din operaţii, pentru fiecare sarcină se cunoaşte
itinerariul operaţiilor şi duratele de procesare ale acestora pe maşini şi eventual se impune o
ordine de execuţie pentru operaţiile sarcinilor. Se caută un program de execuţie a sarcinilor
cu durată minimă, în condiţiile respectării restricţiilor cumulative ale problemei. Este
important de subliniat că numărul de sarcini şi de maşini se consideră finit.
Planificarea sarcinilor pe maşini include:
a. ordonanţarea producţiei (shop scheduling);
b. planificarea în cadrul proiectelor (project scheduling);
c. planificarea task-urilor în sistemele de operare multiprocesor etc.
Terminologie selectivă
‐ acţiune (sarcină2): ansamblu de operaţii care se desfăşoară pentru finalizarea
unui realizarea unui sortiment de produs finit;
‐ resursă (maşină): orice element, disponibil sau indisponibil la un moment dat,
care poarte servi la derularea unei operaţii de un anumit tip;
‐ operaţie: o sarcină elementară care se execută unitar pe o resursă;
‐ durată de procesare a unei operaţii pe o resursă;
‐ instalaţie de producţie (sau atelier de fabricaţie3): schema amplasării resurselor
şi a itinerariilor acţiunilor pe resurse;
‐ program (operativ)4: o ordine de execuţie a operaţiilor de planificat, la care se
asociază momente de start procesare. Soluţiile problemelor de ordonanţare sunt
programe operative.
1 un plan de producţie, o coadă înregistrată de un sistem de operare etc.
2 engl. job
3 engl. shop floor sau shop
4 engl. schedule
Modulul 3. Scheduling, partea 1 2
Clasificarea proceselor de ordonanţare
Dimensiunile de definire a proceselor de ordonanţare a producţiei sunt multiple, între
acestea semnificative fiind următoarele (Kaufmann, 1975; Pinedo, 2008):
- complexitatea procesului;
- generarea cerinţelor;
- variabilitatea parametrilor;
- dinamica parametrilor;
- criteriile de optimizare.
Complexitatea procesului este determinată de numărul de maşini, de numărul de
operaţii ale acţiunilor, de omogenitatea structurii acţiunilor şi de variabilele
suplimentare. Conform acestor multiple criterii, clasele de probleme de ordonanţare a
producţiei sunt următoarele:
‐ ordonanţare pe o singură maşină/procesor;
‐ ordonanţare pe maşini/procesoare identice, în paralel;
‐ ordonanţare pe maşini/procesoare diferite cu aceeaşi viteză de procesare, în paralel;
‐ ordonanţare pe maşini/procesoare diferite cu viteze diferite de procesare, în paralel;
‐ ordonanţare cu o operaţie pe acţiune (etapă unică);
‐ ordonanţare cu mai multe operaţii pe acţiune (multietape);
‐ ordonanţare cu acţiuni similare, cu rute identice pe resurse;
‐ ordonanţare cu acţiuni eterogene, cu sau fără rute alternative pentru aceeaşi operaţie;
‐ ordonanţare cu termene limită prevăzute pentru finalizarea acţiunilor;
‐ ordonanţare cu momente de lansare pentru acţiuni;
‐ ordonanţare cu durate de procesare dependente de resurse;
‐ ordonanţare cu costuri de întârziere, cu costuri de neutilizare a resurselor etc.
După modul de generare a cerinţelor, există:
‐ ordonanţare în instalaţie deschisă (tip open shop), unde nu apare stocat nici un
“inventar”;
‐ ordonanţare în instalaţie închisă (tip closed shop), unde comenzile sunt realizate
dintr-un “inventar” existent.
După variabilitatea parametrilor, există:
‐ ordonanţare deterministă;
‐ ordonanţare stocastică;
Dacă gradul de incertitudine al parametrilor este insignifiant, adică incertitudinea
cantităţilor este cu câteva ordine de mărime mai redusă decât cantităţile procesul se poate
numi determinist5, altfel procesul se consideră stocastic.
Bibliografie
1. J. Blazewicz, K. Ecker, E. Pesch, G. Schmidt, J. Weglarz, Handbook of scheduling,
from theory to applications, in International handbooks on Information Systems,
Springer-Verlag Berlin Heidelberg 2007, Series Editors Peter Bernus, Jacek
Blazewicz, Gunter Schmidt, Michael Shaw
2. Pinedo, M.L. (2008). Scheduling. Theory, Algorithms, and Systems, 3rd ed.,
Springer Science-Business Media, LLC, New York.
3. Brucker, P. (2006). Scheduling agorithms, fifth ed., Springer-Verlag, Berlin
Heidelberg.
4. Richard W. Conway, William L. Maxwell, Louis W. Miller, Theory of scheduling,
Addison-Wesley Publishing Company, 1967.
5. Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A.,
Protasi, M. (2004). A compendium of NP optimization problems, în P. Crescenzi şi
Modulul 3. Scheduling, partea 1 16
V. Kann (editors), Complexity and approximation combinatorial optimization
problems and their approximability properties, Springer Verlag,
http://www.nada.kth.se/~viggo/wwwcompendium/wwwcompendium.html
secţiunea Sequencing and Scheduling:
http://www.nada.kth.se/~viggo/wwwcompendium/node173.html
6. J.D. Landa Silva, E.K. Burke, S. Petrovic, An Introduction to Multiobjective
Metaheuristics for Scheduling and Timetabling, in MetaHeuristics for
Multiobjective Optimisation (eds. X. Gandibleux,M. Sevaux, K. Sorensen and V.
T’Kindt), Lecture Notes in Economics and Mathematical Systems, Vol. 535, pp.
91-129, Springer, 2004
7. Kaufmann, M. (1975). Metode şi modele ale cercetării operaţionale (matematica
întreprinderilor), vol. II, Ed. Ştiinţifică şi Enciclopedică, Bucureşti
8. Nicoară, E.S., Contribuţii privind utilizarea algoritmilor genetici la conducerea
ordonanţării flexibile multiobiectiv a producţiei multisortimentale, teză de doctorat,
Universitatea Petrol-Gaze din Ploieşti, iunie 2011.
9. Jain, A.S., Meeran, S. (1998a). Deterministic job shop scheduling: past, present
and future, European Journal of Operational Research, 113(2).
10. Jain, A.S., Meeran, S. (1999). A State-of-the-Art Review of Job-Shop Scheduling
Techniques, European Journal of Operations Research 113, 390-434.
Preview document
Conținut arhivă zip
- M1 - Introducere.pdf
- M2 - Timetabling v2.pdf
- M3 - Scheduling 1.pdf
- M3 - Scheduling 2.pdf
- M3 - Scheduling 3.pdf
- M3 - Scheduling 4.pdf
- M3 - Scheduling 5.pdf