Scheduling High Multiplicity Coupled Tasks
2020
scientific article
english
- coupled tasks
- scheduling
- complexity theory
- asymptotically optimal algorithms
- high multiplicity
EN 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.
47 - 61
CC BY-NC-ND (attribution - noncommercial - no derivatives)
public
20
40