Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
Medientyp:
E-Artikel
Titel:
Scheduling uniform machines with restricted assignment
Beteiligte:
Li, Shuguang;
Liu, Zhimeng
Erschienen:
American Institute of Mathematical Sciences (AIMS), 2022
Erschienen in:
Mathematical Biosciences and Engineering, 19 (2022) 9, Seite 9697-9708
Sprache:
Nicht zu entscheiden
DOI:
10.3934/mbe.2022450
ISSN:
1551-0018
Entstehung:
Anmerkungen:
Beschreibung:
<jats:p xml:lang="fr"><abstract><p>The problem of minimizing makespan (maximum completion time) on uniform machines with restricted assignment is considered. The machines differ in their speeds and functionalities. Each job has a set of machines to which it can be assigned, called its processing set. The goal is to finish the jobs as soon as possible. There exist 4/3-approximation algorithms for the cases of inclusive and tree-hierarchical assignment restrictions, under an assumption that machines with higher capabilities also run at higher speeds. We eliminate the assumption and present algorithms with approximation ratios 2 and 4/3 for both cases.</p></abstract></jats:p>