Scheduling High Multiplicity Coupled Tasks
| Autor: | Michaël Gabay, Wojciech Wojciechowicz |
|---|---|
| Přispěvatelé: | Institute of Computing Science [Poznan], Poznan University of Technology (PUT), Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS) |
| Rok vydání: | 2020 |
| Předmět: |
0209 industrial biotechnology
021103 operations research Job shop scheduling Computer science 0211 other engineering and technologies complexity theory QA75.5-76.95 [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] 02 engineering and technology High multiplicity Upper and lower bounds Coupled tasks Scheduling (computing) high multiplicity 020901 industrial engineering & automation Asymptotically optimal algorithm asymptotically optimal algorithms Electronic computers. Computer science scheduling Algorithm |
| Zdroj: | Foundations of computing and decision sciences Foundations of computing and decision sciences, 2020, 45 (1), pp.47-61. ⟨10.2478/fcds-2020-0004⟩ Foundations of Computing and Decision Sciences, Vol 45, Iss 1, Pp 47-61 (2020) |
| ISSN: | 2300-3405 0867-6356 |
| DOI: | 10.2478/fcds-2020-0004 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|