Ütemezési elmélet

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. november 14-én felülvizsgált verziótól ; az ellenőrzésekhez 10 szerkesztés szükséges .

Az ütemezéselmélet a diszkrét matematikának a rendezési problémákkal foglalkozó ága . Általános esetben a problémákat a következőképpen fogalmazzuk meg: Meghatározzuk a munkakörök (követelmények) egy meghatározott jellemzőkészletét: a követelmény feldolgozásának időtartama (a legegyszerűbb eset), a követelmény feldolgozásának költsége, a pillanat a megkeresés megérkezik, a megkeresés kézbesítésének határideje. Meg van adva egy bizonyos gép (eszköz) készlet , amelyen a követelményeket meghatározott sorrendben kell kiszolgálni. ${\displaystyle J=\{J_{1},J_{2},\dots ,J_{n}\))$ $M=\{M_{1},M_{2},\dots ,M_{m}}\}$

A diszkrét optimalizálás feladata : olyan ütemterv összeállítása, amely minimalizálja a munkavégzés idejét, a munka költségeit stb. Az ütemterv azt jelzi, hogy mely gépeken és mikor kell a követelményeket szervizelni (munkát végezni).

Az ütemezéselmélet feladatai két csoportra oszthatók:

Szakítsa meg a feladatokat. Egy követelmény kiszolgálása egy gépen bármikor megszakítható (a későbbi leállás lehetőségével ugyanazon vagy egy másik gépen) egy másik igény kiszolgálása érdekében.
megszakítás nélküli feladatok - a gép minden követelményét az elejétől a végéig megszakítás nélkül kiszolgálják.

Az ütemezéselméleti feladatoknak többféle változata létezik, ezek egy része NP-teljes , van, amelyik a polinomiális feladatok osztályába tartozik , néhány probléma esetében nem lehetett bizonyítani egyetlen komplexitási osztályba való tartozást sem. Van egy olyan sejtés, hogy a megszakításokat megengedő feladat semmivel sem nehezebb, mint egy megszakítás nélküli feladat. A legtöbb probléma esetében megfigyelhető, kivéve egyet, ahol egy megszakítás nélküli változatnál bebizonyosodik, hogy a polinomiális feladatok osztályába tartozik , míg egy hasonló, megszakításokkal járó probléma esetén nincs bizonyíték arra, hogy valamelyik komplexitási osztályba tartozik.

A gépeken végzett munka tudománya szerint négy fő feladatosztályt lehet megkülönböztetni:

Nyitott bolt, nyílt sor - minden követelménynek megvan a maga géprészcsoportja, amelyek mindegyikén szervizelni kell egy ideig. A szervizelés sorrendje ezeken a gépeken tetszőleges. Különféle célfüggvények vannak beállítva.
Állásműhely, műhely - minden követelménynek megvan a maga megrendelt géprészcsoportja (útvonala), amelyen adott sorrendben szervizelni kell. Különféle célfüggvények vannak beállítva.
Flow shop , flow line – minden gép rendben van –és minden követelmény ebben a sorrendben megy végig az összes gépen. Az ütemezést a követelmények permutációja határozza meg. Általános szabály, hogy a kérések kiszolgálásának teljes ideje minimálisra csökken. ${\displaystyle M_{1},M_{2},\dots ,M_{m))$
Feladat határidőkkel - minden igénynél meg van adva az érkezés pillanata, a szolgáltatás ideje, a szolgáltatás befejezésének határideje. A szervizelés sorrendje az eszközökön tetszőleges. Olyan ütemtervet kell találnia, amely betartja a határidőket. Ha létezik ilyen ütemezés, beállítható a megszakítások számának minimalizálása.

Az utolsó feladatot egylépcsősnek , az első háromat többlépcsősnek nevezzük , mivel minden követelményhez több szakasz vagy szolgáltatási művelet tartozik különböző eszközökön. A megszorítások és a szolgáltatási diszciplínák különféle kombinációi lehetségesek, de a végrehajtási időben polinomiális algoritmusok ezekből az osztályokból csak a legegyszerűbb problémákra ismertek.

Konkrétan a Flow shop problémára két gépen létezik az időbonyolultság Johnson-algoritmusa [1] , amely egy ütemezést készít a minimális teljes szolgáltatási idővel. $O(n\log(n))$

Egy tetszőleges számú eszközzel és szolgáltatáskimaradásokkal rendelkező feladathoz létezik egy időbonyolítási algoritmus , amely a határidőket figyelembe vevő ütemezést készít [2] . $O(n^{3})$

Az Open shop és Job shop problémák egy készülékkel, megszakítások nélküli megoldása a követelmények némi permutációja, és egy tetszőleges célfüggvényre ezek a problémák NP-teljesek. Néhány konkrét célfüggvényhez azonban találtak polinomiális algoritmusokat. [3] [4] [5]

A folytonos időben írt ütemezéselmélet (ütemezés) problémáinak általában végtelen számú lehetséges megoldása van. A rendezési módszer lehetővé teszi, hogy az ütemezési problémákat optimalizálási problémákra redukáljuk a jobok véges permutációinak halmazain. A folytonos időben történő ütemezéselmélet (ütemezés) problémájának általános megállapítása megfogalmazásra kerül, melyben a megoldási komponenseket az idő egész számú függvényeivel írjuk le, és amely a rendezési módszerrel megoldható. [6]

Az eredeti problémák rendelési problémákra való redukálásának két módja a kompakt (aktív) és a kvázikompakt (félaktív) megoldások koncepcióján alapul. [7] V. V. Shmelev fenti előnyomatában [6] a kompakt és kvázi -kompakt megoldások fogalmát általánosítják, és ennek alapján a monoton megoldások új koncepcióját javasolják. Minden monoton megoldás egyszerre kompakt és kvázi kompakt, így általában kevesebb ilyen megoldás létezik. Ez leegyszerűsíti a rendelési problémák megoldását.

Az összetett késleltetésű erőforrás-allokáció dinamikus problémáinak leírására , beleértve a vektoros és elosztott késleltetéseket is, amelyek magukban foglalják az ütemezéselméleti (ütemezési) problémákat is, Shmelev V.V. 1983 - ban [6] volt az első, aki implicit módon és folyamatosan használta a konvolúciós . Ezt követően ezt a műveletet kifejezetten diszkrét időre használta, és az ütemezéselmélet (ütemezés) problémájának általános megfogalmazását konvolúciókkal rendelkező lineáris dinamikus programozási probléma formájában fogalmazta meg . [8] [9] Ez az utasítás lehetővé teszi nagyszámú dinamikus probléma egyszerű és tömör leírását, beleértve az egész változókkal rendelkezőket is . Shmelev V. V. kiterjesztette a pontos büntetési függvények módszerére vonatkozó eredményeit erre a beállításra.

Jegyzetek

↑ SM Johnson , Optimális két- és háromlépcsős gyártási ütemterv a beállítási időkkel együtt, Naval Res. log. Kvart. I(1954) 61-68.
↑ Tanaev V.S., Gordon V.S., Shafransky Ya.M. Az ütemezés elmélete. Egylépcsős rendszerek - M.: Nauka, 1984.
↑ A menetrend szerinti állatkert . Letöltve: 2013. április 27. Az eredetiből archiválva : 2013. április 28.. (határozatlan)
↑ CiteSeerX – Egygépes ütemezés elsőbbségi késések függvényében . Letöltve: 2013. április 27. Az eredetiből archiválva : 2013. április 28.. (határozatlan)
↑ Az ütemezési problémák összetettségi eredményei . Letöltve: 2013. április 27. Az eredetiből archiválva : 2013. április 28.. (határozatlan)
↑ 1 2 3 V. V. Shmelev. Rendelési mód ütemezési problémákban. Előnyomtatás. Moszkva: VNIISI . 1983. Az előnyomat elérhető az eLIBRARY.RU Tudományos Elektronikus Könyvtár honlapján Shmelev V.V. publikációinak listájában.
↑ Conway R. V., Maxwell V. L., Miller L. V. Ütemezéselmélet. - M .: "Nauka", 1975, 6.5. szakasz.
↑ Shmelev V.V. Az ütemezés dinamikus feladatai. Automatizálás és Telemechanika , 1997, 1. sz., 121-125.
↑ Shmelev V.V. Pontos büntetőfüggvények módszere lineáris vegyes egészszámú optimalizálási problémákhoz. Disszertáció a fizikai és matematikai tudományok doktora fokozat megszerzéséhez, M.: ISA RAN, 2000, 6. fejezet. A disszertáció és absztraktja elérhető az eLIBRARY.RU Tudományos Elektronikus Könyvtár honlapján, Shmelev V.V. publikációi listájában.

Irodalom

Richard W. Conway, William L. Maxwell, Louis W. Miller . Az ütemezés elmélete
- Conway R. V., Maxwell V. L., Miller L. V. Ütemezéselmélet. Moszkva: A Nauka kiadó fizikai és matematikai szakirodalmának főkiadása, 1975.
Tanaev V. S. , Shkurba V. V. Bevezetés az ütemezési elméletbe. ("Közgazdasági és Matematikai Könyvtár" sorozat), Moszkva: A "Nauka" kiadó fizikai és matematikai irodalmának fő kiadása, 1975.
Levin VI. Strukturális-logikai módszerek az ütemezéselméletben. Penza: Penz Kiadó. állapot technol. akadémia, 2006.
Lazarev A. A. Ütemezési elmélet. Az abszolút hiba becslései és az ütemezési problémák közelítő megoldásának sémája . oktatóanyag. (IPU RAS, MIPT) - M.: MIPT, 2008. - 222 p. ISBN 978-5-7417-0257-4
Lazarev A. A., Musatova E. G., Gafarov E. R., Kvaratskhelia A. G. Ütemezési elmélet. A vasúttervezés problémái . M.: IPU RAN, 2012. 92 p. ISBN 978-5-91450-102-7 .
Brucker P. Ütemezési algoritmusok . Heidelberg, Springer. Ötödik kiad. ISBN 978-3-540-24804-0 (hivatalos kiadás a kiadó portálján).
Peter Brucker ütemezési algoritmusok . Heidelberg, Springer. Ötödik kiad. ISBN 978-3-540-24804-0 Archiválva : 2016. február 21. a Wayback Machine -nél

Népszerű tudományos publikációk

Shkurba V. V. " A három gép problémája ." — M.: Nauka, 1976. — 96 p., illusztráció.