Search
Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines: Complexity and Algorithms
Abstract
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.
Citations
-
4
CrossRef
-
0
Web of Science
-
5
Scopus
Authors (3)
-
Krzysztof Turowski dr inż.
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach
- Published in:
-
ARTIFICIAL INTELLIGENCE
no. 309,
ISSN: 0004-3702 - Language:
- English
- Publication year:
- 2022
- Bibliographic description:
- Pikies T., Turowski K., Kubale M.: Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines: Complexity and Algorithms// ARTIFICIAL INTELLIGENCE -, (2022), s.103711-
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.artint.2022.103711
- Verified by:
- Gdańsk University of Technology
seen 186 times
Recommended for you
Approximation algorithms for job scheduling with block-type conflict graphs
- H. Furmańczyk,
- T. Pikies,
- I. Sokołowska
- + 1 authors