Fixed job scheduling with two types of processors

Fixed job scheduling with two types of processors

0.00 Avg rating0 Votes
Article ID: iaor19921723
Country: United States
Volume: 40
Start Page Number: 69
End Page Number: 77
Publication Date: Jan 1992
Journal: Operations Research
Authors: ,
Keywords: networks: scheduling
Abstract:

The authors consider a scheduling problem that involves two types of processors, but three types of jobs. Each job has a fixed start time and a fixed completion time, and falls into one of three types. Jobs of type 1 can be done only by type-1 processors, type-2 jobs only by type-2 processors, and type-0 jobs by either type of processors. The authors present a polynomial algorithm for finding the minimal cost combination of the two types of processors required to complete all jobs. The steps of the algorithm consist of constructing a job schedule network, transforming it into a single-commodity flow problem and finding the maximal flow through it.

Reviews

Required fields are marked *. Your email address will not be published.