<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

Published Online: Mar 27, 2020

Page range: 47 - 61

Received: Oct 29, 2018

Accepted: Jan 24, 2020

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

Keywords
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

Published Online: Mar 27, 2020

Page range: 47 - 61

Received: Oct 29, 2018

Accepted: Jan 24, 2020

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

KeywordsCoupled 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.

Keywords
Coupled tasks, scheduling, complexity theory, asymptotically optimal algorithms, high multiplicity