JACKSON RULE FOR SINGLE-MACHINE SCHEDULING - MAKING A GOOD HEURISTIC BETTER

被引：102

作者：

HALL, LA ^{[1
]}

SHMOYS, DB ^{[1
]}

机构：

[1] CORNELL UNIV,SCH OPERAT RES & IND ENGN,ITHACA,NY 14853

来源：

MATHEMATICS OF OPERATIONS RESEARCH | 1992年 / 17卷 / 01期

关键词：

JOB SHOP SCHEDULING; ONE MACHINE; DETERMINISTIC;

D O I：

10.1287/moor.17.1.22

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider the scheduling problem in which jobs with release dates and delivery times are to be scheduled on one machine. We present a 4/3-approximation algorithm for the problem with precedence constraints among the jobs, and two polynomial approximation schemes for the problem without precedence constraints. At the core of each of the algorithms presented is Jackson's Rule-a simple but seemingly robust heuristic for the problem.

引用

页码：22 / 35

页数：14

共 14 条

[1] SCHEDULING UNIT-TIME TASKS WITH ARBITRARY RELEASE TIMES AND DEADLINES [J].