Publisher: Academic Press
ISSN: 0890-5401
Source: Information and Computation, Vol.132, Iss.2, 1997-02, pp. : 85-108
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
Abstract
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.