Notare pentru probleme de programare

Probleme de programare în procesul de producție, ciclul de optimizare a fabricii.

Problemele de programare în forma lor cea mai simplă constau dintr-un anumit număr de loturi care trebuie efectuate prin intermediul unui număr dat de mașini, fiecare lot prezintă o serie de operații care trebuie efectuate de către diferitele mașini într-o secvență specifică: problema este de a stabili un program admisibil care durează timpul total minim.

Următoarele descriu schema de clasificare introdusă în publicație de Graham, Lawler, Lenstra și Rinnooy Kan Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey ^[1] din 1979 pentru identificarea tipurilor de probleme de programare. Schema de clasificare utilizează trei câmpuri $\alpha |\beta |\gamma$ ${\ displaystyle \ alpha | \ beta | \ gamma}$ ${\ displaystyle \ alpha | \ beta | \ gamma}$ care reflectă în ordine caracteristicile mașinilor, ale operațiunilor și specifică în cele din urmă criteriul de performanță (funcția obiectivă) adoptat pentru evaluarea programului.

Pentru n loturi atribuite $L_{1},L_{2},\ldots ,L_{n}$ ${\ displaystyle L_ {1}, L_ {2}, \ ldots, L_ {n}}$ ${\ displaystyle L_ {1}, L_ {2}, \ ldots, L_ {n}}$ să fie prelucrate prin intermediul a m mașini $M_{1},M_{2},\ldots ,M_{m}$ ${\ displaystyle M_ {1}, M_ {2}, \ ldots, M_ {m}}$ ${\ displaystyle M_ {1}, M_ {2}, \ ldots, M_ {m}}$ se adoptă următoarele ipoteze:

fiecare mașină poate funcționa doar un singur lot la un moment dat
fiecare lot poate fi procesat de o singură mașină la un moment dat

Mai mult, se crede că timpii de procesare și toți ceilalți parametri sunt cunoscuți și fixați: prin urmare, problemele de planificare examinate vor fi implicit de tip determinist spre deosebire de problemele stochastice în care timpii de procesare și ceilalți parametri sunt incerti și aleatori.

Mediul mașinii

Primul câmp $\alpha =\alpha _{1}\alpha _{2}$ ${\ displaystyle \ alpha = \ alpha _ {1} \ alpha _ {2}}$ ${\ displaystyle \ alpha = \ alpha _ {1} \ alpha _ {2}}$ specifică mediul mașinii.

Parametrul $\alpha _{1}{\mathcal {2}}\left\{\emptyset ,P,Q,R,O,F,J\right\}$ ${\ displaystyle \ alpha _ {1} {\ mathcal {2}} \ left \ {\ emptyset, P, Q, R, O, F, J \ right \}}$ ${\ displaystyle \ alpha _ {1} {\ mathcal {2}} \ left \ {\ emptyset, P, Q, R, O, F, J \ right \}}$ caracterizează tipul de mașină folosită:

$\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$	= $\emptyset$ ${\ displaystyle \ emptyset}$ $\ emptyset$	o singură mașină
$\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$	= P	mașini identice
$\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$	= Î	mașini uniforme
$\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$	= R	mașini necorelate
$\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$	= O	mașini dedicate - sistem de magazin deschis
$\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$	= F	sistem dedicat magazinului de fluxuri de mașini
$\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$	= J	sistem dedicat de mașini-magazin

Parametrul $\alpha _{2}{\mathcal {2}}\left\{\emptyset ,m\right\}$ ${\ displaystyle \ alpha _ {2} {\ mathcal {2}} \ left \ {\ emptyset, m \ right \}}$ ${\ displaystyle \ alpha _ {2} {\ mathcal {2}} \ left \ {\ emptyset, m \ right \}}$ caracterizează numărul de mașini din problemă:

$\alpha _{2}$ ${\ displaystyle \ alpha _ {2}}$ $\ alfa _ {2}$	= $\emptyset$ ${\ displaystyle \ emptyset}$ $\ emptyset$	numărul de mașini este variabil și face parte din intrările problemei
$\alpha _{2}$ ${\ displaystyle \ alpha _ {2}}$ $\ alfa _ {2}$	= m	numărul de mașini este constant și egal cu un întreg pozitiv m

Rețineți că $\alpha _{1}=\emptyset$ ${\ displaystyle \ alpha _ {1} = \ emptyset}$ ${\ displaystyle \ alpha _ {1} = \ emptyset}$ dacă și numai dacă $\alpha _{2}=1$ ${\ displaystyle \ alpha _ {2} = 1}$ ${\ displaystyle \ alpha _ {2} = 1}$

Caracteristic loturilor

Al doilea câmp $\beta =\beta _{1},\beta _{2},\beta _{3},\beta _{4},\beta _{5},\beta _{6},\beta _{7},\beta _{8}$ ${\ displaystyle \ beta = \ beta _ {1}, \ beta _ {2}, \ beta _ {3}, \ beta _ {4}, \ beta _ {5}, \ beta _ {6}, \ beta _ {7}, \ beta _ {8}}$ ${\ displaystyle \ beta = \ beta _ {1}, \ beta _ {2}, \ beta _ {3}, \ beta _ {4}, \ beta _ {5}, \ beta _ {6}, \ beta _ {7}, \ beta _ {8}}$ descrie o serie de caracteristici ale lotului definite ca mai jos. Parametrul $\beta _{1}{\mathcal {2}}\left\{\emptyset ,pmtn\right\}$ ${\ displaystyle \ beta _ {1} {\ mathcal {2}} \ left \ {\ emptyset, pmtn \ right \}}$ ${\ displaystyle \ beta _ {1} {\ mathcal {2}} \ left \ {\ emptyset, pmtn \ right \}}$ indică posibilitatea de preempțiune care este de a întrerupe în mod arbitrar prelucrarea oricărui lot și de a o relua ulterior chiar și pe o altă mașină (împărțirea lucrărilor).

$\beta _{1}$ ${\ displaystyle \ beta _ {1}}$ $\ beta_1$	= $\emptyset$ ${\ displaystyle \ emptyset}$ $\ emptyset$	preempțiunea nu este permisă
$\beta _{1}$ ${\ displaystyle \ beta _ {1}}$ $\ beta_1$	= pmtn	prevederile sunt permise

Parametrul $\beta _{2}{\mathcal {2}}\left\{\emptyset ,res\right\}$ ${\ displaystyle \ beta _ {2} {\ mathcal {2}} \ left \ {\ emptyset, res \ right \}}$ ${\ displaystyle \ beta _ {2} {\ mathcal {2}} \ left \ {\ emptyset, res \ right \}}$ indică prezența resurselor limitate.

$\beta _{2}$ ${\ displaystyle \ beta _ {2}}$ $\ beta _ {2}$	= $\emptyset$ ${\ displaystyle \ emptyset}$ $\ emptyset$	nu este specificată nicio constrângere asupra resurselor
$\beta _{2}$ ${\ displaystyle \ beta _ {2}}$ $\ beta _ {2}$	= rez	sunt specificate constrângerile de resurse

Parametrul $\beta _{3}{\mathcal {2}}\left\{\emptyset ,prec,uan,tree,chains\right\}$ ${\ displaystyle \ beta _ {3} {\ mathcal {2}} \ left \ {\ emptyset, prec, uan, tree, chain \ right \}}$ ${\ displaystyle \ beta _ {3} {\ mathcal {2}} \ left \ {\ emptyset, prec, uan, tree, chain \ right \}}$ indică prezența constrângerilor prioritare între loturi.

Parametrul $\beta _{4}{\mathcal {2}}\left\{\emptyset ,r_{j}\right\}$ ${\ displaystyle \ beta _ {4} {\ mathcal {2}} \ left \ {\ emptyset, r_ {j} \ right \}}$ ${\ displaystyle \ beta _ {4} {\ mathcal {2}} \ left \ {\ emptyset, r_ {j} \ right \}}$ indică timpul pregătit, în timpul pregătirii jargonului, adică indică timpul în care un lot este disponibil pentru a fi procesat de o anumită mașină.

$\beta _{4}$ ${\ displaystyle \ beta _ {4}}$ ${\ displaystyle \ beta _ {4}}$	= $\emptyset$ ${\ displaystyle \ emptyset}$ $\ emptyset$	se presupune că toate orele de pregătire sunt nule, adică toate loturile sunt disponibile pentru procesare în același timp
$\beta _{4}$ ${\ displaystyle \ beta _ {4}}$ ${\ displaystyle \ beta _ {4}}$	= $r_{j}$ ${\ displaystyle r_ {j}}$ ${\ displaystyle r_ {j}}$	sunt specificate timpii gata, timpi care pot diferi de la lot la lot j = 1, ..., n

Parametrul $\beta _{5}{\mathcal {2}}\left\{\emptyset ,p_{ij}=p,minp\leq p_{ij}\leq maxp\right\}$ ${\ displaystyle \ beta _ {5} {\ mathcal {2}} \ left \ {\ emptyset, p_ {ij} = p, minp \ leq p_ {ij} \ leq maxp \ right \}}$ ${\ displaystyle \ beta _ {5} {\ mathcal {2}} \ left \ {\ emptyset, p_ {ij} = p, minp \ leq p_ {ij} \ leq maxp \ right \}}$ descrie timpul pentru prelucrarea i pe a j-a, $p_{ij}$ ${\ displaystyle p_ {ij}}$ $p _ {{ij}}$ .

$\beta _{5}$ ${\ displaystyle \ beta _ {5}}$ ${\ displaystyle \ beta _ {5}}$	= $\emptyset$ ${\ displaystyle \ emptyset}$ $\ emptyset$	loturile au timpi de procesare arbitrari
$\beta _{5}$ ${\ displaystyle \ beta _ {5}}$ ${\ displaystyle \ beta _ {5}}$	= $p_{ij}=p$ ${\ displaystyle p_ {ij} = p}$ ${\ displaystyle p_ {ij} = p}$	toate loturile au același timp de procesare egal cu ap
$\beta _{5}$ ${\ displaystyle \ beta _ {5}}$ ${\ displaystyle \ beta _ {5}}$	= $minp\leq p_{ij}\leq maxp$ ${\ displaystyle minp \ leq p_ {ij} \ leq maxp}$ ${\ displaystyle minp \ leq p_ {ij} \ leq maxp}$	fără timp de procesare $p_{ij}$ ${\ displaystyle p_ {ij}}$ $p _ {{ij}}$ este mai mic decât min sau mai mare decât max p

In caz $\alpha _{1}{\mathcal {2}}\left\{P,Q\right\}$ ${\ displaystyle \ alpha _ {1} {\ mathcal {2}} \ left \ {P, Q \ right \}}$ ${\ displaystyle \ alpha _ {1} {\ mathcal {2}} \ left \ {P, Q \ right \}}$ parametrul $p_{ij}$ ${\ displaystyle p_ {ij}}$ $p _ {{ij}}$ se înlocuiește cu notația $p_{i}$ ${\ displaystyle p_ {i}}$ $p_ {i}$

Parametrul $\beta _{6}{\mathcal {2}}\left\{\emptyset ,{\tilde {d}}\right\}$ ${\ displaystyle \ beta _ {6} {\ mathcal {2}} \ left \ {\ emptyset, {\ tilde {d}} \ right \}}$ ${\ displaystyle \ beta _ {6} {\ mathcal {2}} \ left \ {\ emptyset, {\ tilde {d}} \ right \}}$ indică prezența termenelor.

$\beta _{6}$ ${\ displaystyle \ beta _ {6}}$ ${\ displaystyle \ beta _ {6}}$	= $\emptyset$ ${\ displaystyle \ emptyset}$ $\ emptyset$	nu există termene în sistem
$\beta _{6}$ ${\ displaystyle \ beta _ {6}}$ ${\ displaystyle \ beta _ {6}}$	= ${\tilde {d}}$ ${\ displaystyle {\ tilde {d}}}$ ${\ displaystyle {\ tilde {d}}}$	termenele sunt impuse la finalizarea operațiunilor

În cazul sistemelor de locuri de muncă, parametrul $\beta _{7}{\mathcal {2}}\left\{\emptyset ,n_{j}\leq k\right\}$ ${\ displaystyle \ beta _ {7} {\ mathcal {2}} \ left \ {\ emptyset, n_ {j} \ leq k \ right \}}$ ${\ displaystyle \ beta _ {7} {\ mathcal {2}} \ left \ {\ emptyset, n_ {j} \ leq k \ right \}}$ indică numărul maxim de procese care alcătuiesc foarte mult.

$\beta _{7}$ ${\ displaystyle \ beta _ {7}}$ ${\ displaystyle \ beta _ {7}}$	= $\emptyset$ ${\ displaystyle \ emptyset}$ $\ emptyset$	numărul de procese pentru fiecare lot este arbitrar sau sistemul nu este de tipul magazinului
$\beta _{7}$ ${\ displaystyle \ beta _ {7}}$ ${\ displaystyle \ beta _ {7}}$	= $n_{j}\leq k$ ${\ displaystyle n_ {j} \ leq k}$ ${\ displaystyle n_ {j} \ leq k}$	numărul de procese pentru fiecare lot nu depășește k

În cazul sistemelor dedicate, parametrul $\beta _{8}{\mathcal {2}}\left\{\emptyset ,no-wait\right\}$ ${\ displaystyle \ beta _ {8} {\ mathcal {2}} \ left \ {\ emptyset, no-wait \ right \}}$ ${\ displaystyle \ beta _ {8} {\ mathcal {2}} \ left \ {\ emptyset, no-wait \ right \}}$ indică prezența spațiilor de stocare intermediare între mașini, „tampoane”, potrivite pentru găzduirea loturilor în așteptarea începerii următoarei prelucrări.

$\beta _{8}$ ${\ displaystyle \ beta _ {8}}$ ${\ displaystyle \ beta _ {8}}$	= $\emptyset$ ${\ displaystyle \ emptyset}$ $\ emptyset$	există un buffer cu capacitate nelimitată
$\beta _{8}$ ${\ displaystyle \ beta _ {8}}$ ${\ displaystyle \ beta _ {8}}$	= nu așteptați	nu există tampoane între mașini și un lot care a terminat o procesare trebuie să înceapă în mod necesar procesarea imediat pe următoarea mașină

Criteriul de performanță

Al treilea câmp $\gamma$ ${\ displaystyle \ gamma}$ $\gamă$ denotă criteriul de performanță adoptat.

Notă

^ RL Graham, EL Lawler, JK Lenstra, AHG Rinnooy Kan, Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey : Ann. Matematică discretă. 5, 1979, p.287-326

Bibliografie

Blazewicz, JK Lenstra, AHG Rinnooy Kan, Programare sub rezerva constrângerilor de resurse: clasificare și complexitate: Ann. Matematică discretă. 5, 1983, p. 11-24
Blazewicz, K. Ecker, E. Pesch, G. Schmidt, J. Weglarz, Handbook on Scheduling - From Theory to Applications (International Handbooks on Information Systems): Springer-Verlag Berlin Heidelberg, 2007

[1] RL Graham, EL Lawler, JK Lenstra, AHG Rinnooy Kan, Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey : Ann. Matematică discretă. 5, 1979, p.287-326

[1]