FIXED JOB SCHEDULING WITH 2 TYPES OF PROCESSORS

被引：17

作者：

DONDETI, VR ^{[1
]}

EMMONS, H ^{[1
]}

机构：

[1] CASE WESTERN RESERVE UNIV,CLEVELAND,OH 44106

来源：

OPERATIONS RESEARCH | 1992年 / 40卷

关键词：

D O I：

10.1287/opre.40.1.S76

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：S76 / S85

页数：10