Regula lui Johnson

Regula lui Johnson este o metodă care face parte din programarea operațiunilor care este utilizată atunci când trebuie efectuate lucrări diferite pe aceleași mașini într-o succesiune precisă. Pentru a găsi ordinea optimă în care să efectuați aceste procese, este necesar să cunoașteți timpul exact pe care fiecare proces îl va lua pe fiecare mașină.

Exemplu de aplicație

Să vedem cum regula lui Johnson ne permite să rezolvăm o problemă simplă de programare. Avem un set de patru procese pe care le numim A, B, C și D, care necesită ambele mașini „MacchinaUno” și „MacchinaDue” ; pentru fiecare proces știm durata exactă.

	Machine One	Mașina Două
LA	2 minute	1 minut
B.	6 minute	8 minute
C.	4 minute	5 minute
D.	5 minute	7 minute

Să considerăm acum minim timpul referitoare la activitatea depusă pe „MacchinaUno“, adică „A“ , care durează 2 minute . Comparând prelucrarea timpului pe „MacchinaUno“ și „MacchinaDue“ vedem că $2minuti>1minuto$ ${\ displaystyle 2 minute> 1 minut}$ ${\ displaystyle 2 minute> 1 minut}$ asa de:

T_{MacchinaUno}>T_{MacchinaDue}

{\ displaystyle T_ {MachineOne}> T_ {MachineDue}}

{\ displaystyle T_ {MachineOne}> T_ {MachineDue}}

prin urmare prelucrarea A va fi ultima care va fi efectuată.

Să actualizăm tabelul referitor la soluția optimă:

	Prelucrare
1
2
3
4	LA

Să trecem acum la pasul următor luând în considerare prelucrarea (dintre cele încă „libere”) cu un timp „MacchinaUno” mai scurt , adică prelucrarea C. Observăm imediat că $4minuti<5minuti$ ${\ displaystyle 4minutes <5minutes}$ ${\ displaystyle 4minutes <5minutes}$ asa de:

T_{MacchinaUno}<T_{MacchinaDue}

{\ displaystyle T_ {MacchinaUno} <T_ {MacchinaDue}}

{\ displaystyle T_ {MacchinaUno} <T_ {MacchinaDue}}

prin urmare prelucrarea C va fi prima care va fi efectuată.

.

Să actualizăm tabelul referitor la soluția optimă:

	Prelucrare
1	C.
2
3
4	LA

Mai departe, luăm în considerare mai întâi prelucrarea D unde $5minuti<7minuti$ ${\ displaystyle 5minutes <7minutes}$ ${\ displaystyle 5minutes <7minutes}$ care este procesat al doilea (fiind primul loc deja ocupat) și, în cele din urmă, prelucrarea B care este procesată al treilea (fiind primele două locuri deja ocupate) întotdeauna conform celor două reguli de mai sus, de fapt $6minuti<8minuti$ ${\ displaystyle 6minutes <8minutes}$ ${\ displaystyle 6minutes <8minutes}$ . Prin urmare, secvența de planificare optimă conform regulii lui Johnson pentru acest exemplu este:

	Prelucrare
1	C.
2	D.
3	B.
4	LA

Elemente conexe

Portal de inginerie

Portalul de matematică