Wyszukiwarka
Scheduling of identical jobs with bipartite incompatibility graphs on uniform machines. Computational experiments
Abstrakt
We consider the problem of scheduling unit-length jobs on three or four uniform parallel machines to minimize the schedule length or total completion time. We assume that the jobs are subject to some types of mutual exclusion constraints, modeled by a bipartite graph of a bounded degree. The edges of the graph correspond to the pairs of jobs that cannot be processed on the same machine. Although the problem is generally NP-hard, we show that our problem can be solved to optimality in polynomial time under some restrictions imposed on the number of machines, their speeds, and the structure of the incompatibility graph. The theoretical considerations are accompanied by computer experiments with a certain model of scheduling.
Cytowania
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Autorzy (4)
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.7494/dmms.2017.11.1-2.53
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Opublikowano w:
-
Decision Making in Manufacturing and Services
nr 11,
strony 53 - 61,
ISSN: 1896-8325 - Język:
- angielski
- Rok wydania:
- 2017
- Opis bibliograficzny:
- Duraj S., Kopeć P., Kubale M., Pikies T.: Scheduling of identical jobs with bipartite incompatibility graphs on uniform machines. Computational experiments// Decision Making in Manufacturing and Services. -Vol. 11., nr. 1-2 (2017), s.53-61
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.7494/dmms.2017.11.1-2.53
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 191 razy