Páros munkák ütemezése (coupled task scheduling)
| Témavezető: | Györgyi Péter |
| SZTAKI | |
| email: | gyorgyi.peter@sztaki.hu |
Projekt leírás
Adott egy gép, amely 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 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, 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
2) D. Fischer, P. Györgyi: Approximation algorithms for coupled task scheduling minimizing the sum of completion times, Annals of Operations Research (2023) https://link.springer.com/article/10.1007/s10479-023-05322-5