EN HU
  • Discover
    • News
    • Results
  • About us
    • The project
    • Members
    • Milestones
  • Publications
  1. Home
  2. Publications

Györgyi P., Fischer D.: Coupled task scheduling – minimizing the total completion time. Szeged WORkshop on Discrete Structures, November 23-24, 2023

DOMLAB

Coupled task problem on a single machine consists of scheduling a set of jobs, where each job has two tasks. These tasks have to be scheduled so that no tasks overlap and the two tasks of a job are scheduled with exactly their given delay time in between them. We focus on the minimization of the total completion time of the jobs. Recently, [1] drew an almost full complexity picture for these problems. In this talk, we will present approximation algorithms for several NP-hard variants based on the results of [2]. Acknowledgements: This research has been supported by the TKP2021-NKTA-01 NRDIO grant on ”Research on cooperative production and logistics systems to support a competitive and sustainable economy”.

1111 Budapest, Kende u. 13-17.

Judit Megyery, project manager
+36 1 279 6121

coprologs@hun-ren.sztaki.hu

© COPROLOGS