Matematika | Felsőoktatás » Vizvári Béla - Diszkrét optimalizáció

V. DISZKRÉT OPTIMALIZÁCIÓ El®szó  kötetben Ez a rész a diszkrét optimalizációval foglalkozó fejezeteket tartalmazza. Az elso  témái: egy formális rendszer ütejelenik meg az Ütemezéselmélet címu  fejezet, amelynek fo mezési feladatok osztályozására, az ütemezések szemléltetésére szolgáló Gantt-diagramok, egygépes feladatok, párhuzamos berendezésekkel kapcsolatos feladatok, végül az egy- és többutas ütemezési feladat. Ebben a fejezetben végig feltesszük, hogy az ütemezés megkezdésekor minden adat ismert A második kötet része lesz az Versenyképességi elemzés címu  fejezet, amelyben az üte algoritmus folyamatosan kapja az adatokat, és a kapott adatokat – a késobb   mezo beérkezo adatok ismerete nélkül – fel kell dolgozni. 9. Ütemezéselmélet (Vizvári Béla) Egy ütemezési feladat megoldása egy üzem, üzemrész, muhely  vagy berendezés tevékeny ségének meghatározását jelenti rögzített idoszakon

belül. Ez két dolgot takar: egyrészt egy  termelési feladat kiválasztását, másrészt a kiválasztott feladat megoldásának idobeli megter és ezeknek megfeleloen  vezését. Ehhez számba kell venni az üzemben ható összes tényezot, kialakítani egy modellt, majd azt minden konkrét esetben megoldani. Ebben a fejezetben  elore,  feltesszük, hogy az üzem muködése  pontosan jelezheto ezért csak determinisztikus modellekkel foglalkozunk. A termelést fel kell osztani kisebb részekre. Nem mindegy, hogy a dolog melyik oldalát ragadjuk meg. Ha a termelésnek a tevékenység jellege a fontos, akkor feladatokról vagy tevékenységekrol  beszélünk, ha azonban a termelés anyagi oldalát kívánjuk hangsúlyozni, akkor a munkadarab vagy a sorozat fogalmát használjuk. (Az utóbbin egyforma munkadarabokat kell érteni, amelyek együtt haladnak át a termelés minden fázisán) A munkadarabok  tulajdonságaikra külön felhívjuk a gyelmet. és a sorozatok sok

tekintetben hasonlók, eltéro Ha a munkadarab vagy a sorozat fogalmával dolgozunk, akkor azt gondoljuk, hogy az adott  darabokból állnak, a termelés pedig úgy folyik, hogy üzem termékei zikailag elkülönítheto a majdani termék valamely kiinduló állapotban bekerül az üzembe, és bár változik az egyes fázisokon, lényegében mégis ugyanaz marad, azaz nem épül össze más termékekkel, illetve  nem válik több részre. Ebben az esetben a munka tárgyát tekintjük alapvetonek, de ekkor is  a célból beszükség van arra, hogy a munkát, mint tevékenységet felosszuk részekre. Ebbol vezetjük a muvelet  fogalmát. Egy muvelet  az az átalakítás, amit egy gép egyszerre elvégez a munkadarabon. Ha tehát egy munkadarab többször kerül ugyanarra a gépre, akkor több  van szó. muveletr  ol A rendszer harmadik fontos elemét a technológiai körülmények alkotják, melyeken  mind az általános, mind a vizsgált idoszakra vonatkozó egyedi

feltételeket, ezen belül a gépek kapacitását és a termelés során rendelkezésre álló és igényelt eroforrásokat,  a raktá is. rozási és szállítási feltételeket értjük. Modellezési szempontból ide soroljuk a munkaerot  gépek általában különbözo  technológiai feladatokat látnak el, de elofordulhat,  A különbözo hogy egyes gépek helyettesíthetik egymást.  A gépekkel kapcsolatos legfontosabb kérdések a következok: 1. miben mérjük a kapacitásukat; 2. mi a gépeknek a technológiai folyamatban betöltött helye; 3. mi a gépek és a megmunkálások viszonya. 364 9. Ütemezéselmélet (Vizvári Béla) Ezek a kérdések természetesen nem függetlenek egymástól. Mivel egy vállalatnál a termelés célja nyereség elérése, ezért a modellben tekintettel  nyereségre. kell lenni a költségekre, a termékek eladási árára és a terméken keletkezo Mindaz, amit eddig felsoroltunk, még csak egy elvi üzem kereteit szabja meg.

Attól  üzemmé, hogy egy több-kevesebb pontossággal meghatározott termelési felválik muköd  o  megszorítást jelent adatot kell elvégeznie, aminek a megszervezése a feladat, ami igen eros  a lehetoségeknek a technológiai feltételek által megengedett végtelen gazdag tárházával szemben A továbbiakban egyes esetekben nem kell megkülönböztetni a tevékenységeket, a munkadarabokat és a sorozatokat. Ilyenkor összefoglaló néven munkafeladatról fogunk beszélni 9.1 Formális rendszer ütemezési feladatok osztályozására Ismert egy formális rendszer, amellyel az ütemezési feladatokat nagyon tömören le lehet   feltételeírni. Ez a formális rendszer nem öleli föl az összes lehetoséget, ezért a következo zések állandóan érvényben vannak: 1.  minden gép a teljes vizsgált idoszakban rendelkezésre áll; 2. minden munkafeladat elvégzésére egyetlen technológiát határoztunk meg; 3. minden gép egyszerre csak egy munkadarabon

dolgozhat; 4. minden gép, az esetlegesen szükséges átszerszámozástól eltekintve, azonnal megkezd megmunkálást, mihelyst az eloz  ot  befejezte; heti a következo 5. a gyártásközi raktár(ak) kapacitása végtelen; 6.  az elozés megengedett; 7.  munkadarab azonnal megmunkálható, mihelyst a gép szabaddá vált, a soron következo  o  megmunkálása már befejezodött.  feltéve, hogy a munkadarab eloz  ol  áll, melyeket így szokás jelölni: A feladatok leírása három mezob α|β|γ, (9.1) ahol α a gépekre és a legfontosabb technológiai adottságokra, β a munkafeladatokra, illetve ezeknek a gépekhez és egyéb körülményekhez való kapcsolatára vonatkozó feltétele több ket tartalmazza, végül γ a matematikai feladat célfüggvényét írja le. Az egyes mezok  tényezore vonatkozó információt is tartalmazhatnak.  A j-edik munkafeladat befejezési idopontja C j , határideje d j . Ezen munkafeladat mu veleteinek száma m j , és

az i-edik gépen való megmunkálásának ideje pi j . 9.11 Az α mez® Itt kell megadni a gépek számát és a technológiai útvonal típusát. A technológiai útvonal azt határozza meg, hogy a munkadarab milyen sorrendben keresi fel a gépeket. •  1,2,. : A gépek száma 1 (vagy 2 stb), a megadott számtól függoen 9.1 Formális rendszer ütemezési feladatok osztályozására • 365 P: Azonos párhuzamos gépek vannak, azaz egyetlen homogén gépcsoportról van szó,  és minden muvelet ahol bármely muvelet  bármely gépen elvégezheto,  bármelyik gépen ugyanannyi ideig tart. • Q: Hasonló párhuzamos gépek – csak a gépek sebességében van különbség, azaz a j-edik muveletnek  az i-edik gépen való elvégzése p j / si ideig tart, ahol p j csak a muve  si csak a géptol  függo  állandó. lettol, •  R: Általános párhuzamos gépek, ahol az egyes muveletek  ideje tetszoleges lehet a kü gépeken. lönbözo • • O: A

technológiai útvonal kötetlen. F: Egyutas ütemezési probléma, azaz minden munkadarab azonos sorrendben keresi fel a gépeket. •  J: Többutas ütemezési probléma, azaz a munkadarabok technológiai útvonala eltéro. Például a J3 többutas ütemezési problémában a gépek száma 3. Minden munkadarab technológiai útvonalának leírását külön meg kell adni. 9.12 A β mez®  tartalmazza az egyéb technológiai feltételeket. Ez a mezo •  speciálisak, például mindegyik 1 (azonos pi j = 1, pi j ∈ {1, 2} stb.: A megmunkálási idok hosszú), illetve mindegyik 1 vagy 2. •  vannak, azaz egy berendeidle: Olyan ütemezés is lehetséges, ahol betervezett állásidok zés annak ellenére sem dolgozik, hogy van olyan munkadarab, amelyik megmunkálásra vár. • pmtn: A muveletek  megszakítása megengedett. Ilyenkor a megszakítás nem okoz vesz teséget sem idoben, sem költségben. •  prec, tree: A munkafeladatok között megelozési reláció

áll fenn, melyet valamely G  irányított gráf ír le. Ha a mezoben tree szerepel, akkor G fa. •  lehet a rendelkezésre állási ideje, illetve, ha r j : Az egyes munkafeladatoknak különbözo  ennek eleget tesznek. itt még további feltétel szerepel, akkor a rendelkezésre állási idok •  lehet a határideje, illetve, ha itt még tod j : Az egyes munkafeladatoknak különbözo  ennek eleget tesznek. A határidoket  vábbi feltétel szerepel, akkor a határidok puha,  feltételeknek tekintjük. Ha a határidok  tényleges feltételeket jelenteazaz megsértheto nek, akkor egy szokásos jelölés d j .) • •  no-wait: A munkadarabok nem várhatnak a gépek elott. • • m j ≤ m: ˆ Az egyes munkadarabokhoz legfeljebb m ˆ muvelet  tartozik.   res, res1 Az eroforrások csak korlátozottan állnak rendelkezésre. Ha a mezoben res1  áll, akkor egyetlen eroforrásról van szó. overlap: átlapolás korlátlanul megengedett, azaz egy újabb gép már

dolgozhat a munka o  még nem fejezte be a muveletet. darabon, miközben az eloz  (Ez a sorozatok jellegzetes tulajdonsága.)  megszorítás nem A konvenció szerint, ha egy elem nem szerepel, akkor a megfelelo  érvényes. Például, ha nincs a mezoben pmtn, akkor ez azt jelenti, hogy a megmunkálások megszakítása nem lehetséges. 366 9. Ütemezéselmélet (Vizvári Béla) 9.13 A γ mez® A formális rendszer csak kompromisszumos, azaz a késéseket nem kizáró célfüggvényeket  a feladat, és csak enged meg. Ennek oka az, hogy minden más esetben nehezen kezelheto  a probléma. lineáris és egészértéku  programozási feladatokkal modellezheto  értékeket értelmezzük: Az egyes munkafeladatokhoz a következo • • • •  C j : a befejezési idopont, L j = C j − d j : a késés, T j = max{0, L j } : a tényleges késés, U j =sgn(T j ) : egységnyi büntetés.  többféleképpen lehet célfüggvényt formálni, például minimalizálhatjuk

Mindegyikbol  értékek maximumát, összegét, súlyozott összegét. Ennek megfeleloen  a megfelelo tizenkét  lehetséges célfüggvény a következo C max , Lmax , T max , U max , P P C j, w jC j , P P L j, w j L j, P P T j, P w jT j, Uj , P (9.2) w jU j , ahol a súlyok nemnegatívak. Ha a munkafeladatok száma adott, akkor az összeg minimalizálása ekvivalens a meg mennyiség átlagának a minimalizálásával, hiszen a két érték csak egy konstans szorfelelo zóban tér el egymástól. Azt az esetet, amikor a munkafeladatok folyamatosan érkeznek be, és a helyzet állandóan változik, on-line problémának nevezik. Ekkor csak a várható értéket lehet optimalizálni. Vagyis az összeg célfüggvény az on-line eset modellezését is szolgálja  célfüggvények száma kevesebb. Ugyanis Látható, hogy a lényegesen különbözo és P w j L j csak a konstans − P P w jC j w j d j tagban különböznek egymástól. Továbbá Lmax minima-

lizálása egyben minimalizálja a T max és U max célfüggvényeket is.  közül az elso  minimalizálja a másodikat, hiszen U max = 0 akkor és csak Az utóbbi ketto akkor, ha egyetlen munkadarab sem késik, azaz T max = 0. Az Umax célfüggvény szerepe  sem sért meg. csak annyi, hogy olyan ütemezést keresünk, amely egyetlen határidot A (9.2)-ben megadott függvények a reguláris célfüggvények közé tartoznak, melyek   Irregulárisnak nevezünk egy célértéke a befejezési idopontokban monoton növekedo. függvényt, ha nem rendelkezik ezzel a tulajdonsággal. Ilyen az ún sietés és a súlyozott pontosság minimalizálása, ahol • • E j = max{d j − C j , 0} : a sietés. P (v j E j + w j T j ) : a súlyozott pontosság.  Ezen célfüggvényeknek akkor van létjogosultsága, ha pontos elorejelzéssel rendelkezünk   az eladások várható idopontjáról. Ekkor elore gyártani azért haszontalan, mert raktározási költséggel jár.  lesz szó,

hanem valamely tulajdonságokat Némely esetben nem konkrét célfüggvényrol  valamennyi célfüggvényrol.  Ilyen esetben a γ mezobe  kielégíto f kerül. 9.1 példa Az 1 || P C j feladat az az egygépes ütemezési feladat, ahol a termékek ütemezésére 9.2 A Gantt-diagramok 367    a vizsgált idoszakon belül nincs megszorítás, azaz nincsenek határidok, rendelkezésre állási idok,  megelozési relációk stb.  összegét kívánjuk minimalizálni. Könnyen látható, hogy a feladat optimális A befejezési idok  növekvo  sorrendjébe rakjuk. Ezt a gyakran megoldásában a munkadarabokat a megmunkálási idok  eloforduló sorrendet az angol irodalomban SPT ütemezésnek nevezik. 9.2 példa A klasszikus egyutas ütemezési probléma háromgépes speciális esete F3 || C max Gyakorlatok 9.1-1 Írjuk le a formális nyelven azt a feladatot, amelyben a munkák azonos sorrendben  keresik fel a gépeket, és nem várhatnak a munkák a gépek elott. 

9.1-2 Van-e az 1|r j |C max feladatban olyan munka, ami t = 0-ban nem végezheto? munka 1. gép 2. gép 1. 3 22 3. gép 2 2. 22 20 20 3. 20 14 18 9.2 A Gantt-diagramok Az ütemezések szemléltetésének fontos eszköze az ú.n Gantt-diagram Ebben minden gépet   egy-egy idotengellyel szemléltetnek. Az idotengelyeken feltüntetik, hogy az egyes munkadarabok mikor kerülnek megmunkálásra az adott gépen, illetve a gépnek mikor van állásideje.  9.3 példa Tekintsük azt az F2 || C max feladatot, ahol n = 2, és a megmunkálási idoket az alábbi táblázat foglalja össze. munkadarab 1. gép 2. gép 1. 3 1 2. 2 2 Ha mindkét gépen az (1,2) sorrendet alkalmazzuk, akkor a 9.1 ábrához jutunk Ha pedig a fordított sorrend szerinti ütemezést tekintjük, akkor a 9.2 ábrán látható Ganttdiagramot kapjuk A Gantt-diagramok fontos eszközei a matematikai bizonyítások szemléltetésének. Segítségükkel könnyen beláthatók az alábbi állítások Itt

végig feltesszük, hogy az egyes gépeken csak a megmunkálások sorrendjét kell megadni, ugyanis nincs értelme az ütemezés  megmunkálással várni. Ez még nem zárja ki a betervezett állásidok  szerint soron következo   egy munkadarab bevár egy másik lehetoségét, hiszen itt még lehetséges, hogy egy gép elott  munkadarabot azért, hogy az megelozze.  Tekintsünk egy tetszoleges ütemezést és egy rögzített i gépet. A gép muködését  a Gantt muköd  és álló szakaszokra osztja fel, hiszen mihelyst lekerül egy diagram egybefüggo  o 368 9. Ütemezéselmélet (Vizvári Béla) 1 1. gép 0 2 1 2 3 4 5 6 1 2. gép 0 1 2 3 7 8 7 8 2 4 5 6 9.1 ábra A Gantt-diagram az (1,2) ütemezés esetén 2 1. gép 0 1 1 2 3 4 5 2 2. gép 0 1 2 3 6 7 8 6 7 8 1 4 5 9.2 ábra A Gantt-diagram a (2,1) ütemezés esetén  azonnal rákerül a másik, azaz úgy tekintjük, hogy a gép folyamatomunkadarab a géprol, 

munkája. san dolgozik, feltéve persze, hogy van egyáltalán az adott pillanatban végezheto  szakaszt. Jelölje Tekintsünk egy ilyen összefüggo • • • J az ehhez a szakaszhoz tartozó munkadarabok halmazát,  t a szakasz kezdetének idopontját,  ri j ( j ∈ J) a j-edik munkadarab megérkezésének idopontját az i-edik gépre adott ütemezés szerint (ri j tulajdonképpen a j-edik munkadarab rendelkezésre állási ideje az i-edik gépen) • ui j ( j ∈ J) a j-edik munkadarab ütemezését, vagyis a j-edik munkadarab megmunkálásának megkezdését, az i-edik gépen. Ekkor nyilvánvaló, hogy minden j ∈ J esetén t ≤ ri j . (9.3)   a gép állna, miközben egy munkadarab Különben ugyanis közvetlenül a t idopont elott várna a megmunkálásra. Hasonlóképpen teljesülnie kell, hogy minden i és minden j ∈ J esetén ri j ≤ ui j . (9.4)  szakaszon belül átrendezhetjük a megmunkálások sorrendjét, de terAz összefüggo  mészetesen az így

adódó új ütemezésnek is ki kell elégítenie a (9.4) egyenlotlenségeket  szakasz összefüggo  marad, akkor teljesülnie kell a Továbbá, ha a muköd  o t + k X piπ(l) l=1 ≥ riπ(k+1) , k = 0, . , | J | −1 , (9.5) 9.3 Ütemezési problémák egyetlen gépen csere előtt . csere után . 369 j1 j2 j2 j3 j3 j1  cserének nincs hatása a C max értékre. 9.3 ábra A (95) feltételt kielégíto  egyenlotlenségeknek, ahol π a J-beli munkadarabok új sorrendjét jelöli. Végül tegyük fel, hogy az i-edik gép minden technológiai útvonalon az utolsó, azaz itt   idoszak  befejezodik a termelés. Legyen továbbá a vizsgált muköd  o az utolsó. Ekkor bár milyen átrendezés ezen a szakaszon, ami megorzi a szakasz összefüggését, nem változtatja  o  munkadarab befejezési idopontját,  meg az utolsónak befejezod ami t + X pi j , (9.6) j∈ J azaz nem változtatja meg a C max értéket (lásd a 9.3 ábrát) Gyakorlatok

9.2-1 Ábrázoljuk az alábbi egyutas ütemezési feladat (3,2,1) sorrendu  ütemezését Ganttdiagramon. munka 1. gép 2. gép 1. 3 22 3. gép 2 2. 22 20 20 3. 20 14 18 9.2-2 Hogyan változik a célfüggvény értéke az F2||C max feladatban, ha úgy rendezzük át  szakaszán, hogy az egynél több szakaszra a munkákat a második gép utolsó összefüggo bomlik? 9.3 Ütemezési problémák egyetlen gépen A legegyszerubb  ütemezési feladatokban csak egyetlen gép van. A valóság általában bonyolultabb De ez az eset részfeladatként felmerül a bonyolultabb helyzetekben Továbbá jól alkalmazható, ha valamelyik berendezés szuk  keresztmetszetet jelent. Az alábbi három tétel azt mondja ki, hogy számos esetben nem érdemes megszakítást  tartalmazó ütemezéssel foglalkozni. és betervezett állásidot 9.1 tétel Ha f reguláris célfüggvény, akkor az 1 | d j , prec, idle, pmtn | d j , prec, idle | f feladatoknak van közös optimális

megoldása. f és az 1 | 370 9. Ütemezéselmélet (Vizvári Béla)  nem szerepelnek, Megjegyzés. Mivel a feladatok leírásában a rendelkezésre állási idok ezért a konvenció szerint minden j esetén r j = 0.  Bizonyítás. Bármely pillanatban minden – még be nem fejezodött – munkadarab megmun kálható, feltéve természetesen, hogy elozményei elkészültek már. Ezt a feltételt azonban minden megengedett ütemezésnek teljesítenie kell. Tegyük fel, hogy valamely megengedett ütemezésben a j1 munkadarab megmunkálását a j2 munkadarab kedvéért megszakítottuk.    Innen következik, hogy j1 nem elozménye j2 -nek, és j2 minden elozménye befejezodött j1  megmunkálásának ezen, megszakított szakasza elott. Tekintsük most már azt az ütemezést, amit úgy nyerünk, hogy j1 megmunkálásának ezen megszakított szakaszát csatoljuk a foly megmunkálásokat tatásához, közvetlenül az elé, és a j1 ezen két megmunkálása közé eso   hiszen

j1 ezen megmunkálások után fog befejezodni,  elobbre hozzuk. Ez megteheto, így   o  munkadarabnak sem. Ezen átj1 nem elozménye egyetlen, ebbe a szakaszban befejezod rendezés mellett egyetlen munkadarab esetén sem növeltük a C j értéket, így a célfüggvény regularitásából adódik, hogy a célfüggvény értéke nem növekedett. 9.2 tétel Ha f reguláris célfüggvény, akkor az 1 | d j , prec, idle, pmtn | f és az 1 | d j , prec, pmtn | f , illetve az 1 | d j , prec, idle | f és az 1 | d j , prec | f feladatoknak van közös optimális megoldása.   van. Ekkor a Bizonyítás. Tegyük fel, hogy a [t1 , t2 ] idointervallumban betervezett állásido   o  szakaszt elore megmunkálások sorrendjét nem változtatva meg, a t2 idopontban kezdod   megelozések  hozhatjuk t2 − t1 > 0 idovel. Ezáltal nem zavarjuk meg a kötelezo betartását,  míg a C j értékek nem nonek, tehát a célfüggvény regularitásából következik ismét, hogy 

értéke nem nott.  a két tételbol  adódik egy újabb állítás. Ebbol 9.3 tétel Ha f reguláris célfüggvény, akkor az 1 | d j , prec, idle, pmtn | f és az 1 | d j , prec | f feladatoknak van közös optimális megoldása. Bizonyítás. Az 1 | d j , prec, idle, pmtn | f és az 1 | d j , prec, idle | f feladatnak van közös | d j , prec, idle | f és az 1 | d j , prec | f optimális megoldása a 9.1 tétel szerint, az 1 feladatnak pedig a 9.2 tétel szerint Ez a közös megoldás kielégíti az 1 | d j , prec, idle, pmtn | f feladat feltételeit is, mert csak annyi történt, hogy nem használtuk ki a megszakítás és az  lehetoségét.  ütemezett állásido 9.4 példa Fontos rámutatni arra, hogy mennyire lényeges volt minden j esetén az r j = 0 feltétel  adatokkal. Tekintsük azt a feladatot, amelyben csak két munkadarab van a következo munkadarab pj rj dj 1. 2 0 4 2. 2 1 2  hogy a 2. munkadarabot semmiképp sem lehet határidore  Észreveheto,

befejezni, tehát a maximális késés, azaz T max ≥ 1. T max reguláris célfüggvény Az 1 | d j , prec, idle, pmtn | T max , az 9.3 Ütemezési problémák egyetlen gépen 1 0 2 1 2 1 3 4 2 0 1 1 0 2 2 1 0 1 5 1 3 2 1 371 4 5 4 5 4 5 1 3 2 2 3  különbözok.  9.4 ábra Eltérések az optimális megoldásban, ha a rendelkezésre állási idok 1 | d j , prec, idle | T max , az 1 | d j , prec, pmtn | T max és az 1 | d j , prec | T max feladatok optimumát rendre a 9.4 ábrán látható ütemezések adják Az utolsó esetben csak egyetlen sorrend lehetséges, ami persze így optimális is. Ez az egyetlen  és olyan megoldás, ahol T max = 2, minden más esetben T max = 1. A fenti megoldások közül az elso  feladatnak, azonban ennél mindkét a harmadik azonos, és a második is optimális megoldása az elso  megoldás esetében csak a 2. munkadarab munkadarab késik, míg az elso Az alábbiakban néhány könnyebb feladat optimális

megoldását adjuk meg. Az optimális megoldást minden esetben valamely általánosan használható, egyszeru  heurisztikus szabály szolgáltatja, így a szükséges számítások mennyisége kicsi. Számos más feladat azonban ún NP-teljes probléma, azaz jelenlegi tudásunk mellett csak leszámlálási módszerekkel oldható meg Egy optimalizálási feladat megoldó eljárását akkor nevezzük leszámlálási  megoldást explicit módon kipróbál vagy implicit módszernek, ha valamennyi szóba jöheto módon kizár azok közül, akik optimálisak lehetnek.  heurisztikus módszerek ezekben az esetekben is képesek jó Azonban az ismertetendo  megengedett megoldások eloállítására, a célfüggvény optimális értékének becslésére. Az említett heurisztikus módszerek mindig valamilyen egyértelmu  sorrendet jelente elemét, [2] a nek. Ennek a sorrendnek a jelölése: [1], [2], , [n], ahol [1] a sorrend elso sorrend második elemét jelenti stb. Ha egy

bizonyításban több sorrendet vizsgálunk, akkor  zárójelekkel jelöljük. ezeket különbözo 9.4 tétel Az 1 | d j | Lmax feladat egy optimális megoldását a d[1] ≤ d[2] ≤ · · · ≤ d[n] (9.7) sorrend adja meg.  sorrend neve a legkorábbi határidok Megjegyzés. Az állításban szereplo  sorrendje (EDD).  Bizonyítás. Jelöljön < 1 >, < 2 >, , < n > egy tetszoleges sorrendet. Ha ez nem EDD 372 9. Ütemezéselmélet (Vizvári Béla) sorrend, akkor van egy olyan l index, hogy d<l> > d<l+1>   Tegyük fel, hogy < l > megmunkálása a T idopontban kezdodik. A két munkadarab késése ekkor L<l> = C <l> − d<l> = T + p<l> − d<l> , L<l+1> = C <l+1> − d<l+1> = T + p<l> + p<l+1> − d<l+1> .  hogy az Tekintsük azt az (1), (2), . , (n) sorrendet, amely csak annyiban különbözik ettol, említett két munkadarabot felcseréljük. Így a többi

munkadarab késése nem változik, míg a két felcserélt munkadarab új késése = C(l) − d(l) = C(l) − d<l+1> = T + p<l+1> − d<l+1> , L(l+1) = C (l+1) − d(l+1) = C (l+1) − d<l> = T + p<l> + p<l+1> − d<l> . L(l) Könnyen látható, hogy L<l+1> ≥ L(l) , L(l+1) ,  vagyis a célfüggvény értéke nem nott. Ezt a gondolatmenetet mindaddig megismételhetjük, amíg a cserékkel egy EDD sorrendet nem kapunk. Az 1 | r j , d j | Lmax feladat esetében már nem ilyen egyszeru a helyzet, mert a prob-   változata léma teljes általánosságában NP-teljes. Az elobbi heurisztikus módszer következo speciális esetekben megoldja a feladatot. 9.5 tétel Ha egy, az 1 | r j , d j | Lmax feladatosztályhoz tartozó feladat esetében teljesül, hogy nem létezik olyan j és l, melyekre r j < rl és dl < d j , (9.8) akkor az alábbi rekurzív módszer a feladat egy optimális megoldását adja. Tegyük fel, hogy a

keresett sorrend elso  j − 1 tagját már meghatároztuk. Legyen N = {1, , n}{[1], , [ j − 1]}, továbbá α = max{C[ j−1] , min{rl : l ∈ N }} és S = {l ∈ N : rl ≤ α } . Legyen [ j] ∈ N egy olyan munkadarab, amelyre d[ j] = min{ dl : l ∈ S } . (9.9) 9.3 Ütemezési problémák egyetlen gépen 373 Megjegyzés. A kiválasztás logikája tehát az, hogy [ j] a még nem ütemezett munkada rabok közül egyike azoknak, amelyek megmunkálása a legkorábban megkezdodhet és ezek  közül a legkorábbi határidovel rendelkezik.  Bizonyítás. Legyen < 1 >, < 2 >, , < n > egy tetszoleges sorrend. Erre vonatkozóan legyen N j = {1, . , n}{< 1 >, , < j − 1 >}, α j = max{C< j−1> , min{rl : l ∈ N j }} és Sj = {l ∈ N j : rl ≤ α j } .  sorozatot alkotnak. Ezért, ha l Nyilvánvaló, hogy az α j értékek monoton növo ∈ Sj teljesül, akkor l ∈ S j+1 , S j+2 , . mindaddig, amíg az l

munkadarab ütemezésre nem kerül Ha az < 1 >, < 2 >, . , < n > sorrend nem elégíti ki a rekurzív szabályokat, akkor két eset lehetséges, nevezetesen valamely j indexre  közé tartozik, azaz (i) [ j] megmunkálása nem a legkorábban megkezdhetok r[ j] > α j , vagy (ii) van olyan l ∈ S j , hogy dl < d[ j] , rl ≤ αj . (9.10)  Tekintsük eloször az (i) esetet. Vegyük észre, hogy α j deníciójából következik, hogy mindig van olyan l ∈ N j munkadarab, amelyre α j ≥ rl teljesül. Tegyük fel, hogy a vizsgált  ilyen [ j] után, azaz sorrendben [k] az elso r[ j] , r[ j+1] , . , r[k−1] > α j, r[k] ≤ αj . Ekkor (9.8)-ból következik, hogy d[ j] , d[ j+1] , . , d[k−1] ≥ d[k] . Tudjuk, hogy L[k] = C[k−1] + p[k] − d[k] . Innen L[k] − L[l] = C[k−1] + p[k] − d[k] − C[l−1] − p[l] + d[l] ≥ p[k] − d[k] + d[l] ≥ p[k] , l = j, . , k − 1 (9.11) Vagyis [k] késése legalább p[k] -val

nagyobb, mint a [ j], . , [k − 1] munkadarabok késése Tekintsük most azt az (1), (2), . , (n) sorrendet, amelyet a   [l],    (l) =  [k] ,    [l − 1] , > l vagy = l, j < l ≤ k ha j ha j ha j > k, 374 9. Ütemezéselmélet (Vizvári Béla)  egyenloség deniál. Ebben a sorrendben C l értéke l = 1, , j − 1 esetén változatlan, j =   továbbá k + 1, . , n esetén nem nott, legfeljebb csökkent, mert elmarad az r[ j] − α j állásido, (l) = [l − 1]  l = j + 1, . , k esetén pedig legfeljebb p( j) = p[k] értékkel nott Végül L( j) = α j + p( j) − d( j) , azaz L( j) − L[k] = α j − C[k−1] < 0 , tehát ebben az esetben a késés csökkent. Innen (911) alapján adódik, hogy a maximális  késés nem nott. Tekintsük most a (ii) esetet. Ekkor válasszuk meg a k indexet úgy, hogy [k] legyen a  amely (9.9)-et kielégíti Ezután az eloz  o  esetben alkalmazott gondolatsorrendben az

elso,  menet megismételheto. 9.6 tétel A p[1] ≤ w[1] sorrend az 1 || P p[2] w[2] p[n] ≤ ··· ≤ w[n] (9.12) w j C j feladat egy optimális megoldását adja. Megjegyzés. Ennek neve súlyozott legrövidebb megmunkálási idok  sorrendje (SWPT).  Bizonyítás. Jelöljön < 1 >, < 2 >, , < n > egy tetszoleges sorrendet. Ha ez nem SWPT sorrend, akkor van egy olyan l index, hogy p<l> > w<l> p<l+1> w<l+1> . (9.13) Ha felcseréljük ezt a két munkadarabot, akkor a többi munkadarab befejezési ideje nem  a két munkaváltozik, vagyis a célfüggvény értékében bekövetkezett változás pusztán ettol  a darabtól származik. A felcserélés elott (C <l−1> + p<l> )w<l> + (C<l−1> + p<l> + p<l+1> )w<l+1> taggal járultak hozzá a célfüggvény értékéhez, míg utána a (C <l−1> + p<l+1> )w<l+1> + (C<l−1> + p<l+1> + p<l>

)w<l>  különbsége mennyiséggel. A ketto p<l> w<l+1> − p<l+1> w<l> , ami pozitív, mint az azonnal látható (9.13) alapján Ha valamennyi súly 1, vagyis pusztán az összeget minimalizáljuk, akkor (9.12) az SPT sorrendet adja. 9.3 Ütemezési problémák egyetlen gépen 375  azért Amikor a tétel állításában a feladatot leírtuk, akkor a rendelkezésre állási idok  nem szerepeltek, mert mindegyik 0 volt, amit fel is használtunk akkor, amikor egy tetszo  munkadarabot felcserélhetonek  leges sorrendben két tetszoleges, egymást követo vettünk.  viszont azért nem szerepeltek, mert létük nem befolyásolja a feladatot, hiszen A határidok  megsérthetok, így csak a célfüggvényre lehetnek hatással.  tétel elég általános módszert ad arra az esetre, amikor a sorrendet megelo A következo zési relációk korlátozzák. 9.7 tétel Minden j ( j = 1, , n) esetén legyen f j monoton növo  függvény; legyen

továbbá fmax (C 1 , . , C n ) = max{ f j (C j ) : egy tetszoleges  S j = 1, . , n} Jelölje N a munkadarabok halmazát, és P ∗ ⊂ N esetén legyen p(S ) = j∈S p j és fmax (S ) azon feladatnak optimális megoldásának értékét, amelyben csak az S -beli munkadarabok szerepelnek. Végül legyen V azon munkadarabok halmaza, amelyeknek nincs rákövetkezoje.  Ekkor ∗ fmax (N) ∗ = min{max{ f j ( p(N)), fmax (N { j})} : j ∈ V} . (9.14)  következik, hogy a célfüggvény reguláris. Megjegyzés. A tétel feltételeibol Bizonyítás. Nyilvánvaló, hogy bármely megengedett sorrendben a legutolsó munkadarab  csak olyan lehet, amelynek nincs rákövetkezoje. Tegyük fel, hogy az optimális sorrendben ∗ a j munkadarab az utolsó. Ekkor fmax (N) értékét vagy j adja, és az ekkor f j ( p(N)), vagy ∗ egy másik munkadarab, és az ekkor fmax (N { j}). 2 A (9.14) képlet segítségével megadható egy O(n ) futási ideju  algoritmus a feladat

megoldására.   Mint említettük, a megszakítás lehetoségének akkor láthatjuk elonyét, amikor a rendel különbözok.  kezésre állási idok Erre ad egy példát az alábbi tétel az SPT sorrend egy meg általánosításával. Tekintsük az 1 | r j , pmtn | felelo P C j feladatot. Legyen T = {r1 , , rn }  Tegyük fel, hogy a t idopontig bezárólag elkészült már az ütemezés, amikor a jt munkadarab mellett döntöttünk. 0 0  p , . , pn A Jelölje a munkadarabok mindenkori még megmaradt megmunkálási idoit 1   idopont,  t idopont után a következo amikor dönteni kell, u 0 = min{t + p j , min{ s ∈ T : s > t}} . t  Azt kell tehát eldönteni, hogy az u idopontban melyik ju munkadarab kerüljön megmunká kiválasztási szabályt alkalmazzuk: lásra. Erre a következo 0 pj A sorrend neve: 0 u 0 = min{ p j : p j > 0; r j ≤ u} . legrövidebb megmaradt megmunkálási (9.15) idok  sorrendje (Shortest Remaining Processing

Time, SRPT). 9.8 tétel Az 1 | r j , pmtn | P C j feladatnak egy optimális megoldását az SRPT ütemezés adja meg. Bizonyítás. A bizonyítás hasonló a 96 tételéhez, ezért azt az Olvasóra bízzuk A feladat súlyozott változata, azaz 1 | r j , pmtn | P w j C j , azonban NP-teljes. 376 9. Ütemezéselmélet (Vizvári Béla) Végül egy olyan feladatot mutatunk be, ahol a célfüggvény nem reguláris: a késések és sietések összegét minimalizáljuk, feltéve, hogy a munkadarabok határideje azonos. Formális jelöléssel az 1 | idle, d j = d ≥ Pn j=1 pj | P (E j + T j ) feladatot tárgyaljuk. Itt tehát  körül szétosztani a munkákat úgy, hogy azok arról van szó, hogyan lehet a közös határido  legközelebb legyenek a határidohöz.  a leheto Akkor merülhet fel ilyen vagy hasonló fel szezonális hatást mutat, azaz a szállításoknak rövid idon  belül kell adat, ha az igény eros megtörténniük.  szakaszra bontunk fel. A kezdeti

szaMinden ütemezést egy kezdeti és egy befejezo  kaszhoz tartoznak mindazok a munkadarabok, amelyek megmunkálása befejezodött a közös   szakaszhoz tartozik az összes többi munkadarab. A kezd határidoig bezárólag, a befejezo   munkadarab megmunkáládeti szakasz, mint idointervallum, tart a szakaszhoz tartozó elso  a szakaszhoz tartozó utolsó munkadarab megmunkálásának befejezéséig, sának kezdetétol,  szakasz pedig a kezdeti szakasz végétol  az utolsó munkadarab megmunkálásának a befejezo befejezéséig. Most néhány lemmában leírjuk az optimális megoldások legfontosabb tulajdonságait,  melyek segítségével aztán egy egyszeru  algoritmus adódik azok eloállítására. 9.9 lemma Az optimális megoldásokban az elso  és az utolsó megmunkálás között nincs állásido.   akkor a kezdeti szakasz esetén az állásido  elotti,   Bizonyítás. Ha van állásido, a befejezo  utáni megmunkálásokat a határido  felé tolhatjuk el

úgy, hogy a szakasz esetén az állásido sorrend változatlan marad. Ezzel a célfüggvény értéke csökken 9.10 lemma Van olyan optimális ütemezés, amelyben egy megmunkálás pontosan a határidokor  fejezodik  be.  és az utolsó megmunkálás Bizonyítás. Tekintsünk egy olyan ütemezést, amelyben az elso  és amelyre az állítás nem igaz. Ekkor a befejezo  szakasz elso  munkaközött nincs állásido,   darabjának, jb -nek, a megmunkálási idointervalluma a belsejében tartalmazza a határidot.   módon: Toljuk el idoben az egész ütemezést a következo i ha a kezdeti szakasz tartalmaz kevesebb megmunkálást, akkor jb megmunkálásának végpontja essen egybe d-vel,  szakasz tartalmaz kevesebb megmunkálást, akkor jb megmunkálásának ii ha a befejezo kezdete essen egybe d-vel, iii különben (i) és (ii) valamelyikét alkalmazzuk. Az (i) és (ii) esetben csökkent a célfüggvény értéke, a (iii) esetben nem változott. Az SPT sorrend

fordítottjának neve LPT sorrend, azaz leghosszabb megmunkálási ido.  9.11 lemma Bármely optimális megoldásban a megmunkálások a kezdeti szakaszban LPT, a befejezo  szakaszban SPT sorrendben vannak. Bizonyítás. Ha két szomszédos munkadarab ütemezése fordított, akkor ezeket felcserélve a célfüggvény értéke csökken. 9.4 Ütemezési problémák párhuzamos berendezéseken 377 9.12 lemma Legyen (1), (2), , (n) egy olyan ütemezés, amelyben az elso  és az utolsó megmunkálás között nincs állásido  és amelyben egy megmunkálás pontosan a határidokor  fejezodik  be. Ha a kezdeti szakaszban α, a befejezo  szakaszban β megmunkálás van (α + β = n), akkor a célfüggvény értéke α X j=1 ( j − 1) p( j) + β X (β − j + 1) p(α+ j) . (9.16) j=1 Bizonyítás. A kezdeti szakaszban (α) sietése 0, (α− 1) sietése p(α) , (α− 2) sietése p(α−1) + p(α) stb. Tehát p(α) pontosan α− 1 munkadarab sietésében szerepel,

p(α−1) α− 2 munkadarabéban  összeget. Hasonlóan járhatunk el a befejezo  szakasz esetén. (α + 1) stb. Innen kapjuk az elso késése p(α+1) , (α+2) késése p(α+1) + p(α+2) stb. Tehát p(α+1) összesen β munkadarab késésében szerepel, p(α+2) β − 1 munkadarabéban stb. Ez adja a második összeget  állítás. (9.16)-ból még kiolvasható a következo 9.13 lemma Az eloz  o  lemma jelöléseit használva van olyan optimális megoldás, amelyben | α − β |≤ 1 . Bizonyítás. Legyen (1), (2), , (n) egy olyan ütemezés, amelyre a lemma állítása nem  szakasz igaz. Ha α ≥ β + 2, akkor toljuk el az ütemezést úgy, hogy (α) legyen a befejezo  munkadarabja. Ekkor (916) elso  összege (α − 1) p(α) -val csökkent, a második összege elso  (β + 1) p(α) -val nott, vagyis a teljes változás (β + 2 − α) p(α) ≤ 0.  megoldási módszer adódik. Tegyük fel, hogy az indexek szerinti Innen a következo  optimális sorrend egyben az

LPT sorrend is. Ekkor az utolsó lemma feltételeinek eleget tevo megoldás esetén (9.16)-ban p1 szorzója 0, p2 és p3 szorzója 1, általában p2l és p2l+1 szorzója  hogy a 2l és a 2l + 1 munkadarab közül melyik legyen l. Vagyis szabadon dönthetünk afelol,  az (l + 1)-edik, illetve hátulról az l-edik. elölrol Gyakorlatok 9.3-1  feltétel Konkrét példa megadásával bizonyítsuk be, hogy a 9.4 tételben szereplo  szerinti növekvo  rendezés nem szükséges feltétele az Lmax nem szükséges, azaz a határidok optimalizálásának.  súlyozott legrövidebb megmunkálási 9.3-2 Mutassuk meg, hogy a 96 tételben szereplo  sorrendje az adott esetben nem csak elégséges, hanem szükséges feltétel is. idok 9.4 Ütemezési problémák párhuzamos berendezéseken  álló homogén gépcsoportról Az ide tartozó legegyszerubb  feladatok esetében egy m gépbol van szó, azaz minden gép egyforma. Így egy munkadarab megmunkálási ideje minden gé eltekintve –

NP-teljesek, pen azonos. A feladatok még ebben az esetben is – kevés kivételtol   ezért nagy jelentosége van a heurisztikus eljárásoknak. Eloször a polinomiális eredményeket ismertetjük, és utána tárgyaljuk a heurisztikus módszereket. 378 9. Ütemezéselmélet (Vizvári Béla) 9.14 tétel A következo  ütemezés a P | overla p | P C j feladat egy optimális megoldását adja. Legyen [1], [2], , [n] egy SPT sorrend Ekkor minden gépen pontosan egyforma az ütemezés, és minden gépen a j-ediknek ütemezett megmunkálás a [ j] megmunkálás (1/m)-ed része.  Bizonyítás. Tekintsünk egy tetszoleges ütemezést és legyen (1), (2), . , (n) a megmunkálások befejezési sorrendje Legyen 1 ≤ j1 < j2 ≤ n Tegyük fel, hogy ( j1 ) egy h1 hosszú    megmunkálása az m1 gépen késobb kezdodik a t1 idopontban, mint a ( j2 ) egy h2 hosszú  megmunkálása az m2 gépen a t2 idopontban, azaz t1 > t2 . Az m1 és m2 gép nem feltétle Ekkor a két

megmunkálás egy min{h1 , h2 } szakasza felcserélheto,  és így az nül különbözo. összes többi, valamint a ( j2 ) megmunkálás befejezése nem változik, ( j1 ) befejezése pedig  vagy változatlan, vagy elobbre kerül.  két tétel a témakör egyik legkorábbi dolgozatából származik. A következo 9.15 tétel A P | pmtn | f feladatban az átfutási ido  legalább     n   X   1   ∗ p j , max{ p j : j = 1, . , n} C = max      m  j=1  (9.17) Bizonyítás. Mivel az átlapolás nem megengedett, ezért egy megmunkálás akárhány részre is legyen felosztva, ezek a részek nem fedhetik át egymást, azaz minden j esetén p j ≤  a teljes átfutási ido  nem lehet rövidebb annál, mint amit úgy kapunk, hogy a C j . Másfelol megmunkálásokat egyenletesen osztjuk szét a gépek között. 9.16 tétel A P | pmtn | C max feladat optimális célfüggvényértéke a (917) képletben adott mennyiség.

Bizonyítás. Egyenként készítünk ütemezést a gépekre Minden gépet a C ∗  idopontig ter- helünk le munkával, hacsak el nem fogytak a megmunkálások. A megmunkálásokat tet  megmunkálás még befér az éppen szoleges sorrendben vesszük. Ha a soron következo  gép C ütemezendo ∗  idokorlátjába, akkor egyetlen egységben ezen a gépen végezzük el a megmunkálást az erre a gépre már ütemezett megmunkálások után közvetlenül. Ha a teljes  megmunkálás nem fér be az idokorlátba, akkor a megmunkálás akkora részét ütemezzük   gép elso  erre a gépre, hogy ezzel az idokorlátot elérjük, a maradék rész pedig a következo  megmunkálása. Az idokorlát megválasztása miatt ez a két rész nem nyúlhat egymásba. Vegyük észre, hogy az így készített ütemezésben a megszakítások száma legfeljebb m − 1, és minden megmunkálást legfeljebb egyszer szakítunk meg. A minimálisan szükséges megszakítások számának

meghatározása már NP-teljes probléma. Ha egy megmunkálást  gépre került, akkor a tényleges termelés során a megszakítottunk, és egy része a következo  megmunkálás ezzel az átvitt résszel kezdodik. 9.4 Ütemezési problémák párhuzamos berendezéseken 379  A problémák úgy is felfoghatók ebben a körben, mint két részfeladat együttese, eloször meg kell találni a megmunkálások gépek közötti optimális felosztását, majd az egyes gépeken a legjobb sorrendet. Innen az egy gép esetére mondottak alapján azonnal adódik az alábbi tétel. 9.17 tétel Az R || P C j , illetve az R || P w j C j feladat optimális megoldásában a megmun- kálások minden gépen SPT, illetve SWPT sorrendben vannak. 3  tétel bizonyításában O(n ) muvelet A következo  segítségével vezetjük vissza az ütemezési feladatot a polinomiális hozzárendelési feladatra. 9.18 tétel Az R || P C j feladat polinomiális ido  alatt megoldható. Bizonyítás.

Tekintsünk egyetlen ml gépet Tegyük fel, hogy ezen nl (nl ≤ n) megmunkálást akarunk végezni, az (1), (2), . , (nl ) sorrendben Ekkor a célfüggvény értéke ezen a gépen n X l (nl − j + 1) pl( j) , (9.18) j=1  bináris változókat: ahogy ezt például a 9.12 lemmában is láttuk Vezessük be a következo      1,    x(ik) j =        0 ha a j-edik megmunkálást az i-edik gépen végezzük, sorrendben hátulról a k-adiknak , (9.19) különben . Itt k értéke 1 és n közötti egész. Két további feltételcsoport adódik még: (i) minden megmunkálást el kell végezni, (ii) minden gép egyszerre csak egy megmunkálással foglalkozhat.  az alábbi egyenletekkel, a másodikat pedig az azokat követo  egyenlotlensé Az elsot  gekkel írhatjuk elo: m X n X x(ik) j = 1, j = 1, . , n , (9.20) i=1 k=1 n X x(ik) j ≤ 1, i = 1, . , m, k = 1, . , n (9.21) j=1 Ha x(ik) j = 1, akkor a j megmunkálás

költsége a célfüggvényben k pi j , ezért a teljes költség m X n X n X i=1 k=1 k pi j x(ik) j , (9.22) j=1 amit minimalizálni kell. Az így kapott (919)–(922) feladat egy hozzárendelési probléma,  alatt megoldható. ami polinomiális ido 380 9. Ütemezéselmélet (Vizvári Béla)  transzformáció költségeit”. Az Érdemes szemügyre venni a bizonyításban szereplo ” eredeti feladat mérete m × n volt. A jelenlegié pedig (mn) × n (az átfogalmazott feladatban az i, k indexpár egyetlen index szerepét játssza). A hozzárendelési feladat megoldásához 3 szükséges muveletek  száma O(n ) marad. Reguláris célfüggvények mellett bizonyos esetekben a dinamikus programozás természetes módon adódik, mint egy pontos megoldási módszer. A 917 tétel azt mondja, hogy az R || P C j és a R || P w j C j feladatok esetében, ha megtörtént a megmunkálások felosz- tása az egyes gépek között, akkor az egyes gépeken a sorrend kötött.

Hasonló eredmény a  következo. 9.19 tétel Az R || P T j feladatnak van olyan optimális megoldása, amelyben a megmun- kálások minden gépen a határidok  szerinti növekvo  sorrendben vannak. Bizonyítás. Ha a feltétel nem teljesül, akkor van legalább egy gép, amelyen az ütemezés   egy korábbi határideju szerint egy késobbi határideju  megmunkálás közvetlenül megeloz  megmunkálást. E két megmunkálást felcserélve a célfüggvény értéke nem növekszik  azaz a megengedett ütemezés kereHasonló állítás mondható az U max célfüggvényrol,  (lásd a 9.4 tételt) Fontos megjegyezni, hogy ebben lényeges szerepet játszik, hogy sésérol  azonos. A C max célfüggvény esetén nemcsak egy, hanem minden rendelkezésre állási ido bármely sorrend rendelkezik a tételbeli tulajdonsággal, mert a megmunkálásoknak gépekre  Dinamikus progravaló felosztása már egyértelmuen  meghatározza a teljes átfutási idot.  mozással olyan

feladatokat lehet viszonylag könnyen megoldani, amelyekre a következo feltétel teljesül: A megmunkálások indexsorrendje olyan sorrend, hogy van olyan optimális megoldás, hogy minden (S ) gépen a megmunkálások ebben a sorrendben vannak.  feltételeztük, hogy a Nem jelenti az általánosság megszorítását, hogy az indexsorrendrol kívánt tulajdonságú. Vizsgálni fogjuk mind az fmax , mind a P f j típusú célfüggvényt. A tárgyalás nagyon hasonló, ezért az alábbi közös jelölést használjuk: F j (t1 , . , tm ) az optimális célfüggvé j megmunkálást ütemezzük, és a gépek állásido  nyérték, ha csak az indexsorrendben elso  fejezik be. nélkül dolgozva munkájukat a t1 , . , tm idopontokban 9.20 tétel Ha az (S) feltétel teljesül, akkor az R || F j (t1 , . , tm ) P f j feladat esetén = min{ f j (ti ) + F j−1 (t1 , . , ti − pi j , , tm ) : i = 1, . , m} (9.23) Bizonyítás. Most utoljára a j megmunkálást

ütemezzük, és ez az (S) feltétel miatt valame lyik gépen utolsónak fejezodik be az eddig ütemezettek közül. Ha ez történetesen az i gép,  o  megmunkálás a ti − pi j idopontban   akkor ott a j-t közvetlenül megeloz fejezodik be. Így  o  j − 1 megmunkáláson F j−1 (t1 , . , ti − pi j , , tm ) költség, továbbá f j (ti ) felmerül az eloz költség a j megmunkáláson. 9.4 Ütemezési problémák párhuzamos berendezéseken 381 9.21 tétel Ha az (S) feltétel teljesül, akkor az R || fmax feladat esetén F j (t1 , . , tm ) = min{max{ f j (ti ), F j−1 (t1 , , ti − pi j , , tm )} : i = 1, , m} (9.24)  o  tételéhez. Bizonyítás. A bizonyítás hasonló az eloz  Θ(mnC ), ahol C a teljes átfutási ido  felso  korlátja. Jobban korlátozza A számítási ido m a módszer alkalmazását, hogy a szükséges tárolási kapacitás Θ(mC ). Amennyiben az F m  táblákat explicit módon tároljuk, akkor sem a számítás

függvényt tartalmazó kitöltendo  mennyisége, sem a szükséges memória nagyságrendje nem csökkentheto. A heurisztikus módszerekkel legtöbbet a P || C max feladatot vizsgálták, mert ütemezési szempontból egyszeru,  de NP-teljes. Listás ütemezésnek nevezik azt a heurisztikus eljárást,  két lépésbol  áll: amely a következo 1. Meghatározzuk a megmunkálások valamely sorrendjét (lista). 2.  az elsonek  Az adott sorrendben véve a megmunkálásokat, az éppen soron következot  gépre rakjuk. megüresedo Ha L jelöli az adott listát, akkor C(L) a heurisztikus megoldás célfüggvényértéke, míg az ∗ optimális megoldásé C , és a C(L)/C ∗ hányadost vizsgáljuk. 9.22 tétel Tetszoleges  L lista esetén C(L) 1 ≤2− C∗ m . (9.25) Bizonyítás. Ha sikerül teljesen egyenletesen szétosztani a gépek között a megmunkálásokat,  akkor az átfutási idore n X 1 pj m j=1  legalább egy gépen legalább annyi idot  fel

kell használnunk, mint a legadódik. Másfelol  hiszen az átlapolás nem megengedett, azaz hosszabb megmunkálási ido, max{ p j : j = 1, . , n} ∗  o  megmunkálás. Ez a egy másik alsó korlát C -ra. Legyen k az utolsónak befejezod   t = C(L) − pk idopontban kezdodött el. Mivel az ütemezésben nincsenek felesleges állá  sidok, így a t idopontig valamennyi gép folyamatosan dolgozott. Ezért t ≤ 1 m X pj . j,k Végül a C(L) = t + pk ≤  egyenlotlenséget kapjuk. 1 m X pj j,k + pk = 1 m n X pj j=1 + m−1 m pk ≤ 2 − 1 m ! C ∗ (9.26) 382 9. Ütemezéselmélet (Vizvári Béla) A korlát éles. Erre vonatkozóan lásd a 9-5 feladatot  korlát. Számos heurisztikus eljárás pontosságára ismert a fentinél jobb felso 9.23 tétel C(LPT ) C∗ ≤ 4 1 − 3 3m . (9.27)  hogy Bizonyítás. Indirekt módon feltesszük, hogy a tétel állítása nem igaz Felteheto,  részállítás, amit bebizonyítunk, hogy

felteheto  az is, hogy az LPT sorrend m ≥ 2. Az elso szerinti ütemezésben utolsónak az utolsó, azaz a legrövidebb megmunkálási ideju  megmun kálás fejezodik be. Tekintsünk valamely rögzített m mellett egy olyan F ütemezési feladatot, amelyre (9.27) nem igaz, és n értéke minimális Ha az ütemezés szerint egy p < n indexu  0  megmunkálás fejezodik be utolsónak, akkor tekintsük azt az F ütemezési feladatot, ame úgy kapunk, hogy az LPT sorrendbol  csak az elso  p megmunkálást tartalmazza. lyet F-bol  nem változott, míg az optimális átfutási ido  nem nott.  Itt az LPT sorrend szerinti átfutási ido 0 Ezért a tétel állítása erre az F feladatra sem lehet igaz, ami ellentmond n minimalitásának. Innen (9.26) alapján kapjuk, hogy erre a feladatra 4 3 − 1 3m < C(LPT ) C∗ ≤ n X 1 mC ∗ pj + (m − 1) pn mC ∗ j=1 ≤1+ (m − 1) pn mC ∗ , ahonnan adódik, hogy pn > C ∗ 3 .  Ez természetesen az

LPT sorrend miatt valamennyi megmunkálási idore vonatkozik, azaz az optimális megoldásban legfeljebb két megmunkálás lehet egy gépen.  Tekintsünk egy tetszoleges olyan U ütemezést, ahol minden gépen legfeljebb két meg munkálás van. Megadunk néhány olyan átrendezést, amely nem növeli meg az átfutási idot Legyen két – az i gépre ütemezett – megmunkálás ideje ti1 és ti2 , míg egy másik j gép esetén t j1 és t j2 , illetve ha ezen csak egy megmunkálás van, akkor t j .  csökken, (i) Ha ti1 > t j1 és ti2 > t j2 , akkor i1 és j1 felcserélésével a két gépen az átfutási ido hiszen max{ti1 + t j2 , t j1 + ti2 } < ti1 + ti2 . (ii) Ha ti1 > t j , akkor az i2 munkát átrakva a j gépre a két gépen szintén csökken az átfutási  ido. (iii) Az i1 és i2 munkák sorrendjének felcserélése nem változtatja meg az i gépen az átfutási  idot.  kiindulva és elvégezve az összes lehetséges fenti Bármely lehetséges U ütemezésbol

 nem hosszabb, mint átalakítást, egy olyan V ütemezést nyerünk, amelyben az átfutási ido  tulajdonságokkal: U -ban, és rendelkezik a következo (a) ha bármely i, j gép esetén mindkét gépen két megmunkálás van, akkor (i) alapján ti1 > t j1 esetén ti2 ≤ t j2 , (b) minden i, j gép esetén, ha az i gépen két megmunkálás van, a j gépen egy, akkor (ii) alapján 9.4 Ütemezési problémák párhuzamos berendezéseken tj 383 ≥ ti1 , ti2 , (c) minden i gép esetén, ha az i gépen két megmunkálás van, akkor (iii) alapján ti1 ≥ ti2 ,  ezért felteheto,  hogy a gépek (d) mivel a gépek sorrendje nem befolyásolja az átfutási idot,  megmunkálási ido,  indexsorrendje szerint csökken az elso  gépek indexei (b) és (d) alapján kisebbek a két megmunká(e) az egy megmunkálást végzo  lást végzokénél,  gépek indexsorrendje szerint no  a második – azaz a nem (f) a két megmunkálást végzo  nagyobb – megmunkálási ido.

Tehát van olyan optimális megoldás, ami az (a)–(f) tulajdonságokkal rendelkezik, ezek a tulajdonságok azonban egyértelmuen  meghatározzák az ütemezést, ami nem más, mint az LPT lista szerinti ütemezés. Ez pedig ellentmond a C(LPT ) C∗ > 4 3 − 1 3m ≥1.  egyenlotlenségnek. A P || C max problémához nagyon hasonló, mintegy annak duálja a ládapakolási probléma. Egyforma kapacitású ládákba kívánunk belerakni tárgyakat, ahol a tárgyak méretét egyetlen számmal lehet jellemezni. Az egy ládába rakott tárgyak összmérete a méretek összege. Meghatározandó a minimálisan szükséges ládák száma Visszatérve a párhuzamos  például egy muszak berendezésekhez, tegyük fel, hogy a munkákat egy meghatározott ido,  alatt akarjuk elvégezni. Ekkor úgy merül fel a kérdés, hogy hány gépre van szükség FF(n, p, K) 1 2 for i ← 1 to n do zi ← K 3 m ← 1 4 for i ← 1 to n 5 j ← 1 6 while z j < pi do j ← j + 1 7 8

z j ← z j − pi 9 if j > m 10 11 then m ← j return m A ládapakolási feladat megoldására egy mohó heurisztikus eljárás a FF. Legyen K a ládák kapacitása. Feltesszük, hogy nincs olyan tárgy, aminek mérete nagyobb lenne, mint K, hiszen ekkor nincs megengedett megoldás. Ha ez a feltétel teljesül, és a tárgyak száma n, akkor legfeljebb n ládát kell használnunk. A FF algoritmus sorra veszi a tárgyakat, és mind (azaz a legkisebb indexu)  egyiket az elso  olyan ládába rakja, ahova belefér. A következo 384 9. Ütemezéselmélet (Vizvári Béla)  adat a tárgyak n száma, a tárgyak méretét tartalmazó p vektor, pszeudokódban a bemeno  adat a felhasznált ládák m száma. A kódban zi az valamint a ládák K kapacitása, kimeno i-edik láda még fel nem használt kapacitása. A FF és más ládapakolási algoritmusok elemzése megtalálható a 11.4 alfejezetben  korlátot adni a maximálisan A FF algoritmust akkor tudjuk felhasználni, ha

tudunk felso  szükséges kapacitásra, azaz az átfutási idore. 9.24 tétel Bármely P || C max feladat esetén az optimális C ∗ átfutási idore  teljesül, hogy     n   X   2   ∗ p j , max{ p j : j = 1, . , n} C ≤ max       m j=1  (9.28)   mennyiség. Indirekt Bizonyítás. Legyen C a (928) egyenlotlenség jobboldalán szereplo módon tegyük fel, hogy a tétel állítása nem igaz. Alkalmazzuk a FF algoritmust úgy, hogy a  szerinti, azaz a ládapakolási ládák kapacitása C és a megmunkálások a megmunkálási idok  sorrendben vannak. Ha a tétel állítása feladat nyelvén a tárgyak mérete szerinti csökkeno hamis, akkor az algoritmus kénytelen valamely k tárgyat az (m + 1)-edik ládába rakni. Nyilvánvalóan k ≥ m + 1 Mivel pk ≤ pk−1 ≤ · · · ≤ p1 , ezért minden láda legalább pk -ig fel  m ládába, ezért ezeket már jobban feltöltöttük, van töltve. Mivel azonban pk nem

fér az elso mint C/2. Innen adódik, hogy n X pj j=1 > mC 2 ≥ n X pj , j=1 ami ellentmondás. A bizonyításból érezni lehet, hogy a FF algoritmust úgy lesz célszeru  alkalmazni, ha    sorrendbe rakjuk, azaz az LPT sorrendet használjuk. elotte a megmunkálási idoket csökkeno  és erre alkalmazzuk a FF algoritTegyük fel, hogy megbecsüljük a szükséges átfutási idot, must. Természetesen egy jó megengedett megoldáshoz jutunk, ha az eljárás talál ilyet, azaz nem használ több ládát (gépet), mint amennyit felhasználhat. De ha nem talál megengedett  megolmegoldást, akkor lényegében nincs semmi a kezünkben, csak az a durva közelíto  o  tétel bizonyításából származik. Viszont a 915 tételbol  ismerünk egy alsó dás, ami az eloz   korlátból kiindulva, logaritmikus kereséssel egy korlátot az átfutási idore. Az alsó és felso pontosabb korlátot lehet kapni. Ez az FF ismételt alkalmazását jelenti, ahol csökkentjük a 

korlátot, ha találtunk megengedett megoldást, és növeljük az alsó korlátot, ha nem. felso Ne feledjük, hogy a 9.24 tétel bizonyítása mindenképpen ad egy megengedett megoldást, a most vázolt algoritmus ezt kívánja javítani. A fentiekben felvázolt algoritmus leírásánál az alábbi jelöléseket alkalmazzuk: Ka az aktuális alsó korlát, Kf  korlát, az aktuális felso K a pillanatnyi (azaz a kipróbálás alatt álló) korlát, s  iterációs lépések száma. a megteendo Továbbá részeljárásként muködik  némi módosítással a M́ algoritmus. Mivel a párhuzamos berendezések esetén nem az a kérdés, hogy hány berendezést kell használnunk, 9.4 Ütemezési problémák párhuzamos berendezéseken 385  belül végezni akarunk, hanem az, hogy K idon  belül m géppel végezni tudunk-e, ha K idon ezért a FF algoritmus módosítását megvalósító MF algoritmus mind a K kapacitáskorlátot, mind a gépek m számát

paraméterként kapja meg. Az algoritmus eredeti angol neve lentése: többszörös beillesztés). Multi-Fit”, amit rövidítve megtartunk (magyar je” MF(m, K) 2 Pn p , max{ p j : j = 1, . , n}} Pnj=1 j K f ← max{(2/m) p j , max{ p j : j = 1, . , n}} j=1 3  szerinti csökkeno  sorrendbe rendezzük a megmunkálásokat a megmunkálási idok 4 for i ← 1 to s 1 5 Ka ← max{(1/m) do K ← (Ka + K f )/2 M́(K, m, elég) 6 7 if elég =  then K f ← K 8 else Ka ← K 9 10 return Ka és K f  Annak eldöntésére, hogy az adott esetben m darab K kapacitású láda elegendo-e, a M́ eljárást használjuk. Ennek eredménye az elég logikai változó, melynek értéke akkor , ha M́ talált megengedett megoldást. M́(K, m) 1 elég ←  2 for i ← 1 to m 4 do zi ← K 5 for i ← 1 to n 6 j ← 1 7 do while z j < pi do j ← j + 1 8 if j > m 9 then elég ←

 10 11 return elég z j ← z j − pi 12  Az FF aln tárgy méretének összehasonlításos rendezéséhez O(n lg n) lépés elegendo. goritmus beépített változata minden tárgyra legfeljebb m lépést tesz meg, ez O(nm) számítási igény minden korlátra. Tehát az algoritmus muveleti  igénye O(n lg n + nms). A számítási  m − 1 tárgy olyan nagy, hogy egyenként kiigény ennyi is lesz abban az esetben, ha az elso  m − 1 gép közül úgy, hogy más megmunkálás már nem fér töltenek egyet-egyet az elso melléjük.  rendre 7, 7, 5, 5, 9.5 példa Tekintsük azt a feladatot, amelyben n = 5, m = 2 és a megmunkálási idok 5. Ekkor a listás ütemezés a két leghosszabb megmunkálást külön gépre rakja, majd mindkét gépre tesz  gépre rakni. Az átfutási ido  ekkor egy-egy 5 idejut,  végül az utolsó megmunkálást kénytelen az elso 17. Az optimális megoldás viszont az, amikor az azonos megmunkálási ideju  munkák ugyanazon

386 9. Ütemezéselmélet (Vizvári Béla)  csak 15. A 923 tételben megadott felso  korlát most 7/6. a gépen vannak, mert így az átfutási ido Ezzel megszorozva az optimális megoldás értékét, vagyis 15-öt, 17.5-et kapunk, vagyis az eljárás lényegében a hibahatáron dolgozik. Alkalmazzuk most ugyanerre a feladatra az MF algoritmust, m = 2 mellett. A kezdeti alsó korlát 14.5, amit 15-re lehet felkerekíteni  korlát 29, innen az induló korlát 22-nek adódik. A kezdeti felso  gépen a megmunkálási idok  rendre 7, 7, 5, míg a második gépen 5, 5. Mivel találEkkor az elso  korlát átlagát kell venni, ami kerekítéssel 18. Erre tunk megoldást, ezért az alsó és a pillanatnyi felso már az optimális megoldást kapjuk.  10, 7, 7, 6, 6, 4. A listás ütemezés az 9.6 példa Legyen most n = 6, m = 2 és a megmunkálási idok  gépre a 10, 6, 4 megmunkálási ideju elso  munkákat rakja, míg a másodikra a 7, 7, 6 idejuket.  Mivel  ezért ez az

optimális megoldás. Ha az MF algoritmust futtatjuk, mindkét gépen 20 az átfutási ido, akkor ott a kezdeti alsó korlát éppen ez a 20 lesz. Azonban 20 vagy annál nagyobb korlát esetén az eljárás mindig összerakja a 10 megmunkálási ideju  munkát legalább az egyik 7 idejuvel,  így sohasem fogja megtalálni az optimális megoldást. A két kezdeti korlát 20 és 40 Ezért az eljárás a 30 korláttal  gép 10, 7, 7, 6, a második gép 6, 4. Így a következo  korlát 25. Ekkor indul. Ehhez van megoldás: elso  korlát 22. Az ehhez tartozó megoldás a 10, 7, 7, illetve 6, 6, 4 megoldást kapjuk. Innen a következo  csak 21. Ezért a megoldás nem változik a következo  korlátra sem, 10, 7, 4 és 7, 6, 6. Itt az átfutási ido ami éppen ennyi. Innen már a 20 korlát következik, de mint azt említettük, ehhez nincs megoldás Ahhoz, hogy az algoritmus pontosságát elemezni tudjuk, vissza kell térni a ládapakolási feladathoz. Ha a ládák méretét minden

határon túl növeljük, akkor egyre kevesebb ládára lesz szük ség, egészen addig, amíg a ládák mérete el nem éri a tárgyak méreteinek összegét, mert ettol kezdve csak egy ládát kell használnunk. Az ütemezési probléma megoldása szempontjából bennünket rögzített számú láda felhasználása érdekel. Vegyük észre, hogy a 915 tételben  korlát között csak egy legfeljebb 2-es tényezo  megadott alsó korlát és a 9.24 tételbeli felso van. Ez az alábbi állítást sugallja: ha megnöveljük a ládák méretét a minimálisan szükségesnek legfeljebb a kétszeresére, akkor a FF algoritmus talál megengedett megoldást, fel téve, hogy a tárgyak méret szerint csökkenoen rendezettek. Az alábbiakban azt mutatjuk be, hogy ez az állítás lényegében igaz. Ezen felül az is teljesül, hogy az említett 2 korlátnál, ami rosszabb volna, mint a már elért 4/3 korlát, sokkal jobb az eljárás. ∗ Legyen p a tárgyak méreteit tartalmazó vektor,

továbbá C m (p) a ládák azon legkisebb mérete, amely mellett még van olyan pakolás, amely legfeljebb m ládát használ fel. Ne feledjük, hogy véges sok tárgyat csak véges sok féleképpen lehet szétosztani a ládák közt, ∗ ezért C m (p) nem csak inmumként, hanem minimumként is létezik. Mivel itt heurisztikus eljárásról van szó, így egyáltalán nem biztos, hogy a FF algoritmus bármely p és m esetén ∗ talál m ládát használó megoldást a C m (p) korláthoz. Felmerül a kérdés, hogy hányszorosra ∗ kell megnövelni a ládák méretét C m (p)-hez képest, hogy az algoritmus már találjon ilyent. Legyen FF(n, p, K) az FF algoritmus megoldása által használt ládák száma. Jelölje r azt a  ahányszorosára a ládák méretét növeltük. Legyen rm az a legkisebb tényezo,  amely tényezot, bármely feladat esetén biztosítja, hogy algoritmusunk legfeljebb m ládát használ, azaz ∗ rm = inf {r : minden p esetén FF(n, p, rC m (p))

≤ m} . ∗ 9.25 tétel Bármely p és r ≥ rm esetén FF(n, p, rC m (p)) ≤ m. 9.4 Ütemezési problémák párhuzamos berendezéseken 387  Bizonyítás. Legyen eloször r = rm . Ha most a tétel állítása nem igaz, akkor van egy olyan ∗ p méretvektor, hogy FF(n, p, rm C m (p)) > m. Ha egy tárgyat nem tudunk betenni egy ládába, annak az az oka, hogy a ládába tett tárgyak összmérete ezen tárggyal együtt meghaladná ∗  az adott az rm C m (p) korlátot. Tekintsük ezeket, az algoritmus végrehajtása során fellépo, ∗ korlátnál nagyobb mennyiségeket. Legyen ezek közül a minimális rm C m (p) + ε Mivel csak > 0. Legyen C olyan korlát, hogy rmCm∗ (p) < C < rm C m (p) + ε. Ekkor C megválasztásából következik, hogy FF(n, p, C) > m, ami r = ∗ C/C m (p) > rm mellett ellentmond rm megválasztásának. Legyen most már r > rm . Tegyük fel, hogy van olyan p méretvektor, hogy ∗ FF(n, p, rC m (p)) > m. Tekintsük

azt a q méretvektort, amelyben a ládák kapacitását ∗ (r /rm )C m (p)-ra növeltük, továbbá véges sok, a p vektor legkisebb eleménél kisebb tárgyat  van szó, ezért ε véges sok mennyiségrol ∗  legyen p optimális adunk a p tárgyaihoz úgy, hogy ezekkel a kis tárgyakkal kiegészítheto megoldása úgy, hogy a megnagyobbított ládák pontosan fel legyenek töltve. Ez azt jelenti, ∗ ∗ ∗ ∗  viszont feltettük, hogy C m (Q) = (r /rm )C m (p). Ekkor azonban rm C m (Q) = rC m (p) Másfelol ∗ ∗  felében hogy FF(n, p, rC m (p)) = FF(n, p, rm C m (Q)) > m, ami ellentmond a bizonyítás elso rm -re igazoltaknak.  a tételbol  már azonnal következik annyi, hogy a MF algoritmus legalább a loEbbol  legkisebb olyan korlátra fog megengedett megoldást garitmikus keresés folyamán fellépo ∗ találni, amely korlát nem esik rm C m (P) alá. 9.26 tétel Bármely p méretvektor és k ∈ Z+ egész esetén az MF algoritmus által

szolgáltatott megoldás C értékére igaz, hogy C ∗ (p) Cm ≤ rm + 2−k . (9.29)  valamint a befejezo  alsó és felso  Bizonyítás. Legyen az algoritmus kezdeti alsó és felso, korlátja, illetve eredménye rendre A, F, BA, BF és C. Itt C a talált megengedett megoldás átfutási ideje, amire nyilvánvaló, hogy BF ≥ C. Ha az állítás nem igaz, akkor van olyan q méretvektor, ahol rosszabb, azaz nagyobb értéket kapunk a (9.29) képletben megadott korlátnál. Mivel azonban az algoritmus által adott korlát legfeljebb C, adódik, hogy BF ≥ C > (rm + 2−k )Cm∗ (p). (9.30) ∗ A logaritmikus keresés tulajdonságai alapján A ≤ C m (p) ≤ F ≤ 2A, ezért BF − BA = 2−k (F − A) ≤ 2−k Cm∗ (p) . Innen (9.30) alapján adódik, hogy BA > rmCm∗ (P) .  FF algoritmust alkalmazni kellett a BA korlát mellett is, Ezért az eljárás részeként szereplo  o  tétel állításával szemben több, mint m gépet használt. és ekkor FF

az eloz  tételt. Bizonyítás nélkül említjük meg a következo 388 9. Ütemezéselmélet (Vizvári Béla) 9.27 tétel Minden m esetén rm ≤ 122 Gyakorlatok  rm mennyiség minden m ≥ 2 9.4-1 Bizonyítsuk be, hogy a 925–927 tételekben szereplo esetén nagyobb, mint 1.  9.4-2 Oldjuk meg azt a P2||C max feladatot, melyben a megmunkálási idok: 7, 7, 6, 6, 5, 5, 4, 4, 4. 9.5 Az egyutas ütemezési probléma Bár az egyutas ütemezési problémát nagyon sokat vizsgálták az irodalomban, a gyakor ezért csak a leglényegesebb eredmények ismertetésére latban viszonylag ritkán fordul elo, szorítkozunk.  pontosan egy darab van, Csak az F || C max feladatot tárgyaljuk. Tehát minden gépbol a gépek nem helyettesíthetik egymást, és minden munkadarab ugyanazon sorrendben halad végig a gépeken. Az általánosság megszorítása nélkül feltesszük, hogy ez a sorrend a gépek   indexsorrendje. Eroforrások és megelozési feltételek nem korlátozzák az

ütemezést. A fela  datnak még így is két esete van, az elozéses és az elozés nélküli. Az utóbbi azt jelenti, hogy  o  esetben a munkadarabok minden gépre ugyanolyan sorrendben kerülnek fel, míg az eloz  a munkadarabok sorrendje a gépek között változhat. Az elozés nélküli esetet fogjuk részle célunk az, hogy megmutassuk, hogy 2 és 3 gép esetén a két feladat tesen tárgyalni, de elso azonos.  jelölésre. Legyen a egy tetMinden további tárgyaláshoz szükségünk lesz a következo  szoleges munkadarab és k (1  ≤ k ≤ m) egy tetszoleges gép. Ekkor valamely rögzített ütemezés mellett F(a, k) az a munkadarab befejezési ideje a k gépen. 9.28 tétel Ha m > 1, akkor az elozéses  F || C max problémának van olyan optimális megoldása, ahol az utolsó két gépen a megmunkálások sorrendje azonos.   Bizonyítás. Tekintsünk egy tetszoleges optimális ütemezést, amelyben az utolsó elotti gé pen (1), (2), . , (n), az utolsó

gépen [1], [2], , [n] a munkadarabok sorrendje Eloször azt  megnövelése nélkül megváltoztatható úgy a sorrend az mutatjuk meg, hogy az átfutási ido utolsó gépen, hogy a két gépen az utolsó munkadarab azonos legyen. Legyen L azon mun termelési szakaszában vannak, kadarabok halmaza, melyek az utolsó gép utolsó összefüggo  után. Ebben a szakaszban minden kijelölt megmunkálás azonnal vagyis az utolsó állásido    a gépen befejezodött.  megkezdodik, mihelyst az elotte lévo [n] mindenképpen eleme L-nek. Ha L nem tartalmaz mást, akkor ez azt jelenti, hogy minden más megmunkálás az m gé befejezodött,  pen már azelott hogy az m − 1 gép [n] megmunkálásával végzett volna, ezért szükségképpen (n) = [n]. Vizsgáljuk azt az esetet, amikor L több elemet is tartalmaz Legyen [n] = (k) Ha k = n, akkor készen vagyunk Különben rendezzük át az utolsó gépen a sorrendet úgy, hogy az [n] = (k) munkadarab megmunkálását minden (l)

munkadarab meg munkálása elé visszük, ahol k < l ≤ n. Mivel (l) csak az F((l), m − 1) > F([n], m − 1) idopontban vagy az után kerülhet az m gépre, ezért az [n] munkadarab legfeljebb az F([n], m − 1)    idopontig kerül elobbre. Így azonban nem keletkezhet újabb állásido. Ha ezen átrendezés után a két gépen nem lenne azonos az utolsó munkadarab, akkor 9.5 Az egyutas ütemezési probléma 389 ismételten alkalmazható egy hasonló átrendezés, mindaddig, amíg a kívánt állapotot el nem  az utolsó elotti  értük. Ekkor a gondolatmenet megismételheto munkadarabokra, és így tovább.  jelöléseket fogjuk használni, tekintettel arra, hogy eloször  Az alábbiakban a következo  az elozéses feladatot vizsgáljuk. A j gépen a munkadarabok sorrendje [1] j , [2] j , , [n] j A szokásos feltételezések miatt az ütemezést egyértelmuen  meghatározza, ha a megmunkálások sorrendje minden gépen adott. Ezért az ütemezés

azonosítható a fenti m sorrend  együttesével. Továbbá ha a egy tetszoleges munkadarab, akkor j(a) az a munkadarab pozíciója a j gépen, azaz [ j(a)] j = a. 9.29 tétel Minden i, j (1 ≤ i ≤ n, F([i] j , j) 1 ≤ j ≤ m) esetén = max{F([i] j , j − 1), F([i − 1] j , j)} + p[i] j . j (9.31)   Bizonyítás. Az [i] j munkadarab megmunkálása a j gépen nem kezdodhet elobb, mint ahogy   o  megaz [i] j munkadarab megmunkálása a j − 1 gépen befejezodik, és mint ahogy az eloz   munkálás, azaz [i − 1] j -é, a j gépen befejezodik. Ekkor azonban azonnal meg is kezdodik és p[i] j j ideig tart. 9.30 tétel F([n]m , m) = (9.32)   i   m   X X     = max  p[α] j : minden j esetén j([i j−1 ] j−1 ) ≤ i j ; 1 = 1([i0 ]); im = n .      j=1 α= j([i − ] − )  j j j 1 j 1  következik, hogy az F([n]m , m) teljes átfutási ido  vagy Bizonyítás. A 929 tételbol  esetben egy géppel, F([n]m , m

− 1) + p[n]m m vagy F([n − 1]m , m) + p[n]m m . Tehát az elso a második esetben egy munkadarabbal lépünk hátulról visszafelé. Akármelyik kifejezés le arra mindaddig alkalmazható a (931) rekurzív képlet, míg egy gyen is a teljes átfutási ido, olyan összeget nem kapunk, ami a (9.32) képletben is szerepel  Tekintsünk most egy tetszoleges m X i X j p[α] j j (9.33) j=1 α= j([i j−1 ] j−1 )  feltételek teljesülnek. Vegyük észre, alakú összeget, ahol az indexhatárokra a megfelelo   hogy ebben egyetlen megmunkálás sem kezdodhet elobb, mint az összegzési sorrendben   Ugyanis ha j([i j−1 ]) < α ≤ i j , akkor az [α] j munkadarabnak a j gépen közvetlen elotte lévo. való megmunkálásáról van szó, amit [α − 1] j ugyanezen a gépen való megmunkálásának  meg kell eloznie. Ha α = j([i j−1 ]), akkor [α] j = [i j−1 ] j−1 , és [α] j -nek a j-edik gépen való  megmunkálását meg kell eloznie a ( j − 1)-edik gépen

való megmunkálásnak. Tehát a (933)   vele, alakú összegek alsó korlátok a teljes átfutási idore. Mivel egy közülük éppen egyenlo ezért a tétel állítása igaz. 390 9. Ütemezéselmélet (Vizvári Béla) d 9.31 deníció Egy feladat duáljának nevezzük azt a feladatot, ahol az i munkadarab pi j megmunkálási idejét a j gépen a d pi j = pi,m+1− j képlet adja meg. 9.32 tétel Egy F || C max feladatnak és duáljának optimális célfüggvényértéke megegyezik Bizonyítás. Tekintsük a feladat egy ütemezését Vizsgáljuk a duál feladat azon ütemezését,  ahol az (m − j)-edik gépen a megmunkálások sorrendjét a primál feladat adott ütemezésébol úgy kapjuk, hogy a j-edik gépen való sorrendet megfordítjuk, azaz a duál feladatban a sorrend az m − j gépen [n] j , [n − 1] j , . , [1] j Ekkor azonban mind a primál, mind a duál feladat esetén ugyanazok az összegek szerepelnek a (9.32) képletben, csak az összeadandók 

azonos, következésképp az optimális átfutási idok  sorrendje fordított. Így a két átfutási ido is azonosak. 9.33 tétel Az F || C max elozéses  feladatnál m ≤ 3 esetén van olyan optimális megoldás, hogy valamennyi gépen ugyanaz a megmunkálások sorrendje. Bizonyítás. m   adódik. = 1 esetén nincs elozés. Az állítás m = 2 esetén a 9.28 tételbol  és az eloz  ob  ol  pedig következik, hogy a feladatnak van olyan optimális Ezen utóbbi tételbol  két gépen azonos a sorrend. Viszont m = 3 esetén mind az elso  megoldása, ahol az elso két, mind az utolsó két gép egyike a második gép, így van olyan optimális megoldás, ahol mindhárom gépen azonos a sorrend.   9.7 példa Az elozés gyengíti a feltételeket, azaz több megoldást enged meg. Ezért az elozéses feladat   optimum értéke nem nagyobb, mint az elozés nélkülié. Az olyan feladatnak, ahol az elozéses megoldás határozottan jobb, legalább négy gépet és két

munkadarabot kell tartalmaznia. Ilyen minimális méretu   ellenpélda létezik, és a megmunkálási idoket az alábbi táblázat tartalmazza. gép 1. munkadarab 2. munkadarab 1. 3 1 2. 1 3 3. 1 3 4. 3 1   (lásd a 9.5 ábrát) Az elozés nélküli esetben az (1, 2) sorrend esetén 11 az átfutási ido  (lásd 9.6 ábra) A (2, 1) sorrend esetén is 11 az átfutási ido  két gépen (2, 1), a második két gépen (1, 2) a sorrend, akkor az átfutási ido  Ha viszont az elso csak 10 (lásd 9.7 ábra)  m ≥ 3 esetén még az elozés nélküli eset is NP-teljes. Két gépre viszont Johnson már 1954-ben megoldotta a problémát. 9.34 tétel Az F2 || C max feladat optimális megoldását a következo  algoritmus adja: 9.5 Az egyutas ütemezési probléma 1 1. gép 0 391 2 1 2 3 4 5 1 2. gép 0 1 2 3 6 7 8 9 10 11 6 7 8 9 10 11 9 10 11 2 4 5 1 3. gép 0 1 2 3 4 2 5 6 7 8 1 4. gép 0 1 2 3 4 5 6 2 7 8 9 10

11  az (1,2) ütemezés esetén. 9.5 ábra Az átfutási ido 2 1. gép 0 1 1 2 3 4 2 2. gép 0 1 2 5 6 7 8 9 10 11 5 6 7 8 9 10 11 8 9 10 11 10 11 1 3 4 2 3. gép 0 1 2 3 4 5 1 6 7 2 4. gép 0 1 2 3 4 5 6 7 1 8 9  a (2,1) ütemezés esetén. 9.6 ábra Az átfutási ido 1. Rendezzük a munkadarabokat a rövidebb megmunkálási idejük szerinti növekvo  sorrendbe. 2. Ezután ebben a sorrendben döntünk a munkák sorrendjérol.  Tegyük fel, hogy már van egy K kezdeti és egy B befejezo  sorozat. Ekkor a soron következo  megmunkálás aszerint kerül K végére, illetve B elejére, hogy a rövidebb megmunkálási ideje az elso,  illetve a második gépen volt-e. Bizonyítás. Tekintsünk két munkát, indexük legyen j és k, amelyek ebben a sorrendben   közvetlenül egymás után következnek. Legyen T 1 , illetve T 2 az az idopont, amikor j elott   illetve a második gépen. Ez azt jelenti, hogy a j minden

megmunkálás befejezodik az elso, 392 9. Ütemezéselmélet (Vizvári Béla) 2 1. gép 0 1 1 2 3 4 2 2. gép 0 1 2 5 6 7 8 9 10 11 5 6 7 8 9 10 11 8 9 10 11 10 11 1 3 4 1 3. gép 0 1 2 3 4 5 2 6 7 1 4. gép 0 1 2 3 4 5 6 7 2 8 9  elozéses  9.7 ábra Az átfutási ido ütemezés esetén.  gépen a T 1 idopontban   munkadarab megmunkálása az elso kezdodik meg, míg a második   gépen a max{T 1 + p1 j , T 2 } idopontban, azaz itt a max{T 1 + p1 j + p2 j , T 2 + p2 j } idopontban   fejezodik be. Ezért k megmunkálása a második gépen nem kezdodhet meg ennél, valamint  (T 1 + p1 j + p1k )-nál korábban. Összefoglalva azt kapjuk, hogy k befejezésének idopontja a második gépen max{T 1 + p1 j + p2 j + p2k , T 2 + p2 j + p2k , T 1 + p1 j + p1k + p2k } . (9.34)  Ha felcseréljük a két munkadarab sorrendjét, akkor a j befejezésének idopontja a második gépen max{T 1 + p1k + p2k + p2 j , T 2 + p2 j +

p2k , T 1 + p1k + p1 j + p2 j } . (9.35)  tagjai azonosak. Ezért, ha meg tudunk Vegyük észre, hogy az utolsó két képlet középso  tag maximuma mindig (9.34)-ban lesz határozni egy olyan sorrendet, amelyben a két szélso  tagban kisebb, akkor ez lesz az optimális sorrend. Vegyük észre azt is, hogy a két szélso a T 1 additív konstans szerepel, ami nem befolyásolja a maximum helyét, ezért ezt további vizsgálatainkból kihagyjuk. Legyen = p1 j + p2 j + p2k , B = p1 j + p1k + p2k = p1k + p2k + p2 j , D = p1k + p1 j + p2 j . A C Arra keresünk feltételt, hogy mikor lesz max{ A, B} A A ≤ max{C, D}. Látható, hogy ≤ C akkor és csak akkor, ha p1 j ≤ ≤ D akkor és csak akkor, ha p2k ≤ p1k p1k ≤ C akkor és csak akkor, ha p1 j ≤ p2 j B ≤ D akkor és csak akkor, ha p2k ≤ p2 j . B  hossza szerint négy esetet különböztetünk meg. A megmunkálási idok (9.36) (9.37) 9.5 Az egyutas ütemezési probléma (i) Ha p1 j ≤ p2 j és p1k ≥

393  azonnal adódik a kívánt reláció. p2k , akkor a fentiekbol  az elol  álló munka esetében az elso,  a Ez az az eset, amikor a rövidebb megmunkálási ido  mögötte lévonél pedig a második gépen van. (ii) Ha p1 j ≤ p2 j és p1k < p2k , akkor B   p1 j egyenlotlenségre is szükség van, amibol ≤ ≤ C és A p1k < > D. Ezért még az A ≤ C p2k , tehát mindkét munkának az  gépen rövidebb a megmunkálási ideje, és ezek közül is az elol  álló munkáé a rövidebb. elso  (iii) Ha p1 j > p2 j és p1k ≥ p2k , akkor B > C és A ≤ D, ezért az egyenlotlenség, amire szükségünk van, B ≤ D. Ez akkor igaz, ha p2k ≤ p2 j < p1 j , vagyis mindkét munkának a második gépen rövidebb a megmunkálási ideje, és ezek közül is a hátul álló munkáé a rövidebb. (iv) Ha p1 j > p2 j és p1k < p2k , akkor B > C és A > D, tehát a kívánt reláció nem  álló munkának a második, a hátul

állónak teljesülhet, vagyis nem lehetséges, hogy az elol  gépen legyen határozottan rövidebb a megmunkálási ideje. pedig az elso  A jelen szakasz további részében az elozés nélküli feladattal foglalkozunk. Az egyutas ütemezési probléma pontos megoldási módszerei többnyire vagy korlátozás és szétválasztás, vagy implicit leszámlálás típusú módszerek. A korlátozás és szétválasztás lényege, hogy a megengedett megoldások halmazát egyre kisebb részhalmazokra bontja fel,  legjobb megengedett megolmiközben (a) egyre pontosabban becsüli a részhalmazokba eso  eljárás során idonként  dások célfüggvényértékét, és (b) a becslo megengedett megoldásokat  Ily módon feleslegessé válnak azok a részhalmazok, ahol a becslés rosszabb, mint állít elo. az addig talált legjobb megoldás értéke. Az implicit leszámlálásnál a feltételek kielégíthe  tudunk levonni következtetéseket. Az ütemezési feladatok esetében ez azt

jelenti, toségéb ol hogy bizonyos típusú sorrendek esetén a célfüggvény értéke meghaladna egy meghatározott értéket.  Tanulságosak azok a teljes átfutási idore vonatkozó korlátok, amelyeket a korlátozás és szétválasztás típusú módszereknél kell használni. Az alsó korlátok mind a 9.30 tételt használják Két fajtájuk van, a gépre, illetve a mun abból indul ki, hogy az adott objektummal kapcsolatos kára alapozott alsó korlát. Mindketto összes megmunkálást (vagyis az adott gépen vagy az adott munkadarabon végrehajtandó  nélkül, és ez elott  és után is a összes megmunkálást) el kell végezni és ez sikerül is állásido  legkevesebb idot  használjuk fel. Mindezt az alábbi két tételben fogalmaztuk meg leheto 9.35 tétel Az F || C max feladat optimális célfüggvényértéke legalább max{ X j,l min{ p1 j , pm j } + m X pil : l = 1, . , n} (9.38) i=1  Bizonyítás. Tekintsünk egy tetszoleges l munkát. Ennek

végig kell mennie valamennyi gé  pen, vagyis a teljes átfutási idonek tartalmaznia kell ezen munka megmunkálási idoinek összegét (ez a második összeg a fenti képletben). Ezen felül minden más j munka vagy   gépen való megmunkálási ideje elotte van a sorrendben, és akkor ezen j munkának az elso hátrébb tolja l megmunkálásának kezdetét, vagy mögötte van, ekkor j megmunkálása az  l befejezéséhez kéutolsó gépen csak l befejezése után történik, vagyis a teljes átfutási ido pest ennyivel kitolódik. Akkor járunk a legjobban, ha pontosan azok a munkák vannak l 394 9. Ütemezéselmélet (Vizvári Béla)   gépen rövidebb, mint az utolsón. Vagyis – a elott, amelyeknek a megmunkálása az elso  9.30 tételhez hasonlóan – a két összeg olyan megmunkálásokat tartalmaz, amelyeknek idoben egymás után kell következniük 9.36 tétel Az F || C max feladat optimális célfüggvényértéke legalább max{min j i−1 X pl j l=1 + n X

pi j j=1 + min j m X pl j : i = 1, . , m} (9.39) l=i+1  Az elso  tag azt a legrövidebb Bizonyítás. A hármas összeg tagjainak jelentése a következo  adja meg, amennyinek mindenképpen el kell telnie ahhoz, hogy az elso  megmunkálás idot   ami alatt egy megkezdodhessék az i-edik gépen, és ez nem más, mint az a legrövidebb ido, munkadarab az i-edik gépet eléri. A második összeg a megmunkálások ideje az i-edik gépen   munkadarab elérte a gépet. Ezek természetesen csak azután kezdodhetnek meg, hogy az elso  ami alatt egy munkadarab elkészítését be Végül a harmadik összeg az a legrövidebb ido,  Vagyis hasonlóan a 9.30 tételhez, a lehet fejezni azután, hogy lekerült az i-edik géprol.  három tag olyan megmunkálásokra tartalmaz alsó becslést, amelyeknek idoben egymás után kell következniük. Általános szokás, hogyha egy nehéz feladat egy speciális esetét meg lehet oldani valamely egyszeru  eljárással, akkor úgy

készítenek heurisztikus eljárást az általános esetre, hogy visszavezetik” azt a megoldott speciálisra. Mivel az általános egyutas feladat is ne” héz, de ugyanakkor Johnson algoritmusa az m = 2 esetet megoldja, tehát pontosan a fenti helyzettel állunk szemben, pusztán az a kérdés, hogy hogyan lehet értelmezni a két gépet”. ”  Az idézojel itt arra vall, hogy ez a két gép csak absztrakt gép lesz, nem az eredeti feladat valamely gépe.  a fenti kérdésre válaszolnánk, érdemes szemügyre venni a Johnson algoritmusa Mielott  mögött meghúzódó gondolatot. Emlékezzünk rá, hogy azok a munkák kerültek elore, ame gépen, a hosszabb pedig a másodikon volt. lyeknek a rövidebb megmunkálási ideje az elso A sorrend végére pedig azok kerültek, amelyeknél a helyzet éppen fordított volt. Az ilyen  sorrend azt célozza, hogy minél elobb legyen munkája a második gépnek, vagyis ott ke majd miután az elso  gép befejezte a munkáját

(természetesen állásvés legyen az állásido,  nélkül), akkor minél rövidebb ideig kelljen a második gépnek dolgoznia. Kiterjesztve ido  gépeken kevés idot  használó ezt több gép esetére, olyan sorrendet szeretnénk, ahol az elso  munkák kerülnek elore, a hátsó gépeken keveset használók pedig a sorrend végére. Úgy lehet két gépet csinálni” a sokból, hogy bizonyos gépeket összevonunk”, azaz ” ”  megmunkálások egyetlen nagy megmunkálást úgy tekintjük, mintha az ezeken végzendo  az eredeti megmunkálási idok  összege. A fentiek adnának ki, ahol a megmunkálási ido  módon is meg lehet csinálni. Az egyik esetben elölrol  is és szellemében ezt két különbözo  részét gyelmen kívül hagyhátulról is ugyanannyi gépet tekintünk, míg a gépek középso  gépek száma mindkét oldalról, akkor a két mesterséges gépen juk. Ha r a tekintetbe veendo  a megmunkálási idok 9.5 Az egyutas ütemezési probléma r p1 j =

r X pi j , 395 m X r p2 j = i=1 pi j , j = 1, . , n (9.40) i=m−r +1 lesznek. Itt r = 1, , dm/2e Az így deniált kétgépes feladatokat minden r esetén különkülön megoldjuk Johnson módszerével, majd az így kapott sorrendre kiszámítjuk az eredeti feladat átfutási idejét. Végül az így kapott sorrendek közül a legjobbat választjuk Még ha  határának ilyetén megválasztása biztosítja, hogy minden, az eredeti m páratlan is, r felso  gépet legalább egyszer gyelembe veszünk. feladatban szereplo  A másik lehetoség, hogy a gépeket két részre osztjuk, és eszerint határozzuk meg a   csoportban r gép van, akkor a mesterséges gépeken a megmunkálási idoket. Ha az elso  megmunkálási idoket r p1 j = r X m X r pi j , p2 j = pi j , j = 1, . , n (9.41) i=r +1 i=1 adja meg. Itt r = 1, , m − 1 Minden másban úgy járunk el, mint fent Befejezésül azt mutatjuk meg, hogy az F | no-wait | C max probléma egy

utazóügynök  vissza. Ebben a feladatban tehát a munkák nem várhatnak a gépek elott,  feladatra vezetheto hanem éppen fordítva, a gépeknek kell várniuk a munkákra.   Ha a j-edik munkának sehol nem kell várnia a gépek elott, és gyártása a 0 idopontban  kezdodik, akkor a megmunkálása az r gépen a r X pi j i=1   idopontban fejezodik be. Tegyük fel, hogy közvetlenül utána a k munka következik, mely  nek gyártása a t ≥ 0 idopontban kezdodik. Tudjuk, hogy k csak akkor kerülhet az r gépre,  ha a megmunkálása az r − 1 gépen befejezodött, ami a t+ r −1 X pik i=1  idopontban következik be. Ekkor azonban az r gépnek szabadnak kell lennie, azaz teljesülnie kell a t+ r −1 X pik ≥ i=1 r X pi j i=1  egyenlotlenségnek. Vagyis t-nek el kell érnie legalább a r X pi j − i=1 r −1 X pik i=1 értéket. Mivel ennek minden gépre teljesülnie kell, ezért a k munka a j munka után   r r −1   X    X pi

j − pik r = 1, . , m max      i=1 i=1 (9.42) 396 9. Ütemezéselmélet (Vizvári Béla)   ol  idovel indítható. (Itt az üres összeg értéke szokás szerint 0, továbbá a megmunkálási idokr feltesszük, hogy nemnegatívak, így a fenti érték is nemnegatív.) Mivel a feltételezés szerint   a leheto  a megmunkálási idoket nem tudjuk változtatni, csak úgy tudjuk a teljes átfutási idot  várakozási idok  legrövidebbé tenni, hogy minimalizáljuk a munkák indításai között eltelo összegét. Ez azonban nem más, mint az az utazóügynök feladat, ahol a városok a munkák,  távolságot pedig a (9.42) képlet adja meg a közöttük lévo 9.6 A többutas ütemezési probléma A többutas problémák családja tartalmazza a legbonyolultabb ütemezési feladatokat. Itt semmiféle megkötés nincs a technológiai útvonalakra, még az is megengedett, hogy egy munka ne kerüljön minden gépre, és hogy egyes gépeket többször is

felkeressen. Egy megszorítás van, amit általánosan fel szoktak tenni, nevezetesen, hogy nincsenek párhuzamos  csak egy van. Ez annyit jelent, hogy minden megmunberendezések, azaz minden gépbol kálást egy meghatározott gépen kell elvégezni. Ahhoz, hogy egy feladatot pontosan meg lehessen fogalmazni és oldani, valamilyen matematikai modell kell. A két leggyakrabban használt modell az ún diszjunktív gráf mo dell és a diszkrét programozási modell. Eloször ezeket tárgyaljuk. Az alábbiakban az angol nyelvu  irodalomhoz hasonlóan a megmunkálás szó helyett a muvelet  kifejezést alkalmazzuk. Ennek oka az, hogy megmunkáláson inkább értjük az egy munkadarabon végzett átalakítást, míg muvelet  bármi lehet, még két különálló darab összehegesztése vagy egyetlen elem feldarabolása is.  Különösen áll ez az elsonek tárgyalandó diszjunktív gráf modellre. Ennek mélyebb megértéséhez hasznos a kritikus út módszerének ismerete. 9.61 A

kritikus út módszere Ez a módszer (CPM) nem képezi a jelen fejezet tárgyát, ezért itt csak a legfontosabb tudnivalókat foglaljuk össze. Tegyük fel, hogy valamilyen tevékenységek sorozatát – esetünkben valamely termékek gyártásához tartozó muveleteteket  – akarjuk elvégezni. Ezen tevékeny ségek között lehetnek bizonyos megelozési kapcsolatok, amelyek azt fejezik ki, hogy vala  mely tevékenységnek be kell fejezodnie ahhoz, hogy egy másik elkezdodhessék. A feladat  módon is leírható egy G irányított gráffal. Nekünk arra a változatra lesz több különbözo  szükségünk, ahol a gráf csúcsai a tevékenységek. Ekkor egy α csúcsból (tevékenységbol)  közvetlenül követheti. irányított él vezet minden olyan β csúcsba (tevékenységbe), amely ot  azaz az α csúcsból kiinduló vaAz él hossza az α tevékenység elvégzéséhez szükséges ido,  lamennyi él hossza azonos. Feltételezzük továbbá egy 0 hosszúságú ◦ kezdeti

és ∗ befejezo  tulajdonságokkal rendelkeznek. tevékenység létezését, amelyek a következo (i) A ◦ csúcsba nem vezet él. (ii) A ∗ csúcsból nem indul ki él.   és ∗-tól különbözo  tevékenység. Ekkor ◦-bol  vezet irányított (iii) Legyen α tetszoleges, ◦-tol út α-ba, és α-ból vezet irányított út ∗-ba. A G gráf egy fontos további tulajdonsága még, hogy (iv) A G gráf irányított kört nem tartalmaz. Ha ugyanis irányított kört tartalmazna, akkor a körbe tartozó valamennyi tevékenység meg- 9.6 A többutas ütemezési probléma 397  kezdésének az volna a feltétele, hogy a kör többi tevékenysége befejezodjön, azaz egyetlen, a körhöz tartozó tevékenységet sem lehetne elkezdeni.   Feltételezve, hogy az egész tevékenységsorozat a 0 idopontban kezdodik, igaz a követ kezo 9.37 tétel (a) Az egész tevékenységsorozat lehetséges legrövidebb átfutási ideje egyenlo  a ◦-bol  ∗-ba vezeto  leghosszabb út

hosszával. (b) Semmilyen α tevékenység sem kezdodhet  elobb,  mint a ◦-bol  az α-ba vezeto  leghosszabb út hossza. (c) Ha a tevékenységsorozat lehetséges legrövidebb átfutási ideje T , akkor egyetlen α tevékenység sem kezdodhet  késobb,  mint T − (α-ból ∗-ba vezeto  leghosszabb út hossza) anélkül, hogy a teljes átfutási idot  ne tolná ki T -n túlra. A tétel (a) részében említett leghosszabb úthoz tartozó tevékenységek csak egyetlen jól    meghosszabbítása nélkül, ezért meghatározott idopontban kezdodhetnek a teljes átfutási ido ezeket kritikusnak” hívják, innen ered az egész módszer elnevezése. ”  α lehetséges Jelölje pα , qα , rα rendre az α tevékenység elvégzéséhez szükséges idot,   meghosszabbítása nélkül és végül legkésobbi befejezési idejét a teljes átfutási ido α lehetséges legkorábbi kezdési idejét. Az utóbbi két mennyiség egy dinamikus programozási algoritmusból is

meghatározható. (Ebben fontos szerepet játszik, hogy a gráf nem tartalmaz  Bellman-egyenleteket az alábbi tétel adja meg. irányított kört.) A megfelelo 9.38 tétel Jelölje N a G gráf csúcsainak, A pedig éleinek halmazát Ekkor r◦ = 0 , minden α ∈ N {◦} esetén q∗ rα = max{rβ + pβ : (β, α) ∈ A} , = T , minden α ∈ N {∗} esetén qα = min{qβ − pβ : (α, β) ∈ A} . (9.43) (9.44) (9.45) (9.46) 9.62 A diszjunktív gráf modell  Tekintsünk két tetszoleges α, β muveletet.  Ezek az alábbi három viszony valamelyikében állnak egymással:  (i) az egyiknek meg kell eloznie a másikat (pl. azért, mert ugyanahhoz a munkadarabhoz  van szó, és a technológia eloírja  tartozó muveletekr  ol a sorrendjüket),  (pl. azért, mert mindketto  ugyanazt a gépet igényli), (ii) egyszerre nem végezhetok  munkadarabokon különbözo  gé(iii) nincsenek közvetlen hatással egymásra (pl. különbözo  muveletek). pekkel végzendo 

398 9. Ütemezéselmélet (Vizvári Béla) A fenti helyzetet a G = (N, C ∪ D) ú.n diszjunktív gráf írja le, ahol N a muveletek  hal-  relációkat leíró, konjunktívnak nevezett éleket tartalmazza, D maza, C az (i) kategóriába eso pedig a (ii) kategóriába tartozó relációkat reprezentáló, diszjunktív élpárokat. Ez azt jelenti,  egyszerre, akkor mind az (α, β), mind a (β, α) hogyha az α és β muvelet  nem végezheto él eleme a D halmaznak. Továbbá minden α, β ∈ N esetén feltesszük, ha (α, β) ∈ C ∪ D,  ami függetakkor az (α, β) él hossza pα , azaz az α muvelet  elvégzéséhez szükséges ido,  len az él végpontjától, azaz β-tól. Az élek hosszát, azaz a megmunkálási idoket, mindvégig nemnegatívnak tételezzük fel. 9.39 deníció Az A ⊂ D halmazt programnak nevezzük, ha (α, β) ∈ A akkor és csak akkor, ha (β, α) < A. Ha tehát A egy program, akkor a G 0 = (N, C ∪ A) egy szokásos irányított gráf.

Ennek élei  határozzák meg, hogy a muveletek  milyen sorrendben végezhetok. Ha minden muveletet  a   olyan esetben, lehetséges legkorábbi idopontra ütemezünk, azaz nem iktatunk be állásidot  muvelet  amikor mind a gép rendelkezésre áll, mind a sorrend szerint következo  elvégezheto 0 volna, akkor G egyértelmuen  meghatároz egy termelési programot. A diszjunktív gráf modell nyelvén a J ||C max feladat úgy fogalmazható meg, hogy meg0  G gráfban a kritikus út határozandó a G gráfhoz egy A program úgy, hogy az így keletkezo hossza minimális legyen. 0 Kritikus útról természetesen csak akkor lehet beszélni, ha G nem tartalmaz irányított kört. Ezért az alábbiakban mindvégig feltesszük, hogy csak olyan A programokat vizsgá0 lunk, hogy G nem tartalmaz irányított kört.  eltekintve A diszjunktív gráf modell megoldására szolgáló módszerek kevés kivételtol mind a korlátozás és szétválasztás elvén alapulnak. Ehhez

természetesen a kritikus út hosszára vonatkozó alsó korlátra van szükség. Az alábbiakban tárgyaljuk a leggyakoribbakat Amikor az optimális A programot keressük, az élpárok egy-egy tagját külön-külön választjuk ki. Így az algoritmusok során mindig olyan helyzet áll fenn, hogy a C halmazhoz még hozzáválasztunk néhány további élt. Ezt a halmazt fogjuk B-vel jelölni Tehát valamely alkalmas A program mellett mindig igaz a C ⊂ B ⊂ C ∪ A reláció Az (N, B) gráfot H jelöli. Hangsúlyozzuk, hogy H tartalmazza az összes konjunktív élt, bizonyos diszjunktív élpárokból egyet, míg a többi diszjunktív élpárból egyik élt sem. 9.40 deníció Legyen M a muveletek  egy részhalmaza. Azt mondjuk, hogy M diszjunktív, ha bármely α, β ∈ M (α , β) esetén α-t és β-t a H gráfban vagy egy konjunktív élekbol  álló irányított út köti össze, vagy egy diszjunktív élpár. Szükségünk lesz még az alábbi két mesterséges muveletre,

 melyek bevezetése meg muvelet, könnyíti a számításokat: ◦ egy 0 hosszúságú kezdo  ∗ pedig 0 hosszúságú befejezo muvelet.   bármely (N, B) gráfra vonatkozóan, tehát még a (N, C) esetén is a Ezen két muveletr  ol  következoket tesszük fel: (1) A ◦ csúcsba nem vezet él. (2) A ∗ csúcsból nem indul ki él.   és ∗-tól különbözo  muvelet. (3) Legyen α tetszoleges, ◦-tol  Ekkor ◦-ból vezet irányított út α-ba, és α-ból vezet irányított út ∗-ba. 9.6 A többutas ütemezési probléma 399 Továbbá az alábbi jelöléseket alkalmazzuk, amelyek mind a H = (N, B) gráfra vonatkoznak: •  rα az α muvelet  megkezdésének lehetséges legkorábbi idopontja, •  aminek minimálisan el kell telnie az α muvelet qα az az ido,  befejezése után minden muvelet  befejezéséig.  α-ba vezeto  leghosszabb út hossza a H Könnyen látható, hogy rα nem más, mint a ◦-bol  leghosszabb út hossza pα nélkül.

gráfban, míg qα ugyanitt az α csúcsból a ∗ csúcsba vezeto Ezért az rα , qα mennyiségekre a (9.43)–(946) képletekhez hasonlóan az alábbi rekurzív képletek adhatók meg: r◦ = 0 , (9.47) minden α ∈ N {◦} esetén rα = max{rβ + pβ : (β, α) ∈ B} , (9.48) q∗ = 0, (9.49) minden α ∈ N {∗} esetén qα = max{qβ − pβ : (α, β) ∈ B} . (9.50) Ha M a muveletek  egy diszjunktív részhalmaza, és ebben az α és β muvelet  olyan, hogy  álló út vezet α-ból β-ba, akkor az konjunktív élekbol rα ≤ rβ , qα ≥ qβ  egyenlotlenségek automatikusan teljesülnek. Ha a B halmazhoz hozzáveszünk egy addig diszjunktív (α, β) élt, akkor az r és q értékeket azonnal úgy kell módosítani, hogy a Bellmanegyenletek továbbra is igazak maradjanak. 9.41 tétel Bármely A program esetén, amelyre B ⊂ C ∪ A teljesül, a teljes átfutási ido  legalább max{rα + pα + qα : α ∈ N} . (9.51)  α-n keresztül ∗-ba vezeto 

leghosszabb út hossza. Bizonyítás. Az rα + pα + qα összeg a ◦-bol Tehát a képlet a kritikus út hosszát adja meg a H gráfban. Ez a hossz nem csökkenhet, ha további nemnegatív hosszú éleket vezetünk be a gráfba. A 9.36 tételnek az volt a logikája, hogy megvizsgáltuk, hogy milyen gyorsan tud egy nélkül el lehet végezni az általán eljutni valami egy i gépre, ott optimális esetben állásido  összes megmunkálást, majd az utolsó munkadarabnak még be is kell fejezodnie a további  legrövidebbnek feltételezve. Ehhez hasonló módon számos alsó gépeken, ezt is a leheto  korlát nyerheto. 400 9. Ütemezéselmélet (Vizvári Béla) 9.42 tétel A többutas ütemezési feladat átfutási ideje a muveletek  bármely diszjunktív M halmaza esetén legalább min rα α∈ M + X pα + min qα . (9.52) α∈ M α∈ M Bizonyítás. Gyengítsük a feladat feltételeit úgy, hogy az M halmaz kivételével az összes  többi diszjunktív

élpártól eltekintünk. Ekkor is minimálisan el kell annyi idonek telnie, amíg  megkezdodhet,   az M-beli muveletek  közül az elso az összes M-beli muvelet  befejezodik,  megmunkálások is véget érnek. Ezen három tényezore  végül az M-beli muveleteket  követo ad rendre alsó korlátot a (9.52) kifejezés három tagja 9.43 tétel Legyen a muveletek  bármely diszjunktív M halmaza esetén az M-beli muvele teknek egy, a q j értékek szerinti monoton csökkeno  sorrendje [1], [2], . , [| M |] A többutas ütemezési feladat átfutási ideje legalább min rα α∈ M + max{ j X p[i] + q[ j] : j = 1, . , | M |} (9.53) i=1  o  tételnél. Továbbá tegyük fel, Bizonyítás. Gyengítsük ugyanúgy a feltételeket, mint az eloz  hogy minden muvelet  rendelkezésre áll a minα∈ M rα idopontra. Legyen a teljes tevékenység  határideje T . Innen a gyengített feltételek alapján adódik, hogy az M-beli α muvelet végso  határideje T −

qα . Az eredeti feladat teljes átfutási idejére T olyan értéke ad alsó becslést, amely mellett a gyengített feladatban a maximális késés nemnegatív. Nyilvánvalóan ezek  tudjuk, közül az a legjobb T érték, amely mellett a maximális késés éppen 0. A 94 tételbol  határidok  szerinti ütemezés minimalizálja a maximális késést, és hogy a monoton növo  sorrend ilyen. Az adott sorrend szerinti esetünkben a q j értékek szerinti monoton csökkeno  [ j] muvelet  befejezési idopontja min rα α∈ M + j X p[i] . i=1 Mivel a maximális késés 0, ezért innen a j X min rα + max{ p[i] − (T − q[ j] ) : α∈ M j = 1, . , | M |} ≤ 0 i=1   T maximális értékére a (9.53)-beli kifejezés kapható egyenlotlenség adódik. Ebbol 9.44 tétel Legyen a muveletek  egy diszjunktív M halmaza esetén [1], [2], . , [| M |] az M-beli muveleteknek  egy, a rendelkezésre állási idok  szerinti monoton csökkeno  sorrendje. A többutas

ütemezési feladat átfutási ideje legalább min qα α∈ M + max{ j X i=1 p[i] + r[ j] : j = 1, . , | M |} (9.54) 9.6 A többutas ütemezési probléma 401  o  tételt arra az ütemezési feladatra, amelyben a megmunBizonyítás. Alkalmazzuk az eloz  azonosak a vizsgált problémában szereplokkel,   kálási idok míg a rendelkezésre állási idoket  a q j értékek adják meg és r j idonek kell eltelnie a j muvelet  befejezése után a muveletek  teljes befejezéséig. A korlátozás és szétválasztási módszerek gyakran keverednek az implicit leszámlálással, s nem csupán az ütemezési problémák megoldásánál. Az utóbbinak az a lényege, hogy  megoldások egy részét ki akarjuk zárni, anélkül, hogy ténylegesen megvizsa szóba kerülo   gálnánk oket. Itt egy ilyen lehetoséget mutatunk be a 9.42 tételre támaszkodva 9.45 tétel Legyen M muveletek  egy halmaza és α egy további úgy, hogy az M ∪ {α} halmaz diszjunktív.

Legyen továbbá C > 0 egy tetszoleges  szám. Ha rα + X pβ + pα + min qβ ≥ C β∈ M β∈ M (9.55) és min rβ β∈ M + X pβ + pα + min qβ ≥ C , β∈ M β∈ M (9.56) akkor minden olyan ütemezésben, amelynek az átfutási ideje rövidebb, mint C, α az összes M-beli muvelet  mögött áll.   Bizonyítás. A (955) egyenlotlenség baloldala alsó korlát a teljes átfutási idore abban az  esetben, ha α megelozi az összes M-beli muveletet,  azaz ebben az esetben nem lehet az  C-nél rövidebb. Hasonlóképpen a (956) egyenlotlenség  átfutási ido baloldala alsó korlát a   sem teljes átfutási idore abban az esetben, ha α az M-beliek között van, azaz sem nem elso, nem utolsó.  esik szó, ezek összesen (| M | +1)! sorrendet alkothatA tételben | M | +1 muveletr  ol nak. Ha az állítás feltételei teljesülnek, akkor már csak | M |! sorrend kerülhet szóba, azaz a megvizsgálandó esetek számát 1/(| M | + 1)-ed részére

redukáltuk. Ez az oka annak, hogy  az ilyen teszteket akkor is érdemes igen gyakran ellenorizni, ha számos esetben nem adnak pozitív eredményt. A korlátozás és szétválasztás eljárásában a részhalmazok felbontásának számos módszere ismert. Ezek közül a legegyszerubb  az, amikor egy halmazt egy még nem vizsgált  diszjunktív élpárnak megfeleloen bontanak két részhalmazra. Egy nomabb eljárás az ún  kritikus blokkon alapul. Tegyük fel, hogy már ismert egy ütemezés C átfutási idovel Tekintsünk a pillanatnyi, esetleg még teljes ütemezést nem adó megoldásban egy olyan α muveletet,  ha ilyen egyáltalán van, amelyre rα + pα + qα ≥ C (9.57) teljesül. Ha van ilyen muvelet,  akkor egyetlen olyan teljes ütemezés sem adhat jobbat a már ismert megoldásnál, mely teljes ütemezés a jelenlegi megoldásból keletkezik kiegészítéssel. 402 9. Ütemezéselmélet (Vizvári Béla) Ez a helyzet például éppen akkor, amikor egy minden

korábbinál jobb ütemezést találtunk,  a pillanattól kezdve ennél jobbat keresünk, és a (9.57) feltétel legalább egy hiszen ettol  α-ba muveletre  teljesül. Legyen α egy olyan muvelet,  amire (9.57) igaz, de egyetlen ◦-bol  útba eso  muveletre   α-ba vezeto  útba vezeto  sem áll fenn a fenti egyenlotlenség. A ◦-bol  muveletek eso  alkotják az ú.n kritikus blokkot Nyilvánvalóan csak akkor tudunk a már is mertnél jobb ütemezést találni, ha sikerül α-t a kritikus blokkon belül elobbre ütemeznünk.  Tehát minden, a késobbiekben felbontandó halmaznak elég csak azokat a részhalmazait te elemek ezt a követelményt teljesítik. Itt persze adott esetben számos kinteni, amelyekbe eso  lehetoség merülhet fel, melyek kezelésének részleteibe nem megyünk bele. Ha a (957) feltétel semmilyen α mellett sem teljesül, akkor a felbontásra a fent említett egyszeru  szabály alkalmazható. 9.8 példa Tekintsük azt a – négy munkát és

három gépet tartalmazó – feladatot, melyet az alábbi  szám a gép indexe, a második a muvelet adatok határoznak meg. A táblázat belsejében az elso  elvég zéséhez szükséges ido. munka 1. muvelet  2. muvelet  3. muvelet  4. muvelet  5. muvelet  1. 1/2 2/1 3/2 1/4 2/3 2. 2/1 3/3 2/4 3. 1/3 3/2 2/2 1/3 2/4 4. 1/2 2/3 3/4 1/1 3/1  jegy a munka indexe, a második jegy A muveleteket  kétjegyu  indexekkel azonosítjuk, az elso  van szó. Ha még egyetlen pedig azt mutatja meg, hogy adott munkához tartozó hányadik muveletr  ol  r és q értékek a következok:  muveletet  sem ütemeztünk, vagyis az A halmaz üres, akkor a megfelelo r11 = 0 r12 = 2 r13 = 3 r21 = 0 r22 = 1 r23 = 4 r14 = 5 r15 = 9 r31 = 0 r32 = 3 r41 = 0 r42 = 2 r33 = 5 r34 = 7 r35 = 10 r43 = 5 r44 = 9 q11 = 10 r45 = 10 q12 = 9 q13 = 7 q14 = 3 q15 = 0 q23 = 0 q21 = 7 q22 = 4 q31 = 11 q32 = 9 q33 = 7 q34 = 4 q35 = 0 q41 = 9 q42 = 6

q43 = 2 q44 = 1 q45 = 0  muveletek Tekintsük a második gépet. Az ezen végzendo  12, 15, 21, 23, 33, 35, 42. Így a fenti  becsléseket kapjuk. Mivel most minden muvelet tételek alapján a következo  esetén az rα + pα + qα  összege, ezért a 9.41 tétel alapján érték nem más, mint az adott munkához tartozó megmunkálási idok mind a 33, mind a 35 muveletre  a 14 értéket kapjuk. Lévén r21 = q35 = 0, ezért a 942 tétel alapján a  muveletek második gépen végzendo  összidejét kapjuk, ami 18. Ugyanezt az értéket adja a 943 tétel  szerinti csökkeno  sorrend nem egyértelmu, is. A rendelkezésre állási idok  a két lehetséges sorrend 35, 15, 33, 23, 12, 42, 21 és 35, 15, 33, 23, 42, 12, 21. Innen a 944 tétel alapján a 19 alsó korlát adódik, nem tekintve ugyanis a 21 muveletet,  kapjuk, hogy q35 + p35 + p15 + p33 + p23 + p12 + p42 + r42 = 19 . Ez azt sugallja, hogy a második gépen a muveleteket  21, 42, 12, 23, 33, 15, 35 sorrendben

kell végezni, és valóban, ez ugyanis az alábbi ütemezéshez vezet, ahol t j a muvelet  kezdési, c j pedig a  befejezési idopontja. 9.6 A többutas ütemezési probléma 41 1. gép 0 1 11 2 3 21 2. gép 0 31 4 5 42 1 2 3 6 0 1 2 12 4 3 14 7 5 8 6 7 8 13 4 5 9 34 6 7 8 44 10 11 12 13 14 15 16 17 18 19 20 23 22 3. gép 403 33 15 35 9 10 11 12 13 14 15 16 17 18 19 20 32 43 9 10 11 12 13 14 15 16 17 18 19 20 45 9.8 ábra Egy optimális ütemezés 11 12 13 14 15 21 22 23 31 32 33 34 35 41 42 43 44 45 tj 2 5 6 8 12 0 2 cj 4 6 8 12 15 1 5 10 6 5 8 10 12 15 0 2 13 17 18 8 10 12 15 19 2 5 17 18 19 Az ütemezés Gantt-diagramja a 9.8 ábrán látható 9.63 Egészérték¶ programozási modellek  elterjedt modell a J || f feladatra vonatkozik azon egyszerusít  feltételezés mellett, Az elso  o hogy minden munka legfeljebb egyszer kerül egy gépre. A képletekben az alábbi indexeket és állandókat

használjuk: • i, j: a munkák indexei, • n: munkák száma, •  muveletek mi : az i munkán végzendo  száma, • k, l: a muveletek  indexei, • g: a gép indexe, • di : az i munka határideje, •  muveletének pig : az i munka g gépen végzendo  megmunkálási ideje, • gik : az a gép, amelyen az i munka k muveletét  végezni kell, • M: egy nagy szám, például Pn Pm i=1 i k =1 pigik . A feladat változói pedig ( 1,  ha az i munka megelozi a j munkát a g gépen, 0 különben; • xi jg = •  muveletének  tig – az i-edik munka g gépen végzendo  kezdeti idopontja.  azt biztosítja, hogy ugyanannak a munkáKét feltételcsoportot kell felírnunk. Az elso  nak a muveletei  a meghatározott sorrendben kövessék egymást, és idoben ne legyen átfedés  munkák ugyanazon a gépen végzendo  muveleközöttük, míg a második csoport különbözo  tei közti átfedést akadályozza meg. 404 9. Ütemezéselmélet

(Vizvári Béla)  esetben egyszeruen Az elso  csak azt kell biztosítani, hogy az i munka k és k + 1 muve  elteljen, azaz a letének megkezdése között legalább pigik ido tigik + pigik ≤ tigi,k+1 , i = 1, . , n, k = 1, , mi − 1 (9.58)  egyenlotlenségek teljesülését kell megkövetelni. Tegyük fel, hogy g = gik = g jl , azaz az i munka k és a j munka l muveletét  azonos gépen kell végezni. Ekkor a t jg − tig ≥ pig , tig − t jg ≥ p jg (9.59)   azt fejezi ki, hogy a g gépen i megegyenlotlenségek közül egynek teljesülnie kell. Az elso  elozi a j munkát, azaz xi jg = 1. Ennek felhasználásával a M xi jg + tig − t jg ≥ p jg , (9.60) M(1 − xi jg ) + t jg − tig ≥ pig (9.61)   automatikusan teljesül, míg a második egyenlotlenségek adódnak. Ha xi jg = 1, akkor az elso  idovel   kikényszeríti, hogy a j munka megfelelo késobb kerüljön a g gépre, mint i, és ha xi jg = 0, akkor éppen fordítva. A változókra

természetes módon adódnak a minden i, j, g esetén 0 ≤ tig ≤ M, xi jg ∈ {0, 1} (9.62) megszorítások. További feltételekre lehet szükség a célfüggvény kezelésére, illetve akkor,  is vannak. Az utóbbi esetben azt kell megkövetelni, hogy az egyes ha a munkákra határidok    munkák utolsó muvelete  a határidonél ne késobb fejezodjék be, azaz tigim i A célfüggvények közül P + pig imi ≤ di , w j C j és így i = 1, . , n P (9.63) w j L j írható fel a legkönnyebben, hiszen az  elobbi n X wi (tigim i + pig ) = im n X wi tigim i i i=1 i=1 + n X wi pigim i . i=1 Az utóbbi tag állandó, így el is hagyható. Egy új változóra, legyen ez C, és n további feltételre van szükség C max kezeléséhez. Az új feltételek C ≥ tigim i + pig imi i = 1, . , n  alakja pedig A célfüggvény megfelelo min C .  el Lmax is, csak ott C i értéke helyett Li értékére kell az egyenlot Hasonlóképpen intézheto

lenségeket megkövetelni. Vegyük számba a modell változóit és feltételeit. Mint láttuk, xi jg és x jig közül elég csak az egyiket bevezetni, így ezek maximális száma n(n − 1)m/2. Mivel minden munka csak 9.6 A többutas ütemezési probléma 405 egyszer kerülhet egy gépre, ezért a tig változók száma legfeljebb nm, összesen pontosan Pn i=1 mi . A (958) feltételek száma munkánként mi − 1, azaz összesen A (9.60)–(961) feltételeké pedig legfeljebb n(n − 1)m Pn i=1 (mi − 1) ≤ nm − n.  másik modell általánosabb, és tekintettel tud lenni különbözo  eroforrá A következo sokra is. Ez a modell egy ún oszlopgeneráló eljárás alapja Matematikai programozásban akkor neveznek így egy módszert, ha az egy olyan modellen (feladaton) alapszik, aminek explicit felírása nem lehetséges, mert az legalább egyenértéku  volna a feladat megoldásával, de a modell, illetve annak matematikai tulajdonságai  lehetové teszik, hogy

egyre újabb oszlopokat, azaz változókat (a hozzájuk tartozó együtthatókkal együtt), vezessünk be a lineáris feltételeket tartalmazó modell megoldása során,  soron a feladatot annak és teszteljük a mindenkori részmegoldás optimalitását. Így végso explicit felírása nélkül tudjuk megoldani. P A modell a J | res | f j feladatra vonatkozik, azzal a további könnyítéssel, hogy nem  követeli meg, hogy az egyes munkákhoz tartozó muveletekre  egyértelmuen  eloírt sorrend  legyen, hanem megengedi, hogy a szükséges megelozési feltételeket munkánként különkülön egy háló írja le. Viszont feltesszük, hogy minden j esetén az f j célfüggvény reguláris, továbbá, hogy a  egészek. megmunkálási idok Legyen a j munka muveleteinek  halmaza O j . A j munka ütemezésének nevezzük a tα számokat, ha minden α, β ∈ O j esetén tα + pα ≤ tβ teljesül, feltéve, hogy az α muveletnek   meg kell eloznie a β muveletet.  Itt tα

egyben azt is jelenti, hogy minden α muvelet  esetén  a muveletet  a [tα , tα + pα ] idointervallumban végzik el. Egy további megszorítás, hogy fel tesszük, hogy a feladat véges T idokorláton belül megoldható. Az adatok egész voltából  a tα számok egész volta is. Végül azt a következtetést kapjuk, következik, hogy felteheto hogy csak véges sok ütemezés van, ami közül választanunk kell. Ezt a számot a j munka esetén w j jelöli.    erofor Az eroforrásokra vonatkozó feltételezések a következok. A gyelembe veendo rások száma s. Minden α muvelet  az elvégzése során állandó intenzitással használja va lamennyi eroforrást, ide értve azt az esetet is, amikor a muvelet  elvégzéséhez nem kell  valamely eroforrás. Ezt a mennyiséget, vagyis azt, hogy az α muvelet  mennyit igényel a k  eroforrásból, bαk jelöli. Ilyen módon bármely j munka és annak h ütemezése esetén meg  mondható, hogy a k eroforrásból a t

idopontban az adott munkának mekkora mennyiségre    mennyiség ekt . van szüksége, amit a jhkt jelöl. A k eroforrásból a t idopontban elérheto Hasonlóképpen bármely j munka és h ütemezés esetén egyértelmuen  meghatározott a  költség, ami f jh . j munka során felmerülo Az alapfeladatban a költségeket akarjuk minimalizálni úgy, hogy semmikor sem lépjük  túl az eroforrások szabta korlátokat és minden munkára pontosan egy ütemezést választunk ki. Így a fenti jelölésekkel az alábbi feladathoz jutunk: w n X X j f jh x jh min (9.64) j=1 h=1 w n X X j j=1 h=1 a jhkt x jh ≤ ekt , k = 1, . , s, t = 0, , T , (9.65) 406 9. Ütemezéselmélet (Vizvári Béla) w X j x jh = 1 j = 1, . , n , (9.66) j = 1, . , n, h = 1, , w j (9.67) h=1 x jh ∈ {0, 1}, Tehát x jh az a döntési változó, ami akkor és csak akkor 1, ha a j munka h ütemezését   feltételeket. használjuk, különben 0. Itt a (965) egyenlotlenségek

jelentik az ú.n összeköto Ha ezek nem volnának, akkor a feladat igen egyszeru  lenne, ugyanis minden munkára a legkisebb költségu  ütemezést kellene választani.  λkt számok tetszoleges rögzített, nemnegatív mennyiségek (k = 1, . , s; t = 0, , T ) Könnyen látható, hogy ekkor a (964)–(967) feladat célfüggvényéLegyenek a nek értékét minden megengedett megoldás esetén alulról becsüli az alábbi, ú.n Lagrangefeladat célfüggvényének értéke a változók ugyanazon értéke mellett w n X X j min w s X T X n X X j f jh x jh + j=1 h=1 k=1 t=0 w X a jhkt x jh λkt − j=1 h=1 s X T X ekt λkt , (9.68) k=1 t=0 j x jh = 1, j = 1, . , n ; (9.69) j = 1, . , n h = 1, , w j (9.70) h=1 x jh ∈ {0, 1}  tagban az összegzés sorrendjét megváltoztatva a célfüggvény az alábbi alakra A középso hozható   w s X T s X T n X X X X    f jh + ekt λkt . a jhkt λkt  min  x jh − j

j=1 h=1 (9.71) k=1 t=0 k=1 t=0  szintjét jelentik, amelyben csak közvetve, az a jhkt száA fentiek csak a modell felso  mokon keresztül, jelennek meg a muveletek  ütemezései és eroforrás-felhasználásai. Az eddig mondottakat ütemezések megkonstruálására akarjuk felhasználni. Ezt a célt szolgálja a célfüggvény (9.71) formája is Itt ugyanis jól látható egy munka ütemezésének hatása a Lagrange-feladat célfüggvényére. A továbbiakban ezt a tagot akarjuk becsülni Az α tevé kenységhez szükséges eroforrások felhasználása a fenti jelölések mellett uα (tα ) = X s X tα + pα −1 bαk k=1 λkt t = tα értékkel járul hozzá az adott ütemezésnek a célfüggvénybeli együtthatójához, vagyis a s X T X k =1 t =0 a jhkt λkt 9.6 A többutas ütemezési probléma 407 ˆ összeghez. Tegyük fel, hogy a j munkából már ütemeztük az O j ⊂ O j tevékenységeket.  o  modell jelöléseit használva az éppen

konstruálandó h ütemezés együtthatója Ekkor az eloz legalább ˆ }+ max{ f j (tα + pα + qα ) : α ∈ O j X uα (tα ) α∈Oˆ j lesz. A további részleteket elhagyjuk. Az eljárás lényege, amit a fentiekben igyekeztünk demonstrálni, az, hogy ilyen módon az ütemezések konstrukciója során mindvégig becsülni  tudjuk a célfüggvény értékét alulról, és így ki lehet szurni  a nem elegendoen jó ütemezéseket.  feladatok mérete állandóan nöA felsorolt adatokból is látható, hogy bár a kezelheto  hogy a vekszik, azonban számos gyakorlati probléma mérete jóval nagyobb, így értheto,  heurisztikus módszereknek nagy jelentoségük van.  azonban ezekre rátérnénk, a pontos eredmények közül utolsónak Jackson észMielott revételét adjuk közre, amelyben kiterjesztette Johnson módszerét a kétgépes, többutas probléma megoldására. 9.46 tétel Legyen a J2 | m j ≤ 2 | C max feladat esetén • • • J1 azon munkák halmaza,

amelyeket csak az elso  gépen kell megmunkálni, J2 azon munkák halmaza, amelyeket csak a második gépen kell megmunkálni, J12 azon munkák halmaza, amelyeket eloször  az elso  gépen, utána a második gépen kell megmunkálni, • J21 azon munkák halmaza, amelyeket eloször  a második gépen, utána az elso  gépen kell megmunkálni. Ekkor a feladat egy optimális ütemezése a következo:  • az elso  gépen eloször  a J12 -beli munkák itteni muveleteit  végezzük el a Johnsonalgoritmus szerinti sorrendben, utána a J1 -beli muveleteket  tetszoleges  sorrendben, végül a J21 -beli munkák itteni muveleteit  ugyancsak a Johnson-algoritmus szerinti sorrendben. • a második gépen eloször  a J21 -beli munkák itteni muveleteit  végezzük el a Johnson algoritmus szerinti sorrendben, utána a J2 -beli muveleteket  tetszoleges  sorrendben, végül a J12 -beli munkák itteni muveleteit  ugyancsak a Johnson-algoritmus szerinti sorrendben. Megjegyzés.

Johnson algoritmusát külön-külön alkalmazzuk a J12 - és J21 -beli mun- kákra. Azt szokás mondani, hogy a J1 - és J2 -beli munkák esetén csak egy muvelet  van. Nem jelent megszorítást azonban, ha akárhány muveletet  is megengedünk, mint azt látni fogjuk. Annyi azonnal látható, hogy akárhány muveletet  is kelljen elvégezni egy munkán,  egyetlen menetben, hiszen mihelyst véget ért egy muvelet, ezek megtehetok  a munkadarab  ugyanarra a gépre. azonnal felteheto  gépen a muveletek Bizonyítás. Tegyük fel, hogy az elso  sorrendje nem azonos az állításbelivel. Ha két szomszédos muvelet  közül •  J1 -beli, a második J12 -beli, akkor ezek felcserélése nem változtatja meg az álláaz elso  az elso  gépen és nem növeli a második gépen, sidot 408 9. Ütemezéselmélet (Vizvári Béla) 41 1. gép 0 1 11 2 3 21 2. gép 0 31 4 5 42 1 2 3 6 0 1 2 4 3 7 12 5 8 6 7 8 13 4 5 9 23 22 3. gép 14 6 7 8 34

44 10 11 12 13 14 15 16 17 18 19 20 33 15 35 9 10 11 12 13 14 15 16 17 18 19 20 32 43 9 10 11 12 13 14 15 16 17 18 19 20 45 9.9 ábra Egy optimális megoldás, mely aktív ütemezés •  J21 -beli, a második J12 -beli, akkor ezek felcserélése nem növeli az állásidot  az elso egyik gépen sem, •  J12 -beli, de nem a Johnson algoritmus szerinti sorrendben vannak, akkor mindketto  az elso  gépen és nem növeli a másoezek felcserélése nem változtatja meg az állásidot dik gépen.  sorrend az elso  gépen semmilyen más sorrendnél sem rosszabb. Tehát az állításban szereplo  szükség esetén a második gépen is. Hasonló átrendezések végezhetok 9.64 Heurisztikus módszerek A továbbiakban rátérünk a heurisztikus módszerek tárgyalására.  fogalmak Mindvégig feltesszük, hogy a célfüggvény reguláris. Az alább bevezetendo   megoldások leírására szolgálnak. ilyenekhez eloállítandó közelíto 9.47 deníció Egy

ütemezést aktívnak nevezünk, ha egyetlen muveletet  sem lehet idoben  elobbre  tolni anélkül, hogy valamely más muvelet  ütemezését hátrébb kellene csúsztatni. 9.9 példa A 98 példában megadott optimális ütemezés nem aktív, mert a 22 muveletet  már t = 1-ben    meg lehet kezdeni. Hasonlóképpen 43 elobbre hozható a 10 idopontig és ezáltal 44 és 45 is elobbre  már (t csúsztatható két egységgel. Végül a 31 muvelet  is megkezdheto = 4)-ben. Így a ?? ábrán látható ütemezéshez jutunk. Reguláris célfüggvény esetén mindig van aktív optimális megoldás, mert egy kezdési    idopont elobbre hozása egy másik kezdési idopont növelése nélkül nem növelheti a cél függvény értékét. Az aktív ütemezések úgy is felfoghatók, hogy eloször meghatározzuk a   legkomuveletek  sorrendjét a gépeken, aztán minden muvelet  kezdési idopontját a leheto  rábbinak választjuk úgy, hogy a gépeken eloírt sorrend ne

sérüljön meg.  Az aktív ütemezések egy fontos alosztálya a következo: 9.48 deníció Egy ütemezés állásido  nélküli, ha minden gép dolgozik, ha egyáltalán van elvégezheto  muvelet.  9.6 A többutas ütemezési probléma 409  o  példában szereplo  módosított optimális megoldás nem állásido  nélküli, mert a 9.10 példa Az eloz  43 muvelet  már t = 5-ben rendelkezésre áll. Nem elonyös azonban ekkor megkezdeni, mert akkor  soron megnövelnénk a teljes átfutási idot.  mind a 13, mind a 32 muveletet  kitolnánk, és így végso  nélküli ütemezés nem ad mindig optimális megoldást. A példa mutatja, hogy az állásido Az irodalom mégis nagy gyelmet szentel neki, mint természetes heurisztikának, amely  megoldásokat ad. különösen nagyméretu  feladatoknál jó közelíto  nélküli ütemezések eloállítása  Az állásido általában egy ú.n prioritási szabályon alapszik Ilyeneket láttunk egyetlen gép és

párhuzamos berendezések esetében, az utóbbinál lista szerinti ütemezés volt a neve. A leggyakrabban alkalmazott szabályok • az SPT sorrend, • az LPT sorrend, • a legkevesebb megmaradt megmunkálás (LWR), ahol munkánként megvizsgálják a  megmunkálások összidejét, és annak a munkának a soron következo  még hátralévo  a legrövidebb, megmunkálását választják, ahol az összido •  onek  a leghosszabb megmaradt megmunkálás (rövidítve MWR) az eloz a fordítottja, •  muveletek a hátralévo  maximális száma (MOPRNR), • a FIFO sorrend, • az EDD sorrend.  az elso  ketto  általánosításának tekintheto.  Általában az a helyzet, hogy A második ketto  ha van egy szabály, akkor annak az ellenkezojét is használják bizonyos esetekben. Például  az említett FIFO sorrend mellett elofordul a LIFO sorrend alkalmazása is. Egy prioritási szabályon alapuló mohó elindítási módszer az alábbi két követelményt

teljesíti: 1. Ha egy munkadarab megérkezik egy éppen nem dolgozó gép elé, akkor a gép azonnal megkezdi a megmunkálását. 2. Ha egy megmunkálás véget ér, akkor a munkadarab azonnal megérkezik a technológiai  gép elé. A most felszabaduló gép pedig az elotte  útvonalban soron következo várakozó  muveletét munkadarabok közül a prioritási szabály alapján kiválasztott megfelelo  kezdi meg azonnal. 9.11 példa Nézzük meg, hogy mit ad a mohó módszer az MWR prioritási szabály alapján a 98  példa feladatára. A prioritási szabályhoz felhasználandó értékek muveletenként  a következok: pr11 = 12 pr12 = 10 pr13 = 9 pr21 = 8 pr22 = 7 pr23 = 4 pr14 = 7 pr15 = 3 pr31 = 14 pr32 = 11 pr41 = 11 pr42 = 9 pr33 = 9 pr34 = 7 pr35 = 4 pr43 = 6 pr44 = 2 pr45 = 1 Az ütemezés elkészítését az alábbi táblázat foglalja össze. Ha ebben a munkák alatt egyetlen szám található, akkor a munka éppen azon a gépen van. Ha pedig

például 1v12 áll egy munka oszlopában,  gép elott  vár 12 prioritási értékkel. akkor ez azt jelenti, hogy a munka az elso 410 9. Ütemezéselmélet (Vizvári Béla)  ido 1. munka 2. munka 3. munka 4. munka 1. gép 2. gép 1. 1v12 2 1 1v11 31 21 – 2. 1v12 3 1 1v11 31 – 22 3. gép 3. 1 3 3v11 1v11 11 – 22 4. 1 2 3 1v11 11 23 32 5. 2v10 2 3 1 41 23 32 6. 2v10 2 2v9 1 41 23 – 7. 2v10 2 2v9 2v9 – 23 – 8. 2 – 2v9 2v9 – 33 13 9. 3 – 2 2v9 – 33 13 10. 3 – 2 2v9 – 33 13 11. 1 – 1v7 2 14 42 – 12. 1 – 1v7 2 14 42 – 13. 1 – 1v7 2 14 42 – 14. 1 – 1v7 3 14 – 43 15. 2 – 1 3 34 15 43 16. 2 – 1 3 34 15 43 17. 2 – 1 3 34 15 43 18. – – 2 1 44 35 – 19. – – 2 3 – 35 45 20. – – 2 – – 35 – 21. – – 2 – – 35 –  minimalizálása, akkor ez az eredmény nem olyan jó, mint az

optimális Ha a cél a teljes átfutási ido megoldásé, de értéke közel van hozzá. Érdemes összehasonlítani a pontos módszereket a fenti heurisztikus módszerekkel. A  rendszerre, ide értve most a termékeket is, vonatkozó pontos módszerek az egész termelo  modellt felállítani. teljes információt követelnek meg, hiszen csak így lehet a megfelelo  hiszen mindig csak akkor Ezzel szemben a mohó módszer valós ideju  eljárásnak tekintheto, dönt, azaz választ ki egy muveletet,  ha erre szükség van. Ehhez nem használ mást, mint a rendszer pillanatnyi állapotának ismeretét. Tehát teljesen gyelmen kívül hagyja azokat a muveleteket,  amelyek az adott pillanat el, függetlenül attól, hogy ennek mi az oka, azaz, hogy a megeloz  o  ban nem végezhetok  muveletek  még nem fejezodtek be, vagy a munkadarab még meg sem érkezett a rendszerbe,  és függetlenül attól is, hogy ezek késobbi megjelenése milyen hatást okoz. Ennek megvan  az az

elonye, hogy azonnal reagálni képesek váratlan eseményekre. Például egy munkada további muveletek rab meghibásodása esetén az ezen végzendo  egyszeruen  nem jelennek  meg, és így nincs szükség az elore elkészített sorrendek átdolgozására. Ez a módszer tulajdonképpen nem más, mint a rendszer muködésének  szimulációja, ahol az egyes gépek irányítását a muveletek  szintjén egy nagyon egyszeru  szabály határozza meg.  hogy egy prioritási szabály bizonyos célokat A mohó módszer hátrányaként említheto, jól szolgál, ugyanakkor nagyon rossz eredményeket adhat más vonatkozásban. Egy tipikus  minél alacsonyabb értéken példa erre, hogy az SPT szabály kiváló az átlagos átfutási ido  súlyos megsértéséhez vezet. való tartására, ugyanakkor számos esetben a határidok  nehézA többutas probléma kezelésének fenti két megközelítésében külön-külön rejlo  szinten a többségek leküzdésének egy természetes

módja a kétszintes modell, ahol a felso 9. fejezet feladatai 411 utas probléma egy diszkrét programozási modellje található. Elképzeléseik szerint ezt a  szinten dönproblémát csak ritkán, például naponta vagy hetente oldják meg. Az alatta lévo  várakozó muveletek tik el gépenként, hogy a gép elott  sorából éppen melyiket végezzék el.  szint eredményei alapján számolnak költségeket minden muvelet A felso  minden (diszkrét)  idopontban való megkezdésére. Ezek a költségek fejezik ki az alsó szinten az egyes muve  muveletnek letek fontosságát, azaz súlyát. Az éppen elvégzendo  valamely prioritási szabály  elemét választják. A költségeket pedig ezen feladat optimális Lagrange-szorzói szerint elso alapján számítják. Gyakorlatok 9.6-1 Mi a 945 tétel párja, ami arra ad feltételt, hogy az α muveletnek  az M-beli muvele  kell állnia? tek elott 9.6-2 Írjuk fel a Pm||C max feladat diszjunktív gráf modelljét

Feladatok 9-1. SPT optimalitása Bizonyítsuk be, hogy az SPT sorrend optimális megoldása az 1 || P L j feladatnak. 9-2. Késésmentes optimális megoldás Bizonyítsuk be, hogy ha az 1 | d j | P C j feladatnak van olyan optimális megoldása, amiben nincs késés, akkor ezen megoldásban az α megmunkálás akkor és csak akkor állhat az utolsó helyen, ha dα ≥ Pn 1 p j és minden i : di ≥ Pn 1 p j esetén pα ≥ pi . 9-3. Minimális késés maximalizálása Legyen egy 1 | d j | f feladat esetén [1], [2], . , [n] olyan sorrend, amelyre teljesül, hogy d[1] − p[1] ≤ d[2] − p[2] ≤ · · · ≤ d[n] − p[n] . Bizonyítsuk be, hogy ez a sorrend maximalizálja a minimális késést. (Útmutatás Vegyük  használata nem megengedett. Alkalmazzuk a szokásos észre, hogy betervezett állásido felcseréléses” módszert.) ” 9-4. Legjobb és legrosszabb lista Tegyük fel, hogy m azonos gépünk van, amelyeken 2m − 1 megmunkálást kell elvégezni. A 

közül egy értéke m, további m − 1 értéke m − 1 és még további m − 1 megmunkálási idok értéke 1. Adjuk meg a legjobb és a legrosszabb értéket adó listát 9-5. LPT-korlát élessége  2m − 1, 2m − 1, 2m − 2, 2m − Bizonyítsuk be, hogy ha m gép van és a megmunkálási idok  2, . , m + 1, m + 1, m, m, m, akkor tetszoleges m esetén az LPT ütemezés pontossága a 9.23  korláttal egyezik meg. tételben megadott felso 9-6. Azonos párhuzamos gépek  Általánosítsuk a 9.4-2 gyakorlat eredményét két gép és tetszoleges m mellett a 2m − 1, 2m −  esetére. 1, 2m − 2, 2m − 2, . , m + 1, m + 1, m, m, m megmunkálási idok 9-7. Egyutas ütemezési feladat Oldjuk meg az alábbi egyutas ütemezési feladatot. Ábrázoljuk az optimális megoldást Gantt-diagrammal. 412 9. Ütemezéselmélet (Vizvári Béla) munka 1. gép 2. gép 1. 3 22 3. gép 2 2. 22 20 20 3. 20 14 18 9-8. Kétgépes feladat Bizonyítsuk be, hogy ha az F3

|| C max probléma esetén a min t1 j > max t2 j min t3 j > max t2 j j j és a j j feltételek legalább egyike teljesül, akkor a feladat optimális megoldása ugyanaz, mint azé a  munkánként kétgépes feladaté, ahol a megmunkálási idok t1 j + t2 j , t1 j + t2 j . Útmutatás. Alkalmazzuk a 934 tétel bizonyításának módszerét 9-9. Többutas ütemezés Tekintsük a többutas ütemezési feladatot. Bizonyítsuk be, hogy ha M páronként diszjunktív  muveletek  egy tetszoleges halmaza és α egy további muvelet,  mely diszjunktív valamennyi  M-belivel, végül C > 0 egy tetszoleges szám, akkor min rβ β∈ M + X pβ + pα + qα ≥ C β∈ M esetén α egyetlen olyan ütemezésben sem követheti valamennyi M-beli muveletet,  amely kevesebb, mint C. ben a teljes átfutási ido 9-10. Diszjunkt gráf modell Tegyük fel, hogy egy, a diszjunktív gráf modellen alapuló eljárás során a konjunktív élek pillanatnyi halmaza B. Tekintsünk

egy diszjunktív {(α, β), (β, α)} élpárt, amelyiknek egyik  feltételt arra, hogy az élpár egyik tagjának tagja sincs B-ben. Adjunk egyszeru  elegendo hozzá vétele se hozzon létre kört a gráfban. 9-11. Többutas probléma célfüggvényei A többutas probléma (9.58)–(962) modellje esetén írjuk fel a szükséges feltételek és változók bevezetésével a P w j T j és a P w j U j célfüggvényeket. Megjegyzések a fejezethez Az ütemezési algoritmusok tulajdonságainak jó összefoglalója Bruckner [5] 2002-ben megjelent monográája.  [19] és Lawlertol  [29] Az ütemezési feladatok tömör leírásának rendszere Grahamtol származik. A Gantt-diagramok használatát Henry Laurence Gantt javasolta 1903-ban. Az 1 | r j , d j | Lmax feladat esetében már nem ilyen egyszeru  a helyzet, mert a probléma 9. fejezet megjegyzései 413 teljes általánosságában NP-teljes.A 95 tétel forrása [22, 42] Az SPT sorrend fogalmát Schmidt [43] vezette be. A

9.7 tétel alapjául szolgáló algoritmus megtalálható Lawler cikkében [28] Az 9.15 és 916 tételek a témakör legkorábbi eredményeihez tartoznak és McNaughton cikkében [32] találhatók meg. Az 9.18 tétel bizonyítása Horntól [21] származik  o  elemzés, valamint a 9.27 tétel forrása Coffman, A 9.24 tétel, a 925 tételt megeloz  korlátot Friesen [13] 1.20-ra javíGarey és Johnson cikke [9] A 927 tételben szereplo totta. A módszert magát Friesen és Langston [14] nomították Ennek a változatnak az −k ismert hibakorlátja már 72/61 + 2 . Bár a szükséges muveletek  számának nagyságrendje nem változott, az a konstans, amit a nagy ordó tartalmaz, igen nagy. A további munkák közül megemlítjük még Sahni cikkét [39], ahol a korlát 1 + 1/k, de a muveletek  száma 2 O(n(n k) m−1 ). Igaz továbbá, hogy minden m esetén rm > 1 (lásd a 9-7 feladatot) A P | pmtn, d j  | Umax feladatra, vagyis ahol csak a határidoket betartó,

megengedett ütemezés megtalálása a feladat, ha ilyen létezik, illetve annak kimutatása, ha nem létezik,  (ha Sahni [40] javasolt O(n log nm) futási ideju  algoritmust, amely olyan megoldást állít elo van megoldás), amelyben legfeljebb n − 2 megmunkálást kell megszakítani. Az U max célfüggvényre vonatkozó, a 9.19 tételhez hasonló állítás Hujter Mihálytól [22] származik.  dinamikus programozással elért ütemezési eredmény Rothkopf [36] nevéhez Az elso,   fuz  odik. Lawler és társai [29] késobb egyszerusítették  a Rothkopf által használt képleteket. ∗  eredményt – a 9.22 tételt – Graham bizonyította A C(L)/C hányadosra vonatkozó elso  származik a 9.23 tétel 1966-ban [17]. Ugyancsak Grahamtol A ládapakolási algoritmusokra vonatkozó eredmények összefoglalása megtalálható Coffman, Csirik János és Woeginger [10] cikkében. A korlátozás és szétválasztás részletes leírása megtalálható Vizvári Béla

jegyzetében [47]. Az egyutas ütemezési problémával részletesen foglalkoznak a [20, 27, 31, 46, 44, 45] dolgozatok. Az egyutas problémának a (9.42) képlethez kapcsolódó változatát Piehler [33] tanulmányozta  A diszjunktív gráf modell eloször a [38] dolgozatban jelent meg. A (9.47)–(950) képletek közvetlenül adódnak [47] 5 fejezete alapján Az irodalomban ismert alsó korlátok egy nagyon jó összefoglalását adja [26]. A (952) korlátot gyengébb formában, a harmadik tag nélkül közli [7] és [41]. Maga a korlát éle a 94 tétel alapján A (953) korlát eloször   míg (9.54) sítheto a [23] cikkben fordult elo, megfordítása [4]-ben. A 9.45 tétel alapja [6] A kritikus blokk fogalmát Grabowski [16] vezette be. A kritikus blokkal kapcsolatos további részletek találhatók a [2] dolgozatban.  modellje [30] alapján terjedt el a szakirodalomban. Az egészértéku  programozás elso A másik tárgyalt modell több vonatkozásban általánosabb, és

tekintettel tud lenni külön eroforrásokra  bözo is [11, 12]. Ebben a fejezetben csak a modellt tárgyaljuk – a Fisher által javasolt módszer részletesen megtalálható a [47] könyvben.  származik. A (9.64)–(967) feladat célfüggvényének elemzése [47] 7 fejezetébol Az általános egészértéku  programozási feladatra vonatkozóan eddig említett módszerek csak szerény méretu  feladatokat képesek egzaktul megoldani. [1] még nem számol be 414 9. Ütemezéselmélet (Vizvári Béla)  [11] esetében a legnagyobb vizsgált problémában a munszámítástechnikai eredményekrol.  kák száma 5, az eroforrásoké 4. [26] mindössze három feladatot oldott meg, melyek közül a legnagyobb esetén a muveletek  száma 36 és mind a munkák, mind a gépek száma 6. [2] már tovább növelte a méretet, a pontosan megoldott legnagyobb feladatokban 8 gép és 64 mu  velet volt. [6] az, amelyben eloször oldottak meg egy, az irodalomból jól ismert, és

állandó  10 munkát és 10 gépet tartalmazó feladatot, továbbá ugyanez a dolgozat kihívást jelento beszámol számos, a korábbiaknál nagyobb probléma, például 20 munka, 5 gép és számos muvelet  megoldásáról is. Johnson módszerének a kétgépes, többutas problémára való kiterjesztése Jackson [24] érdeme. A többutas probléma kezelésére Roundy [37] javasolta a kétszintes modellt. Az on-line algoritmusokra vonatkozó eredmények összefoglalása megtalálható ennek a könyvnek a második kötetében. Az ütemezéselmélet egyik fontos alkalmazási területe a számítógépes feladatmegoldás. Ezzel kapcsolatban ajánljuk Blazewicz és társai [3], Coffman [8] és Pinedo [34, 35] monográáit. Pinedo két ajánlott könyve a determinisztikus ütemezés mellett a sztochasztikus ütemezés módszereit és eredményeit is tárgyalja.  a 9-8. feladat A 9-2. feladat forrása [43], a 9-4 feladat [15]-ból, a 9-5 feladat [18]-bol, pedig [25]-ból származik.

Irodalomjegyzék [1] E. Balas Sequencing via disjunctive graphs: an implicit enumeration algorithm Operation Research, 17:941–953, 1969. 413 [2] J. R Barker, G B McMahon Scheduling the general job-shop Management Science, 31:594–598, 1985 413, 414 [3] J. Blazewicz, K Ecker, E Pesch, G Schmidt, J Weglarz Scheduling Computer and Manufacturing Processes Springer-Verlag, 2001 (2 kiadás) 414 [4] G. Brooks, C R White An algorithm for nding optimal or near optimal solutions to the production scheduling problem Journal of Industrial Engineering, 16:34–40, 1965 413 [5] P. Bruckner Scheduling Algorithms Springer-Verlag, 1998 412 [6] J. Carlier, E Pinson Algorithm for solving the job-shop problem Management Science, 35:164–176, 1989 413, 414 [7] J. Charlton, C C Death A method of solution for general machine scheduling problems Operations Research, 18:689–707, 1970 413 [8] E. Coffman Computer and Job Shop Scheduling John Wiley & Sons, 1976 414 [9] E. Coffman, M Garey, D Johnson An

application of bin-packing to multiprocessor scheduling SIAM Journal on Computing, 7:1–17, 1978 413 [10] E. G Coffman, J Csirik, G J Woeginger Approximate solutions to bin packing problems In P M Pardalos,  M. G C Resende (szerkesztok), Handbook of Applied Optimization, 607–615. o Oxford University Press, 2002. 413 [11] M. L Fisher Optimal solution of scheduling problems using lagrange multipliers: Part I Operations Research, 21:1114–1127, 1973 413, 414 [12] M. L Fisher Optimal solution of scheduling problems using lagrange multipliers: Part II, In S E Elmagh Symposium on the Theory of Scheduling and Its Applications Springer-Verlag, 1973 413 raby (szerkeszto), [13] D. K Friesen Tighter bounds for the multit processor scheduling algorithm Journal of Algorithms, 7:35– 59, 1984. 413 [14] D. K Friesen, M A Langston Evaluation of a multit-based scheduling algorithm Journal of Algorithms, 7:35–59, 1986. 413 [15] M. R Garey, R L Graham Performance guarantees for scheduling algorithm

Operations Research, 26:3– 21, 1978. 414 [16] J. Grabowski On two-machine scheduling with release and due-dates to minimize maximum lateness Opsearch, 17:133–154, 1980 413 [17] R. L Graham Bounds for certain multiprocessor anomalies The Bell Systems Technical Journal, 45:1563– 1581, 1966. 413 [18] R. L Graham Bounds on multiprocessing timing anomalies SIAM Journal on Applied Mathematics, 17:416–429, 1969. 414 [19] R. L Graham, E L Lawler, J K Lenstra, A H G Rinnoy Kan Optimization and approximation in deterministic sequencing and scheduling: a survey Annals of Discrete Mathematics, 5:287–326, 1979 412 [20] J. N D Gupta, S S Reddi Improved dominance conditions for the three-machine owshop scheduling problem. Operations Research, 26:200–203, 1978 413 416 Irodalomjegyzék [21] W. A Horn Minimizing average ow time with parallel machines Operations Research, 21:845–847, 1973 413 [22] M. Hujter Egy ütemezéselméleti probléma vizsgálata és alkalmazásai (Investigation of a

scheduling problem and its applications), 1987. Doktori értekezés, ELTE TTK 413 [23] J. R Jackson Research Report 43, Management Science Research Project, University of California, 1955 413 [24] J. R Jackson An extension of Johnson's results on job shop scheduling Naval Research Logistics Quaterly, 3:201–224, 1956. 414 [25] S. M Johnson Optimal two- and three-stage production schedules with setup times included Naval Research Logistics Quaterly, 1:61–68, 1954 414 [26] B. Lageweg, J K Lenstra, A Rinnoy Kan Job-shop scheduling by implicit enumeration Management Science, 24:441–450, 1977. 413, 414 [27] B. Lageweg, J K Lenstra, A Rinnoy Kan A general bounding scheme for the permutation ow-shop problem Operations Research, 26:53–67, 1978 413 [28] E. L Lawler Optimal sequencing of a single machine subject to precedence constraints Management Science, 19:544–546, 1973 413 [29] E. L Lawler, J K Lenstra, A H G Rinnoy Kan, D B Shmoys Sequencing and scheduling: Algorithms  Handbooks

in Operations Research and complexity. In S C Graves, A Kan, P Zipkin, P Hszerkesztok), and Management Science, Volume 4: Logistics of Production and Inventory, 445–522. o Elsevier, 1993 412, 413 [30] A. S Manne On the job-shop scheduling problem Operations Research, 9:219–223, 1960 413 [31] G. B McMahon Optimal production schedules for ow shops Canadian Operation Research Society Journal, 7:141–151, 1969 413 [32] R. McNaughton Scheduling with deadlines loss functions Management Science, 6:1–12, 1959 413 [33] J. Piehler Ein Beitrag zum Reihenfolgeproblem, Unternehmensforschung Unternehmerforschung, 4:138– 142, 1960. 413 [34] M. Pinedo Scheduling: Theory, Algorithms and Systems Pearson Education, 2001 (2 kiadás) 414  [35] M. Pinedo Planning and Scheduling in Manufacturing and Services Springer-Verlag, 2004 (megjelenoben) 414 [36] M. H Rothkopf Scheduling independent tasks on parallel machines Management Science, 12:437–447, 1966. 413 [37] R. O Roundy, W L Maxwell, Y T Herer, S

R Tayur, A W Getzler A price-directed approach of production operations IIE Transactions, 23:149–160, 1991 414 [38] B. Roy, B Sussmann Les problémes d'ordonnuncement avec contraintes disjonctives Note DS no 9 bis, SEMA, 1964. 413 [39] S. Sahni Algorithms for scheduling independent tasks Journal of the ACM, 23:116–127, 1976 413 [40] S. Sahni Preemptive scheduling with due dates Operations Research, 27:929–934, 1979 413 [41] L. Schrage Solving resource-constrained network problems by implicit enumeration Operations Research, 18:263–278, 1970. 413 [42] L. Schrage Obtaining optimal solutions to resource constrained network scheduling problems, 1971 Publikálatlan kézirat 413 [43] W. Smith Various optimizers for single-stage production Naval Research Logistics Quaterly, 3:59–66, 1956. 413, 414 [44] W. Szwarc Optimal elimination methods in the m × n sequencing problem Operations Research, 21:1250– 1259, 1973. 413 [45] W. Szwarc Dominance conditions for the three-machine

ow-shop problem Operations Research, 26:203– 206, 1978. 413 [46] W. Szwarc Elimination methods in the m × n sequencing problem CWI Quarterly, 18:295–305, 1971 413 [47] B. Vizvári Egészértéku  programozás. ELTE TTK, 1990 413 Tárgymutató A, Á  367 legrövidebb megmunkálási ido,  365 állásido, általános párhuzamos gépek, 365  390 átfutási ido, LIFO sorrend, 409 listás ütemezés, 381 átlapolás, 365, 378  LPT, lásd leghosszabb megmunkálási ido LPT sorrend, 377, 384, 409, 411 LWR, lásd legkevesebb megmaradt megmunkálás D duál feladat (az egyutas ütemezési problémáé), 390 M E, É megszakítás, 365 MF algoritmus, 386, 387  364 megmunkálási ido,  EDD, 372, 409, lásd legkorábbi határido egyutas ütemezési probléma, 365, 388  elozéses egyutas ütemezési probléma, 390  elozésnélküli egyutas ütemezési probléma, 390  eroforrás, 363, 365 MF ládapakolási algoritmus, 385 M́, 385 mohó ládapakolási

eljárás, 383 munkadarab, 363 muvelet,  363 MWKR sorrend, 409 MWR, lásd leghosszabb megmaradt megmunkálás F FF, 383, lásd mohó ládapakolási algoritmus FIFO sorrend, 409 O, Ó on-line ütemezési feladat, 366 G Gantt-diagram, 411fe P gép, 363 program, 398  365 puha határido, H hasonló párhuzamos gépek, 365  365 határido, R raktározás, 363 reguláris célfüggvény, 366  368 rendelkezésre állási ido, I, Í irreguláris célfüggvény, 366 S sorozat, 363, 365 K kapacitás, 363 SPT, 374, 375, 378, 379, 409, 411fe, 413, lásd  |textitlegrövidebb legrövidebb megmunkálási ido L SRPT, lásd legrövidebb megmaradt megmunkálási  ido ládapakolási probléma, 383  376 leghosszabb megmunkálási ido, legkevesebb megmaradt megmunkálás, 409  384 legkisebb megmunkálási ido,  megmunkálási ido  súlyozott legrövidebb megmunkálási idok, 374 SWPT, lásd súlyozott legrövidebb megmunkálási  sorrendje idok SWPT sorrend, 379  sorrendje, 371

legkorábbi határidok  legrövidebb megmaradt megmunkálási idok, 375 SZ 418 szállítás, 363 Tárgymutató  365 tényleges határido, termelési feladat, 364 tevékenység, 363 T technológiai útvonal, 364 többutas ütemezési probléma, 365, 396 Névmutató B Jackson, J. R, 414, 416 Balas, E., 415 Barker, J. R, 415 Johnson, David S., 413, 415 Johnson, S. M, 416 Bellman, Richard, 397 Blazewicz, Jacek, 414, 415 Brooks, G. H, 415 Brucker, Peter, 415 K Kan, A. H, 416 C L Carlier, J., 415 Charlton, M., 415 Lageweg, B. J, 416 †Lagrange, Joseph-Luis, 406, 411 Coffman, Ed G., Jr, 413–415 Langston, M. A, 413, 415 Lawler, Eugene L., 412, 413, 415, 416 Lenstra, Jan Karel, 415, 416 CS Csirik János, 413, 415 M Manne, A. S, 416 D Maxwell, W. L, 416 Death, C. C, 415 McMahon, G. B, 415, 416 McNaughton, R., 413, 416 E, É Ecker, K., 415 Elmaghraby, S. E, 415 P Pesch, E., 415 Piehler, J., 413, 416 Pinedo, Michael, 414, 416 F Pinson, E., 415 Fisher, M. L,

413, 415 Friesen, D. K, 413, 415 R Reddi, S. S, 415 G Gantt, Henry Laurence, 411, 412 Garey, Michael R., 413, 415 Getzler, A. W, 416 Grabowski, J., 413, 415 Graham, Ronald Lewis, 412, 415 Graves, S. C, 416 Gupta, J. N D, 415 Rinnoy Kan, A. H G, 415, 416 Rothkopf, M. H, 413, 416 Roundy, R. O, 416 Roy, B., 416 S Sahni, Sartaj, 413, 416 Schmidt, G., 415 Schrage, L., 416 H Herer, Y. T, 416 Horn, W. A, 413, 415 Shmoys, David B., 416 Smith, W. E, 416 Sussmann, B., 416 Hujter Mihály, 415 J SZ Szwarc, Wlodzimierz, 416 420 Névmutató T W Tayur, S. R, 416 Weglarz, J., 415 White, C. R, 415 Woeginger, Gerard J., 415 V Vizvári Béla, 413, 416 Z Zipkin, P. H, 416 Tartalomjegyzék V. DISZKRÉT OPTIMALIZÁCIÓ . 361 Bevezetés . 362 9. Ütemezéselmélet (Vizvári Béla) . 363 9.1 364 Formális rendszer ütemezési feladatok osztályozására . 9.11  Az α mezo .

364 9.12  . A β mezo 365 9.13  . A γ mezo 366 9.2 A Gantt-diagramok . 367 9.3 Ütemezési problémák egyetlen gépen 369 9.4 Ütemezési problémák párhuzamos berendezéseken 9.5 Az egyutas ütemezési probléma 9.6 . . 377 . 388 A többutas ütemezési probléma . 396 9.61 A kritikus út módszere . 396 9.62 A diszjunktív gráf modell . 397 9.63 Egészértéku  programozási modellek . 403 9.64 Heurisztikus módszerek . 408 Irodalomjegyzék . 415 Tárgymutató . 417 Névmutató 419