Abstract
We consider scheduling problems in a multiprocessor system with incompatible jobs (two incompatible jobs cannot be processed by the same machine). We consider the problem to minimize the maximum job completion time, the makespan. This problem is NP-complete.
We present a number of polynomial time approximation algorithms for this problem where the job incompatibilities possess a special structure. As the incompatibilities form a graph on the set of jobs, our algorithms strongly rely on graph theoretic methods. We also solve an open problem by Biró, Hujter and Tuza on coloring precolored bipartite graphs.
We present a number of polynomial time approximation algorithms for this problem where the job incompatibilities possess a special structure. As the incompatibilities form a graph on the set of jobs, our algorithms strongly rely on graph theoretic methods. We also solve an open problem by Biró, Hujter and Tuza on coloring precolored bipartite graphs.
| Original language | English |
|---|---|
| Title of host publication | Graph-Theoretic Concepts in Computer Science |
| Editors | Ernst W. Mayr |
| Publisher | Springer |
| Pages | 37-49 |
| Number of pages | 13 |
| Volume | 657 |
| ISBN (Electronic) | 978-3-540-47554-5 |
| ISBN (Print) | 978-3-540-56402-7 |
| DOIs | |
| Publication status | Published - 1993 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|
Fingerprint
Dive into the research topics of 'Scheduling with incompatible jobs: Graph-Theoretic Concepts in Computer Science'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver