Skip to main content
ENHU
Home

Main navigation

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

Fischer, D., Györgyi, P. Approximation algorithms for coupled task scheduling minimizing the sum of completion times. Ann Oper Res (2023).

DOI
National Research, Development and Innovation Office - Project financed from the NRDI fund

In this paper we consider the coupled task scheduling problem with exact delay times on a single machine with the objective of minimizing the total completion time of the jobs. We provide constant-factor approximation algorithms for several variants of this problem that are known to be NP hard, while also proving NP-hardness for two variants whose complexity was unknown before. Using these results, together with constant-factor approximations for the makespan objective from the literature, we also introduce the first results on bi-objective approximation in the coupled task setting.

Home
1111 Budapest, Kende u. 13-17.
Judit Megyery, project manager
+36 1 279 6121
@email

© COPROLOGS