SOME NEW EFFICIENT METHODS TO SOLVE THE N/1/RI/SIGMA-TI SCHEDULING PROBLEM

被引：22

作者：

CHU, C ^{[1
]}

PORTMANN, MC ^{[1
]}

机构：

[1] ECOLE MINES NANCY,F-54042 NANCY,FRANCE

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1992年 / 58卷 / 03期

关键词：

ONE-MACHINE SCHEDULING; TOTAL TARDINESS MINIMIZATION; APPROXIMATE ALGORITHMS; DOMINANT SUBSET;

D O I：

10.1016/0377-2217(92)90071-G

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we prove a sufficient condition for local optimality to solve the n/1/r(i)/SIGMA-T(i) scheduling problem which is known to be NP-hard. We then define a new dominant subset of schedules on the basis of this condition and propose several new approximate algorithms to construct schedules belonging to this subset. Numerical experiments enable us to compare them with classical approximate algorithms.

引用

页码：404 / 413

页数：10

共 19 条

[1]

Baker K., 1974, INTRO SEQUENCING SCH

[2]

Baker K.R., 1982, J OPER MANAGE, V3, P37

[3]

CHU C, 1989, INRIA1023 RAPP RECH

[4]

CHU C, 1990, SINGLE MACHINE SCHED