Fixed Job Scheduling with Two Types of Processors

V. R. Dondeti and Hamilton Emmons
Additional contact information
V. R. Dondeti: Norfolk State University, Norfolk, Virginia
Hamilton Emmons: Case Western Reserve University, Cleveland, Ohio

Operations Research, 1992, vol. 40, issue 1-supplement-1, S76-S85

Abstract: We 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. We 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.

Keywords: networks/graphs; flow algorithms; flows and arc-disjoint paths of networks; production/scheduling; sequencing; assigning two types of processors to three types (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.1.S76 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:40:y:1992:i:1-supplement-1:p:s76-s85

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().