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

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.


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
Full Text: DOI