SCHEDULING PARALLEL DEDICATED MACHINES UNDER RESOURCE CONSTRAINTS
Professor Vitaly Strusevich, School of Computing and Mathematical Sciences, University of Greenwich

Abstract: The following scheduling model is considered. The jobs of a given set are to be processed on several machines. The machines are parallel and dedicated, i.e., each job requires one stage of processing to be performed on a prescribed machine.

Some jobs may require additional renewable resources at any time of their processing. Several jobs can be run in parallel on the corresponding machines if their total consumption of each resource does not exceed the resource availability. For problems considered in this talk the objective function to be minimized is the makespan, i.e., the maximum completion time. The models under consideration can be applied to distribution of human resources in project management, to sharing additional tools in manufacturing, etc.

We present a number of polynomial-time algorithms, provide a fairly complete computational complexity classification of the relevant problems, and discuss and analyse approximation algorithms, including a polynomial-time approximation scheme.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 27 November 2001.

back