Ugrás a tartalomra
ENHU
Címlap

Main navigation

  • Felfedezés
    • Hírek
    • Eredmények
  • Rólunk
    • A projekt
    • Résztvevők
    • Mérföldkövek
  • Publikációk
  1. Címlap
  2. Publikációk

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

DOI
Nemzeti Kutatási, Fejlesztési és Információs Hivatal - Az NKFI alapból megvalósuló projekt

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.

Címlap
1111 Budapest, Kende u. 13-17.
Megyery Judit, projektmenedzser:
+36 1 279 6121
coprologs@hun-ren.sztaki.hu

© COPROLOGS