FIXED JOB SCHEDULING WITH 2 TYPES OF PROCESSORS
成果类型：
Article
署名作者：
DONDETI, VR; EMMONS, H
署名单位：
University System of Ohio; Case Western Reserve University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.40.1.S76
发表日期：
1992
页码：
S76-S85
关键词：
摘要：
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.