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.