Approximation Algorithms for Time Constrained Scheduling

AbstractIn this paper we consider the following time constrained scheduling problem. Given a set of jobsJwith execution timese(j)∈(0, 1] and an undirected graphG=(J, E), we consider the problem to find a schedule for the jobs such that adjacent jobs (j, j′)∈Eare 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