Scheduling of incompatible jobs on unrelated machines. (English) Zbl 0799.90066

Jansen, Klaus

Int. J. Found. Comput. Sci. 4, No. 4, 275-291 (1993).

Summary: We study a general scheduling problem, where each job \(j\in J\) has an execution time \(e(j,M_ i)\in \mathbb{R}^ +\) on a machine of type \(M_ i\in M\) and where we have an incompatibility relation between the jobs. Given a price \(p(M_ i)\in \mathbb{R}^ +\) for each machine of type \(M_ i\) and a deadline \(d\in\mathbb{R}^ +\), we consider the problem to select a minimum cost set of machines for which there exists a schedule with makespan at most \(d\). We propose an approximation method, where the solution is at most \(\sum^{| J|}_{i=1} {1\over i}= O(\log| J|)\) away from the optimum. The method is based on a graph theoretical problem which we have studied for several graph classes.

MSC:

90B35	Deterministic scheduling theory in operations research
68M20	Performance evaluation, queueing, and scheduling in the context of computer systems
68R10	Graph theory (including graph drawing) in computer science

Keywords:

incompatible jobs; scheduling; makespan