Az ütemezéselmélet az operatív kutatás olyan ága, amely az optimális feladat végrehajtási dátumok kiszámítására összpontosít. Ehhez nagyon gyakran egyidejűleg szükséges elosztani az e feladatok végrehajtásához szükséges erőforrásokat. Az ütemezési probléma tervezési részproblémának tekinthető , amelyben az ütemezett feladatok operatív végrehajtásáról kell dönteni.
Az ütemezési probléma a feladatok teljesítésének időbeli megszervezésében áll, figyelembe véve az időkorlátokat (határidők, sorrendbeli korlátozások) és a szükséges erőforrások rendelkezésre állásával kapcsolatos korlátozásokat.
A termelésben (gyártás, áruk, szolgáltatások) problémaként lehet bemutatni, ahol a rendszert alkotó különböző központokon keresztül be kell váltani és ellenőrizni kell egy megrendelés haladását.
Az ütemezés az ütemezési probléma megoldása. A feladatok végrehajtásának ütemezése („megrendelés” és „naptár”), valamint az erőforrások elosztása határozza meg, és egy vagy több célkitűzés elérésére irányul. Az ütemezést nagyon gyakran egy Gantt-diagram képviseli .
A feladat egy kezdeti és / vagy befejezési dátum szerint időben elhelyezkedő elemi entitás, amelynek megvalósításához időtartam szükséges, és amely egy bizonyos intenzitásnak megfelelő eszközöket emészt fel. Egyes modellek tartalmazzák az esedékesség fogalmát, azt az időpontot, amikor a feladatot el kell végezni; ezekben az esetekben a késedelem büntetést von maga után.
A problémától függően a feladatokat darabokban, vagy megszakítás nélkül kell végrehajtani; ezután megelőző és nem megelőző problémákról beszélünk. Ha a feladatokra nem vonatkozik semmilyen következetességi kényszer, akkor azt mondják, hogy függetlenek.
Több feladat is tevékenységet jelenthet, és több tevékenység meghatározhat egy folyamatot .
Az erőforrás egy technikai vagy emberi eszköz, amelyet egy feladat végrehajtására használnak, és korlátozott mennyiségben, kapacitása rendelkezésre áll.
Többféle erőforrást kell megkülönböztetni. Az erőforrás megújítható, ha egy vagy több feladatra való felosztása után ugyanabban a mennyiségben (férfiak, gépek, berendezések általában) rendelkezésre áll; a felhasználható erőforrások mennyisége bármikor korlátozott. Egyébként fogyasztható (alapanyagok, költségvetés); a teljes fogyasztás (vagy felhalmozás) az idő múlásával korlátozott. Egy erőforrás kétszeresen korlátozott, ha mind azonnali felhasználása, mind az összfogyasztása korlátozott (a pénz jó példa).
Akár megújuló, akár fogyasztható, az erőforrások elérhetősége idővel változhat. Elérhetőségi görbéje általában eleve ismert, kivéve azokat az eseteket, amikor bizonyos generáló feladatok elhelyezésétől függ.
A megújuló erőforrások esetében főleg megkülönböztetünk olyan diszjunktív erőforrásokat is, amelyek egyszerre csak egy feladatot tudnak végrehajtani (szerszámgép, robotmanipulátor), és olyan kumulatív erőforrásokat, amelyeket egyszerre több feladat is felhasználhat, de korlátozott számban (munkáscsoport) , munkaállomás).
A megszorítások korlátozásokat fejeznek ki azokra az értékekre, amelyeket a döntési változók egyidejűleg meghozhatnak. Megkülönböztetünk:
Az ütemezési probléma megoldása során a stratégiák két fő típusa közül választhatunk, amelyek a megoldások optimálisra, vagy egyszerűbben az elfogadhatóságukra törekszenek.
Az optimalizálási megközelítés azt feltételezi, hogy a probléma jelölt megoldásait racionálisan lehet elrendelni egy vagy több, teljesítménymutatók alapján felépített numerikus értékelési kritérium szerint. Ezért törekszünk az ilyen kritériumok minimalizálására vagy maximalizálására. Megjegyezzük például azokat
Az ütemezéses kutatások gyakran egy kiszámítható univerzum feltételezésén alapultak, ahol a probléma összes adata előre ismert, és a valós problémák nem veszélyeztetik a tervezést. A gyakorlatban különféle rendellenességek fordulhatnak elő: gépi meghibásodások, munkavállalói távollétek, szállítás késedelmek. Ebben az esetben felül kell vizsgálni az ütemezést, és a kezdeti adatok alapján kiszámított nagyon jó ütemezés elveszítheti a minőségét.
A robusztus ütemezés az ütemezés meglehetősen friss ága, amelynek már nem csak az optimális (vagy kvázi optimális) ütemtervek biztosítása a célja, hanem mindenekelőtt a robusztus ütemezések. Az erősség az ütemterv teljesítésének képessége a zavarok előfordulása ellenére is.
Többféle robusztus megközelítés létezik: