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 ().