Programare calendaristică

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.