Total Completion Time Minimization for Scheduling with Incompatibility Cliques

Klaus Jansen; Alexandra Lassota; Marten Maack; Tytus Pikies

Total Completion Time Minimization for Scheduling with Incompatibility Cliques

Abstrakt

This paper considers parallel machine scheduling with incompatibilities between jobs. The jobs form a graph equivalent to a collection of disjoint cliques. No two jobs in a clique are allowed to be assigned to the same machine. Scheduling with incompatibilities between jobs represents a well-established line of research in scheduling theory and the case of disjoint cliques has received increasing attention in recent years. While the research up to this point has been focused on the makespan objective, we broaden the scope and study the classical total completion time criterion. In the setting without incompatibilities, this objective is well-known to admit polynomial time algorithms even for unrelated machines via matching techniques. We show that the introduction of incompatibility cliques results in a richer, more interesting picture. We prove that scheduling on identical machines remains solvable in polynomial time, while scheduling on unrelated machines becomes APX-hard. Next, we study the problem under the paradigm of fixed-parameter tractable algorithms (FPT). In particular, we consider a problem variant with assignment restrictions for the cliques rather than the jobs. We prove that, despite still being APX-hard, it can be solved in FPT time with respect to the number of cliques. Moreover, we show that the problem on unrelated machines can be solved in FPT time for reasonable parameters, in particular, the parameter combination: maximum processing time, number of job kinds, and number of machines or maximum processing time, number of job kinds, and number of cliques. The latter results are extensions of known results for the case without incompatibilities, and can even be further extended to the case of total weighted completion time. All of the FPT results make use of n-fold Integer Programs that recently received great attention by proving their usefulness for scheduling problems.

Autorzy (4)

Klaus Jansen Profesor Doktor
Alexandra Lassota
Marten Maack Doktor
Tytus Pikies dr inż.

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

Słowa kluczowe

Informacje szczegółowe

Kategoria:

Aktywność konferencyjna

Typ:

publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)

Język:

angielski

Rok wydania:

2021

Opis bibliograficzny:

Jansen K., Lassota A., Maack M., Pikies T.: Total Completion Time Minimization for Scheduling with Incompatibility Cliques// / : , 2021,

Źródła finansowania:

Supported by DFG Projects "Strukturaussagen und deren Anwendung in Scheduling- und Packungsprobleme", JA612/20-1 and, JA 612/20-2; Gdańsk University of Technology, grant no. POWR.03.02.00-IP.08-00-DOK/16.
Projekt Rozwój Interdyscyplinarnego Programu Studiów Doktoranckich o wymiarze międzynarodowym

Weryfikacja: