Approximation algorithms for time constrained scheduling

In this paper we consider the following time constrained scheduling problem. Given a set of jobs J with execution times e(j)∈(0, 1] and an undirected graph G=(J, E), we consider the problem to find a schedule for the jobs such that adjacent jobs (j,j´)∈E are assigned to different machines and that the total execution time for each machine is at most 1. The goal is to find a minimum number of machines to execute all jobs under this time constraint. This scheduling problem is a natural generalization of the classical bin packing problem. We propose and analyse several approximation algorithms with constant absolute worst case ratio for graphs that can be colored in polynomial time