Cel mai scurt timp de procesare

Aceasta este teorema cunoscută ca cel mai scurt timp de procesare ^[1] elaborată în teoria planificării care afirmă că timpul mediu de curgere , ${\bar {F}}\$ ${\ displaystyle {\ bar {F}} \}$ ${\ displaystyle {\ bar {F}} \}$ , este minimizat prin secvențierea loturilor în ordinea nedescrescă a timpilor de procesare $p_{[1]}\leq \ p_{[2]}\leq \$ ${\ displaystyle p _ {[1]} \ leq \ p _ {[2]} \ leq \}$ ${\ displaystyle p _ {[1]} \ leq \ p _ {[2]} \ leq \}$ $...\leq \ p_{[n]}$ ${\ displaystyle ... \ leq \ p _ {[n]}}$ ${\ displaystyle ... \ leq \ p _ {[n]}}$ .

Având în vedere n loturi care urmează să fie procesate în cadrul sistemului de producție constând dintr-o singură mașină , pentru o secvență particulară atribuită a acestor n loturi avem timpul mediu de curgere : ${\bar {F}}\ ={\frac {1}{n}}\sum _{i=1}^{n}F_{i}=C_{k}={\frac {1}{n}}\sum _{i=1}^{n}\left(A_{k}+p_{k}\right)={\frac {1}{n}}\sum _{i=1}^{n}A_{k}+{\frac {1}{n}}\sum _{i=1}^{n}p_{k}$ ${\ displaystyle {\ bar {F}} \ = {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} F_ {i} = C_ {k} = {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} \ left (A_ {k} + p_ {k} \ right) = {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} A_ {k} + {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} p_ {k}}$ ${\ displaystyle {\ bar {F}} \ = {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} F_ {i} = C_ {k} = {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} \ left (A_ {k} + p_ {k} \ right) = {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} A_ {k} + {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} p_ {k}}$

Observând că $\sum _{i=1}^{n}p_{k}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} p_ {k}}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} p_ {k}}$ este constantă pentru orice ordonare a secvenței adoptate, se deduce că pentru a minimiza ${\bar {F}}\$ ${\ displaystyle {\ bar {F}} \}$ ${\ displaystyle {\ bar {F}} \}$ este necesar să se minimizeze $\sum _{i=1}^{n}A_{k}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} A_ {k}}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} A_ {k}}$ . Este clar că dacă alegeți o astfel de secvență de redat $A_{k}$ ${\ displaystyle A_ {k}}$ $A _ {{k}}$ cea mai mică valoare posibilă, atunci suma lor va fi, de asemenea, minimizată.

În cele ce urmează pentru a indica poziția atribuită unui lot k-lea generic $L_{k}$ ${\ displaystyle L_ {k}}$ ${\ displaystyle L_ {k}}$ într-o secvență ordonată de loturi, se adoptă următoarea convenție de scriere: parantezele pătrate vor fi folosite pentru a indica poziția aleasă în secvență. De exemplu, simbolul [7] = 5 înseamnă că lotul numărul 5 este atribuit poziției 7 din secvență; precum și $p_{[k]}$ ${\ displaystyle p _ {[k]}}$ ${\ displaystyle p _ {[k]}}$ va indica timpul de procesare al lotului care ocupă poziția a k-a în secvență.

Din moment ce pentru primul lot $L_{[1]}$ ${\ displaystyle L _ {[1]}}$ ${\ displaystyle L _ {[1]}}$ începe imediat, puteți întreba $A_{[1]}=0$ ${\ displaystyle A _ {[1]} = 0}$ ${\ displaystyle A _ {[1]} = 0}$ .

De la lotul din a doua poziție a secvenței $L_{[2]}$ ${\ displaystyle L _ {[2]}}$ ${\ displaystyle L _ {[2]}}$ va trebui să aștepte procesarea lotului care îl precedă, da $A_{[2]}=p_{[1]}$ ${\ displaystyle A _ {[2]} = p _ {[1]}}$ ${\ displaystyle A _ {[2]} = p _ {[1]}}$ . Dacă lotul cu cel mai scurt timp de procesare este ales ca lot în poziția [1], atunci acesta va fi minimizat $A_{[2]}$ ${\ displaystyle A _ {[2]}}$ ${\ displaystyle A _ {[2]}}$ .

În poziția [3] avem $A_{[3]}=p_{[1]}+p_{[2]}$ ${\ displaystyle A _ {[3]} = p _ {[1]} + p _ {[2]}}$ ${\ displaystyle A _ {[3]} = p _ {[1]} + p _ {[2]}}$ , acesta este al treilea lot $L_{[3]}$ ${\ displaystyle L _ {[3]}}$ ${\ displaystyle L _ {[3]}}$ va trebui să aștepte asta $L_{[1]}$ ${\ displaystyle L _ {[1]}}$ ${\ displaystyle L _ {[1]}}$ Și $L_{[2]}$ ${\ displaystyle L _ {[2]}}$ ${\ displaystyle L _ {[2]}}$ sunt procesate. Pentru a minimiza $A_{[3]}$ ${\ displaystyle A _ {[3]}}$ ${\ displaystyle A _ {[3]}}$ vor fi alese loturile cu cel mai scurt timp de procesare: prin urmare, lotul ales în pasul anterior este optim, în timp ce ca al doilea lot, va fi ales cel cu cel mai scurt timp de procesare dintre celelalte.

Procedând în acest mod, se construiește o secvență de loturi în care lotul care urmează să fie procesat în poziția [i] are cel mai scurt timp de procesare dintre cele care mai sunt încă de procesat. Ca rezultat, secvența aleasă SPT - Timpul de procesare cel mai scurt se minimizează ${\bar {F}}\$ ${\ displaystyle {\ bar {F}} \}$ ${\ displaystyle {\ bar {F}} \}$ .

Notă

^ Simon French, Sequencing and scheduling: an introduction to the Mathematics of the Job-Shop, Marea Britanie: Ellis Horwood Limited, 1987, p.37 , ISBN 0-85312-299-7

Bibliografie

Simon French, Secvențierea și programarea: o introducere în matematica magazinului de locuri de muncă , Marea Britanie: Ellis Horwood Limited, 1987

[1] Simon French, Sequencing and scheduling: an introduction to the Mathematics of the Job-Shop, Marea Britanie: Ellis Horwood Limited, 1987, p.37 , ISBN 0-85312-299-7

[1]