Wyszukiwarka
Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines: Complexity and Algorithms
Abstrakt
In this paper, the problem of scheduling on parallel machines with a presence of incompatibilities between jobs is considered. The incompatibility relation can be modeled as a complete multipartite graph in which each edge denotes a pair of jobs that cannot be scheduled on the same machine. The paper provides several results concerning schedules, optimal or approximate with respect to the two most popular criteria of optimality: (makespan) and (total completion time). The problems are considered for a variety of machine types: identical, uniform and unrelated. The results consist of delimitation of the easy (polynomial) and NP-hard problems within these constraints. Also, polynomial-time exact algorithms are provided for easier problems and algorithms with a guaranteed constant worst-case approximation ratio for harder ones. In particular, there is provided a polynomial-time approximation scheme (PTAS) for scheduling with respect to on uniform machines, when the number of parts (i.e. sets of vertices constituting the mentioned graph) is bounded. The problem is addressed by developing a linear programming relaxation technique with appropriate rounding. This technique together with an exhaustive search (albeit in a manner controlled by the precision parameter) allows to provide the desired algorithm. For a PTAS is provided for the case of unit time jobs, but when the number of parts is part of the input. Interestingly, the latter result shows a connection between the considered problem of scheduling and covering problems.
Cytowania
-
4
CrossRef
-
0
Web of Science
-
5
Scopus
Autorzy (3)
-
Krzysztof Turowski dr inż.
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach
- Opublikowano w:
-
ARTIFICIAL INTELLIGENCE
nr 309,
ISSN: 0004-3702 - Język:
- angielski
- Rok wydania:
- 2022
- Opis bibliograficzny:
- Pikies T., Turowski K., Kubale M.: Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines: Complexity and Algorithms// ARTIFICIAL INTELLIGENCE -, (2022), s.103711-
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.artint.2022.103711
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 181 razy
Publikacje, które mogą cię zainteresować
Approximation algorithms for job scheduling with block-type conflict graphs
- H. Furmańczyk,
- T. Pikies,
- I. Sokołowska
- + 1 autorów