Páros munkák ütemezése párhuzamos gépeken (coupled task scheduling on parallel machines)

Témavezető:	Györgyi Péter
	SZTAKI
email:	gyorgyi.peter@sztaki.hu

Projekt leírás

Adott néhány azonos gép és munkák egy halmaza. Egy gép egyszerre egy munkán tud dolgozni. Az ütemezendő munkák két részből állnak ismert megmunkálási időkkel, továbbá a részek között is egy meghatározott időnek kell eltelnie. A cél a munkák ütemezése oly módon, hogy valamilyen célfüggvény szerint minél jobb eredményt érjünk el. A feladatnak számos gyakorlati alkalmazása van, pl. radar jelek adásánál és vételénél, kémiai gyártási feladatoknál vagy betegek kemoterápiás kezelésekhez való beosztásánál.

Az eddigi eredmények döntő része egy gépes környezetben a makespan (az utolsó munka befejezésének időpontja) minimalizálásával kapcsolatos, ezeket különböző kombinatorikus módszerekkel értek el. Az elmúlt években más célfüggvények vizsgálata is megindult egy gép esetén, de párhuzamos gépeken alig vannak eredmények. A projekt célja ilyen variánsok vizsgálata. Számos nyitott kérdés van, így lehetőség van tisztán elméleti eredményeket keresni és különféle megoldó algoritmusok fejlesztésére is.

Előfeltételek

angol nyelvtudás

javasolt az Ütemezéselmélet tárgy felvétele (ha még nem történt meg)

Hivatkozások

1) A.J. Orman, C.N. Potts: On the complexity of coupled-task scheduling, Discrete Applied Mathematics (1997) https://www.sciencedirect.com/science/article/pii/S0166218X96000418?via%3Dihub