Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines

Authors

  • Tytus Pikies Dept. of Algorithms and System Modeling, Gdańsk University of Technology
  • Krzysztof Turowski Theoretical Computer Science Dept., Jagiellonian University
  • Marek Kubale Dept. of Algorithms and System Modeling, Gdańsk University of Technology

Keywords:

Classical Planning Techniques And Analysis

Abstract

In this paper we consider a problem of job scheduling on parallel machines with a presence of incompatibilities between jobs. 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. We provide several results concerning schedules, optimal or approximate with respect to the two most popular criteria of optimality: Cmax (makespan) and ∑Cj (total completion time). We consider a variety of machine types in our paper: identical, uniform, and unrelated. Our results consist of delimitation of the easy (polynomial) and NP-hard problems within these constraints. We also provide algorithms, either polynomial exact algorithms for the easier problems, or algorithms with a guaranteed constant worst-case approximation ratio. In particular, we fill the gap on research for the problem of finding a schedule with the smallest ∑Cj on uniform machines. We address this problem by developing a linear programming relaxation technique with an appropriate rounding, which to our knowledge is a novelty for this criterion in the considered setting.

Downloads

Published

2021-05-17

How to Cite

Pikies, T., Turowski, K., & Kubale, M. (2021). Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 262-270. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/15970