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.
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