COMPLEXITY OF SINGLE-MACHINE, MULTICRITERIA SCHEDULING PROBLEMS

被引：78

作者：

CHEN, CL

BULFIN, RL

机构：

[1] AUBURN UNIV,COLL ENGN,DEPT IND ENGN,207 DUNSTAN HALL,AUBURN,AL 36849

[2] MISSISSIPPI STATE UNIV,DEPT IND ENGN,MISSISSIPPI STATE,MS 39762

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1993年 / 70卷 / 01期

关键词：

COMPLEXITY; MULTIPLE CRITERIA; SCHEDULING; SINGLE MACHINE;

D O I：

10.1016/0377-2217(93)90236-G

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We examine the complexity of scheduling problems when more than one measure of performance is appropriate. The criteria we study are maximal tardiness, flowtime, number of tardy jobs, tardiness and the weighted counterparts of the last three measures. The machine environment is restricted to a single machine. Complexity results are given for secondary criterion, bicriteria and weighted criteria approaches for all combinations of measures. Of the problems examined, only six remain open.

引用

页码：115 / 125

页数：11

共 17 条

[1] [Anonymous], 1973, S THEORY SCHEDULING
[2] Baker K., 1974, INTRO SEQUENCING SCH
[3] Chen C. L., 1989, COMPUTERS OPERATIONS, V17, P1
[4] MINIMIZING TOTAL TARDINESS ON ONE MACHINE IS NP-HARD
DU, JZ
LEUNG, JYT
[J]. MATHEMATICS OF OPERATIONS RESEARCH, 1990, 15 (03) : 483 - 495
[5] ONE MACHINE SEQUENCING TO MINIMIZE MEAN FLOW TIME WITH MINIMUM NUMBER TARDY
EMMONS, H
[J]. NAVAL RESEARCH LOGISTICS, 1975, 22 (03) : 585 - 592
[6] NOTE ON A SCHEDULING PROBLEM WITH DUAL CRITERIA
EMMONS, H
[J]. NAVAL RESEARCH LOGISTICS, 1975, 22 (03) : 615 - 616
[7] French S., 1986, SEQUENCING SCHEDULIN
[8] Garey MR., 1979, COMPUTERS INTRACTABI
[9] Goicoechea A., 1982, MULTIOBJECTIVE DECIS
[10] Graham R. L., 1979, Discrete Optimisation, P287

← 1 2 →