1 ¨ Utemez´ esi feladatok Az u ¨temez´esi feladatok vizsg´alata az 50-es ´evek elej´en kezd˝ od¨ ott, majd tekintettel a feladat gyakorlati fontoss´ ag´ ara sok k¨ ul¨ onb¨ oz˝ o modell tanulm´ anyoz´as´ara ker¨ ult sor, ´es a t´emak¨ or nagyon gyors ´es nagy fejl˝od´esen ment ´at. A modellek nagy sz´am´ara jellemz˝o, hogy 1977-ben A. H. G. Rinnooy Kan egy konferencia szekci´oj´anak ¨osszefoglal´ oj´ aban 9000-re becs¨ ulte a katalogiz´alhat´o k¨ ul¨onb¨oz˝o determinisztikus u ¨temez´esi probl´em´ ak sz´am´ at. Az´ota ez a sz´am m´eg sz´amottev˝oen n¨ovekedett. Tekintettel a t´emak¨ or nagys´ag´ ara ´es bonyolults´ag´ara a jelen fejezetben csak v´azoljuk az u ¨temez´esi probl´em´ akat ´es csak n´eh´any egyszer˝ u modellt vizsg´alunk r´eszletesebben.
¨ Utemez´ esi modellek Az u ¨temez´esi probl´em´akban adottak bizonyos p´aronk´ent k¨ ul¨ onb¨ oz˝ o g´epek ´es m sz´am´ u munka, amelyeket az 1, . . . , m sz´ amokkal fogunk sorsz´amozni. A feladat az, hogy u ¨temezz¨ uk az egyes munk´ ak v´egrehajt´as´ at a g´epeken, u ´gy, hogy valamely c´el szerint optim´alis u ¨temez´est kapjunk. A munk´ ak v´egrehajt´ as´ anak u ¨temez´es´en vagy egyszer˝ ubben a munk´ ak u ¨temez´es´en azt ´ertj¨ uk, hogy a j-edik munk´at hozz´arendelj¨ uk valamely g´ephez egy Sj kezd´esi ´es Cj befejez´esi id˝ ovel minden j-re. A munk´ akhoz minden modellben tartozik egy v´egrehajt´ asi id˝ o, amit pj -vel szok´as jel¨olni. Ez azt adja meg, hogy mennyi ideig tart a munk´at elv´egezni. Ennek megfelel˝oen a munk´ ahoz rendelt kezd´esi ´es befejez´esi id˝okre a Cj − Sj = pj felt´etelnek kell teljes¨ ulni. A k¨ ul¨onb¨oz˝o modelleket t¨obbf´ele szempontb´ ol is oszt´alyozhatjuk. A tov´abbiakban a legismertebb v´altozatokat igyeksz¨ unk ¨osszegy˝ ujteni. A munk´ ak meghat´ aroz´ o param´ eterei Mint m´ar eml´ıtett¨ uk minden munk´ ahoz tartozik egy v´egrehajt´asi id˝o, de m´as modellekben egy´eb param´eterei is vannak az egyes munk´ aknak. • A munk´akhoz rendelhet˝o ´erkez´esi id˝ o is, ezt a param´etert a j-edik munk´ara ´altal´aban rj jel¨oli. Ez az id˝o azt az id˝opontot adja meg, amelyt˝ol kezdve a munka v´egrehajt´asa elkezdhet˝ o, teh´at a munk´ ara az Sj ≥ rj felt´etelnek kell teljes¨ ulni. • A j-edik munk´ahoz tartozhat egy dj hat´ arid˝ o. Itt k´et k¨ ul¨ onb¨ oz˝ o t´ıpus´ u modellt vizsg´alhatunk. Az els˝o esetben csak olyan u ¨temez´eseket fogadunk el, amelyekre Cj ≤ dj , azaz amelyek betartj´ak a hat´arid˝ ot, a
2 m´asodikban megszeghetj¨ uk a hat´arid˝ ot, de ekkor a c´elf¨ uggv´enyben a hat´arid˝o is szerepel. • A j-edik munk´ ahoz hozz´arendelhet¨ unk egy wj s´ ulyt vagy egy fj (t) s´ ulyf¨ uggv´enyt, amely azt adja meg mennyire fontos a munka, illetve azt, hogy mennyire fontos a munka t id˝opontra t¨ort´en˝ o befejez´ese. Egy m´asik fontos oszt´alyoz´ asi szempont az, hogy mi az a f¨ uggv´eny, aminek az optimum´at keress¨ uk. Eszerint a szempont szerint is igen sok lehets´eges modell ker¨ ult bevezet´esre, a tov´ abbiakban a legfontosabbakat v´azoljuk. A c´elf¨ uggv´enyek k´et alapvet˝ o oszt´alyra bonthat´ ok: a maximum c´elf¨ uggv´enyekre ´es az ¨osszeg c´elf¨ uggv´enyekre. • Tal´an a legismertebb modellek azok, amelyekben az utols´onak befejezett munka befejez´esi idej´et akarjuk minimaliz´alni, azaz ahol a c´elf¨ uggv´eny min{max{Cj : 1 ≤ j ≤ m}}, amelyet a lehets´eges u ¨temez´esekre minimaliz´alunk. Szint´en gyakran haszn´alt c´elf¨ uggv´eny a befejez´esi ´ id˝ ok ¨ osszegf¨ uggv´enye. Altal´ anosabb esetben, mikor a munk´ aknak van Pm Pm s´ ulya vagy s´ ulyf¨ uggv´enye, akkor a j=1 wj · Cj illetve j=1 fj (Cj ) f¨ uggv´enyeket minimaliz´aljuk. akhoz hat´arid˝ o is tartozik, akkor a c´elf¨ uggv´eny • Amennyiben a munk´ ´altal´aban a k´es´esek minimaliz´al´ asa. Itt k´et ´ert´eket szok´as vizsg´alni. Az els˝o a k´es´esi id˝ o (lateness), amely az Lj = Cj − dj ´ert´ek, a m´asik pedig a cs´ usz´ asi id˝ o (tardiness), amely az Tj = max{0, Lj } ´ert´ek. A k´et maximum c´elf¨ uggv´eny a k´es´esi id˝oknek illetve a cs´ usz´ asi id˝oknek a maximuma. Egy´eb modellekben ezen ´ert´ekek ¨osszeg´et illetve s´ ulyozott ¨osszeg´et igyeksz¨ unk minimaliz´alni. Itt ´erdemes azt a modellt eml´ıten¨ unk, ahol a c´el az elk´esett (Tj > 0) munk´ ak sz´am´ anak minimaliz´al´ asa. • Amennyiben ´erkez´esi id˝ok is vannak szok´as a befejez´esi id˝o helyett a foly´ asi id˝ ot (flow time) vizsg´alni, amely az Fj = Cj − rj ´ert´ek. Ezekben a modellekben a c´elf¨ uggv´eny ezen Fj ´ert´ekek maximuma vagy s´ ulyozott ¨osszege. A fenti alapvet˝o oszt´alyoz´ ason kiv¨ uli egy´eb v´altozatokat, ´altal´ anos´ıt´ asokat kaphatunk n´eh´any extra felt´etellel. Az al´abbiakban ezekb˝ol gy˝ ujt¨ ott¨ unk ¨ossze n´eh´anyat.
3 • Feltehetj¨ uk, hogy bizonyos munk´ akat csak m´as munk´ ak ut´an lehet elv´egezni. Igen sok gyakorlati probl´em´ an´ al el˝ofordulnak ilyen felt´etelek. Ekkor az egyes munk´akhoz tartozik az a felt´etel is, hogy mely munk´ ak el˝ozetes v´egrehajt´as´at k¨ovetelik meg. Ezen extra felt´etelek mellett az ¨osszes, a fentiekben eml´ıtett modell vizsg´alhat´ o. Megeml´ıtj¨ uk, hogy ilyen extra felt´etellel kezelhet˝ o a tekintett p´eld´ aban, hogy a fi´ uk egy adott sorrendben olvass´ak az u ´js´ agokat. unk, hogy minden egyes • Az eddigiek sor´an v´egig azzal a felt´etellel ´elt¨ munk´ahoz pontosan egy v´egrehajt´asi id˝o tartozik ´es ez f¨ uggetlen att´ol, hogy melyik g´epen ker¨ ul a munka v´egrehajt´asra. Ez ´altal´ aban gyakorlati probl´em´akn´al nem ´ıgy van. Egy ´altal´ anosabb modellben minden munk´ahoz egy v´egrehajt´ asi vektor tartozik, amely i-edik komponense megadja, hogy az Mi g´epen mennyi ideig tart a munk´ at v´egrehajtani. Itt ´erdemes k´et speci´alisabb esetre kit´erni. Az egyik esetben a j-edik munka v´egrehajt´asi vektor´anak i-edik komponense pj /vi , ahol vi az Mi g´ep sebess´eg´enek felel meg. A m´asodik esetben a korl´ atozott hozz´arendel´esi esetben a v´egrehajt´asi vektor n´eh´ any komponense v´egtelen a t¨obbi megegyezik, ez azt jelenti, hogy a g´epek azonosak csak a munka n´eh´any g´epen nem hajthat´o v´egre. uk, hogy a munk´ ak v´egre• Egy m´asik ´altal´anos´ıt´as, amelyben megengedj¨ hajt´asa megszak´ıthat´o legyen. Ekkor a j-edik munk´ ahoz nem egy darab legal´abb pj hossz´ u intervallumot kell hozz´arendeln¨ unk valamely g´epen, hanem t¨obb, egym´ast nem ´atfed˝ o intervallumot (ak´ar k¨ ul¨ onb¨ oz˝ o g´epeken), amelyek ¨osszhossza legal´abb pj .
Heurisztikus algoritmusok az alapprobl´ em´ ara Ebben a r´eszben az egyik legegyszer˝ ubb v´altozatot vizsg´aljuk. A modellben n darab azonos M1 , . . . , Mn g´ep¨ unk van , a J1 , . . . , Jm munk´ akhoz pedig csak egyetlen param´eter tartozik, a pj , j = 1, . . . , m v´egrehajt´asi id˝ok. C´el egy olyan u ¨temez´es megkonstru´ al´ asa, amelyre a befejez´esi id˝ok maximuma minim´alis. A probl´ema egy g´ep eset´en trivi´alis b´armely olyan u ¨temez´esre, amelyben a g´ep folyamatosan dolgozik, (nem v´arunk a munk´ ak elv´egz´ese k¨ozben) a max{Cj : 1 ≤ j ≤ m} ´ert´ek megegyezik a v´egrehajt´asi id˝ok ¨osszeg´evel. Tov´abb´a az is nyilv´anval´o, hogy amennyiben minden munk´ at elv´egz¨ unk, akkor nem fejezhetj¨ uk be a munk´ akat ezen id˝opont el˝ott. Ha a g´epek sz´ama t¨obb, mint 1, akkor a feladat l´enyegesen nehezebb. Igazol´ast nyert,
4 hogy n ≥ 2 eset´en a probl´ema NP-neh´ez. M´asr´eszt ebben az esetben egy lehets´eges u ¨temez´est meghat´arozhatunk az´altal, hogy az egyes munk´ akat mely g´epekhez rendelj¨ uk hozz´a. Amennyiben minden g´epre megkapjuk, hogy mi a g´ephez rendelt munk´ aknak a halmaza, akkor minden egyes g´epre, az ott lev˝o munk´akat optim´alisan u ´gy u ¨temezhetj¨ uk, hogy a a g´ep folyamatosan dolgozzon, ´es minden ilyen u ¨temez´esre ugyanannyi lesz a g´epen a maxim´alis befejez´esi id˝o, a munk´ aknak a v´egrehajt´asi idejeinek az ¨osszege. Ezt az ´ert´eket a g´ep t¨ olt´es´enek nevezz¨ uk. A fogalmat haszn´aljuk ´altal´ anosabb ´ertelemben is, g´epek egy halmaz´anak a t¨olt´es´en a g´epekhez rendelt munk´ ak v´egrehajt´asi idejeinek az ¨osszeg´enek ´es a g´epek sz´am´ anak a h´anyados´ at ´ertj¨ uk. Mivel a feladat NP-neh´ez ez´ert erre a feladatoszt´alyra is fontos heurisztikus algoritmusok kidolgoz´asa. Az al´abbiakban k´et egyszer˝ u heurisztikus algoritmussal ismerked¨ unk meg. Az els˝o R. L. Graham-t˝ol sz´armaz´ o algoritmus, amelyet Lista algoritmusnak nevez¨ unk a k¨ovetkez˝ ok´eppen m˝ uk¨ odik.
Lista algoritmus El˝ ok´esz´ıt˝ o r´esz. A J1 munk´ at rendelj¨ uk az M1 g´ephez, tov´ abb´ a legyen r := 1. Iter´ aci´ os r´esz (r-edik iter´aci´ o). Ha r = m, akkor v´ege az elj´ar´ asnak. Ellenkez˝o esetben a Jr+1 munk´ at rendelj¨ uk ahhoz a g´ephez, amely g´epen minim´alis a t¨olt´es. Ha t¨obb ilyen g´ep is van v´alasszuk a legkisebb index˝ ut. Az algoritmus az optim´alishoz k¨ozeli eredm´enyt eredm´enyez, amint azt az al´abbi t´etel mutatja. 11.1 t´ etel. A lista algoritmus approxim´ aci´ os h´ anyadosa 2 − 1/n, ahol n a g´epek sz´ ama. Bizony´ıt´ as. Els˝ok´ent igazoljuk, hogy az algoritmus 2−1/n-approxim´ aci´ os. Legyen σ = {J1 , . . . , Jm } tetsz˝oleges munkasorozat rendre p1 , . . . , pm v´egrehajt´asi id˝okkel. Tekints¨ uk a lista algoritmus ´altal kapott u ¨temez´est. Legyen Jl az a munka, amely legk´es˝ obb fejez˝odik be. Vizsg´aljuk ezen munka Sl kezd´esi idej´et. Mivel egyetlen g´ep sem kezdte el a munk´ at u ¨temezni Sl el˝ott, ez´ert minden g´ep sz¨ unet n´elk¨ ul dolgozott az Sl id˝opontig. Ebb˝ol azt kapjuk, hogy
5
Sl ≤
m m m 1X 1 X 1 X 1 pj = ( pj − pl ) = ( pj ) − pl . n j=1 n j=1 n j=1 n j6=l
K¨ovetkez´esk´epp Lista(σ) = Sl + pl ≤
m 1 X n−1 ( pl . pj ) + n j=1 n
M´asr´eszt az optim´alis u ¨temez´esben is v´egre kell hajtani az ¨osszes munk´ at, 1 Pm ´ıgy OP T (σ) ≥ n ( j=1 pj ). Tov´ abb´ a a pl munk´ at is v´egre kell hajtani valamely g´epen, ´ıgy OP T (σ) ≥ pl . Ezen becsl´esek alapj´an egyb˝ol ad´odik, hogy Lista(σ) ≤ (1 +
n−1 )OP T (σ), n
amivel bizony´ıtottuk, hogy az algoritmus 2 − 1/n-approxim´ aci´ os. Most igazoljuk, hogy a tekintett korl´ at ´eles. Vegy¨ unk n(n − 1) darab munk´at 1/n v´egrehajt´asi id˝ovel, majd egy munk´ at 1 v´egrehajt´asi id˝ovel. Ekkor a lista algoritmus az els˝o n(n−1) munk´ at egyenletesen elosztja a g´epek k¨oz¨ott, majd az utols´o munk´at az M1 g´epen u ¨temezi. Teh´ at a maxim´alis befejez´esi id˝o 1+(n−1)/n lesz. Egy optim´alis u ¨temez´es pedig a r¨ovid munk´ akat egyenletesen osztja sz´et az els˝o n − 1 g´ep k¨oz¨ ott, majd az utols´o munk´ at az n-edik g´ephez rendeli, ´es a maxim´alis befejez´esi ideje 1 lesz. Teh´ at ebben az esetben az algoritmus ´altal kapott megold´as ´es az optim´alis megold´as c´elf¨ uggv´eny´ert´ekeinek h´anyadosa 2 − 1/n, amivel igazoltuk az ´all´ıt´ asunkat. Amint azt l´athattuk a korl´at ´eless´eg´enek igazol´as´ an´ al, a lista algoritmus legnagyobb hib´aja akkor j¨on el˝o, amikor sok r¨ovid munka ut´an egy hossz´ u munk´at kell v´egrehajtani. Ezt a probl´em´ at jobban kezeli a k¨ovetkez˝ o szint´en R. L. Graham-t˝ol sz´armaz´o elj´ar´ as.
LPT Algoritmus • 1. l´ep´es. Rendezz¨ uk sorba a munk´ akat cs¨okken˝ o v´egrehajt´asi id˝o szerint. • 2. l´ep´es. A munk´ak kapott list´aj´ an hajtsuk v´egre a lista algoritmust.
6 Az els˝o rendez´esi f´azis val´ oban jav´ıtja az elj´ar´ as hat´ekonys´ ag´ at, amint azt a k¨ovetkez˝o ´all´ıt´as mutatja. 11.2. t´ etel. Az LPT algoritmus approxim´ aci´ os h´ anyadosa 4/3−1/(3n).
Shop u ¨ temez´ es Shop u ¨temez´esr˝ol besz´el¨ unk abban az esetben, ha a g´epeken minden v´egrehajtand´o munka t¨obb m˝ uveletb˝ ol ´all. Minden egyes m˝ uvelet egy, a m˝ uvelethez rendelt g´epen hajthat´o v´egre, ´es adott a m˝ uvelet v´egrehajt´asi ideje. Ezen oszt´alyon bel¨ ul k´et f˝o csoportot k¨ ul¨ onb¨ oztet¨ unk meg. Amennyiben b´armely munk´ara a hozz´atartoz´ o m˝ uveletek tetsz˝oleges sorrendben v´egrehajthat´ok, akkor open shop u ¨temez´esr˝ ol besz´el¨ unk. Ezt a modellt itt nem t´argyaljuk. A m´asik esetben ism´et megk¨ ul¨ onb¨ oztet¨ unk k´et modellt. Ha a munk´ak m˝ uveleteihez tartoz´o g´epek sorrendje nem azonos akkor job shop u ¨temez´esr˝ ol besz´el¨ unk. (A fi´ uk u ´js´ agolvas´ asi probl´em´ aja ´ıgy egy job shop u ¨temez´esi feladat.) Ha a g´epek sorrendje azonos minden munk´ ara, akkor flow shop u ¨temez´esr˝ ol szok´asos besz´elni. A tov´ abbiakban ezt a probl´emaoszt´alyt vizsg´aljuk. Speci´alisabban olyan probl´em´ akat tekint¨ unk, amelyekben a g´epek sz´ama n ´es minden Ji munka n sz´ am´ u m˝ uveletb˝ ol, az Oi1 , . . . , Oin m˝ uveletekb˝ol ´all, amelyek k¨oz¨ ul a k-adik m˝ uveletetet a k-adik g´epen kell v´egrehajtanunk. ´ Eszrevehetj¨ uk, hogy a fenti flow shop u ¨temez´esi p´elda eset´en a g´epeken a munk´ak v´egrehajt´asa nem azonos sorrendben t¨ort´enik. Amennyiben m´eg az azonos sorrendet is kik¨otj¨ uk, akkor permut´ aci´ os flow shop probl´em´ ar´ ol besz´el¨ unk. Amint az elnevez´es is mutatja ebben az esetben a munk´ aknak kell azt a sorrendj´et meghat´arozni, amely sorrendre az u ¨temez´es optim´alis. A probl´ema ´altal´aban m´eg ennyi kik¨ot´es mellett is NP-neh´ez marad, de ebben az esetben k´et g´epre m´ar ismert hat´ekony elj´ar´ as. A tov´ abbiakban bemutatjuk ezt az elj´ar´ ast ´es igazoljuk annak helyess´eg´et. Jel¨olje a g´epeket M1 ´es M2 a munk´ akat pedig rendre J1 , . . . , Jm . A Ji i = 1, . . . , m munka k´et m˝ uveletb˝ ol ´all, el˝osz¨ or az Oi1 m˝ uveletet kell az M1 g´epen v´egrehajtani, ami τi1 ideig tart, majd az Oi2 m˝ uveletet az M2 g´epen ami τi2 ideig tart.
Johnson algoritmusa uk a nem u ¨temezett • 1. l´ep´es. Legyen k := 1 ´es l := m, ´es tekints¨ munk´ak J = {J1 , . . . , Jm } halmaz´ at.
7 • 2. l´ep´es. Keress¨ uk meg a {τi1 , τi2 |Ji ∈ J} halmaz egy minim´alis elem´et. Jel¨olje a hozz´atartoz´ o indexet i. Ha i nem egy´ertelm˝ uen meghat´arozott, akkor a lehets´eges indexek k¨oz¨ ul v´alasszuk a legkisebbet. uk a Ji • 3. l´ep´es. Ha a 2. l´ep´esben v´alasztott elem τi1 akkor helyezz¨ munk´at a list´ank k-adik hely´ere, t¨or¨ olj¨ uk a J halmazb´ ol, ´es n¨ovelj¨ uk k ´ert´ek´et 1-gyel. Majd l´epj¨ unk az 5. l´ep´esre. • 4. l´ep´es. Ha a 2. l´ep´esben v´alasztott elem τi2 akkor helyezz¨ uk a Ji munk´at a list´ank l-adik hely´ere, t¨or¨ olj¨ uk a J halmazb´ ol, ´es cs¨okkents¨ uk l ´ert´ek´et 1-gyel. Majd l´epj¨ unk az 5. l´ep´esre. • 5. l´ep´es. Amennyiben J u ¨res, akkor v´ege az elj´ar´ asnak. Az optim´alis u ¨temez´est kapjuk meg, ha az elj´ar´ as sor´an meghat´arozott lista sorrendje szerint hajtjuk v´egre a munk´ akat k´esleked´es n´elk¨ ul. Ellenkez˝ o esetben l´epj¨ unk a 2. l´ep´esre. Az elj´ar´as helyess´ege egyb˝ol k¨ovetkezik a k¨ovetkez˝ o t´etelb˝ ol. 11.3. t´ etel. Ha egy permut´ aci´ os flow shop probl´ema egy k´esleltet´est nem tartalmaz´ o S u ¨temez´es´eben egy Ji munk´ ara ´es az u ¨temez´esben ut´ ana k¨ ozvetlen¨ ul k¨ ovetkez˝ o Jl munk´ ara min{τi1 , τi2 , τl1 , τl2 } = min{τl1 , τi2 } teljes¨ ul, akkor arra az S 0 u ¨temez´esre, amelyet u ´gy kapunk S -b˝ ol, hogy felcser´elj¨ uk az Ji ´es Jl munk´ akat a maxim´ alis befejez´esi id˝ o legfeljebb akkora lesz, mint az S u ¨temez´esben. A fenti elj´ar´ast fejlesztette tov´ abb J. R. Jackson egy speci´alis job shop u ¨temez´esi modell megold´as´ara. A tov´ abbiakban olyan job shop u ¨temez´esi probl´em´at tekint¨ unk, amelyben k´et g´ep van M1 ´es M2 , minden munka legfeljebb k´et m˝ uveletb˝ol ´all, ´es amennyiben egy munka k´et m˝ uveletb˝ ol ´all akkor azt a k´et m˝ uveletet k¨ ul¨onb¨oz˝o g´epeken kell v´egrehajtani, amelyek hozz´a vannak rendelve a m˝ uveletekhez. Ezt a feladatot oldja meg a k¨ovetkez˝ o elj´ar´as.
8 Jackson algoritmus • 1. l´ep´es. K´epezz¨ uk a k¨ovetkez˝ o halmazokat: K12 = { azon k´et m˝ uveletb˝ ol ´all´ o munk´ ak, amelyek m˝ uveleteib˝ ol az els˝ot az M1 a m´asodikat az M2 g´epen kell v´egrehajtani }, K21 = { azon k´et m˝ uveletb˝ ol ´all´ o munk´ ak, amelyek m˝ uveleteib˝ ol az els˝ot az M2 a m´asodikat az M1 g´epen kell v´egrehajtani }, K1 = { azon munk´ ak, amelyek egy, az M1 -en v´egrehajtand´o m˝ uveletb˝ol ´allnak }, K2 = { azon munk´ ak, amelyek egy, az M2 -en v´egrehajtand´o m˝ uveletb˝ol ´allnak }. • 2. l´ep´es. Rendezz¨ uk a K12 ´es a K21 halmazokat a Johnson elj´ar´ as szerint. • 3. l´ep´es. Rendezz¨ uk a K12 ∪K1 ∪K21 halmaz elemeit u ´gy, hogy K1 -ben tetsz˝oleges legyen a rendez´es, ´es K12 legnagyobb eleme kisebb legyen mint K1 legkisebb eleme, tov´ abb´ a K1 legnagyobb eleme kisebb legyen, mint K21 legkisebb eleme. Jel¨olje ezt a rendez´est (K10 , ≺). uk a K21 ∪K2 ∪K12 halmaz elemeit u ´gy, hogy K2 -ben • 4. l´ep´es. Rendezz¨ tetsz˝oleges legyen a rendez´es, ´es K21 legnagyobb eleme kisebb legyen mint K2 legkisebb eleme, tov´ abb´ a K2 legnagyobb eleme kisebb legyen, mint K12 legkisebb eleme. Jel¨olje ezt a rendez´est (K20 , ≺). ¨temezz¨ uk a munk´ akat (K10 , ≺) szerint, az • 5. l´ep´es. Az M1 g´epen u 0 M2 -n pedig (K2 , ≺) szerint. 11.4. t´ etel Az algoritmus val´ oban egy optim´ alis megold´ as´ at adja meg a job shop probl´em´ anak k´et g´ep eset´en.
