<abstract xmlns="http://www.w3.org/1999/xhtml"><p>The coupled tasks scheduling problem is class of scheduling problems, where each task consists of two operations and a separation gap between them. The high-multiplicity is a compact encoding, where identical tasks are grouped together, and the group is specified instead of each individual task. Consequently the encoding of a problem instance is decreased significantly. In this article we derive a lower bound for the problem variant as well as propose an asymptotically optimal algorithm. The theoretical results are complemented with computational experiment, where a new algorithm is compared with three other algorithms implemented.</p></abstract>

The coupled tasks scheduling problem is class of scheduling problems, where each task consists of two operations and a separation gap between them. The high-multiplicity is a compact encoding, where identical tasks are grouped together, and the group is specified instead of each individual task. Consequently the encoding of a problem instance is decreased significantly. In this article we derive a lower bound for the problem variant as well as propose an asymptotically optimal algorithm. The theoretical results are complemented with computational experiment, where a new algorithm is compared with three other algorithms implemented.

Scheduling High Multiplicity Coupled Tasks

Foundations of Computing and Decision Sciences

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"Scheduling High Multiplicity Coupled Tasks"}

The coupled tasks scheduling problem is class of scheduling problems, where each task consists of two operations and a separation gap between them. The...

Scheduling High Multiplicity Coupled Tasks

Data publikacji: 27 mar 2020

Zakres stron: 47 - 61

Otrzymano: 29 paź 2018

Przyjęty: 24 sty 2020

DOI: https://doi.org/10.2478/fcds-2020-0004

Słowa kluczowe
Coupled tasks, scheduling, complexity theory, asymptotically optimal algorithms, high multiplicity

© 2020 Wojciech Wojciechowicz et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Scheduling High Multiplicity Coupled Tasks

Data publikacji: 27 mar 2020

Zakres stron: 47 - 61

Otrzymano: 29 paź 2018

Przyjęty: 24 sty 2020

DOI: https://doi.org/10.2478/fcds-2020-0004

Słowa kluczoweCoupled tasks, scheduling, complexity theory, asymptotically optimal algorithms, high multiplicity

© 2020 Wojciech Wojciechowicz et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Słowa kluczowe
Coupled tasks, scheduling, complexity theory, asymptotically optimal algorithms, high multiplicity