COMPLETION-TIME VARIANCE MINIMIZATION ON A SINGLE-MACHINE IS DIFFICULT

被引：103

作者：

KUBIAK, W

机构：

[1] Faculty of Business Administration, Memorial University of Newfoundland, St. John's

来源：

OPERATIONS RESEARCH LETTERS | 1993年 / 14卷 / 01期

基金：

加拿大自然科学与工程研究理事会;

关键词：

SCHEDULING; VARIANCE; NP-COMPLETENESS;

D O I：

10.1016/0167-6377(93)90019-D

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The complexity of the completion time variance minimization (CTV) problem on a single machine has been open since the paper by Merten and Muller (Management Science 18 (1972)). In this paper we prove that the CTV problem is NP-hard.

引用

页码：49 / 59

页数：11

共 13 条

[1] SIMULTANEOUS MINIMIZATION OF MEAN AND VARIATION OF FLOW TIME AND WAITING TIME IN SINGLE-MACHINE SYSTEMS [J].

BAGCHI, U .

OPERATIONS RESEARCH, 1989, 37 (01) :118-125

[2] SEQUENCING WITH EARLINESS AND TARDINESS PENALTIES - A REVIEW [J].

BAKER, KR ;

SCUDDER, GD .

OPERATIONS RESEARCH, 1990, 38 (01) :22-36

[3]

CAI X, 1991, VARIANCE MINIMIZATIO

[4] ON THE MINIMIZATION OF COMPLETION-TIME VARIANCE WITH A BICRITERIA EXTENSION [J].

DE, P ;

GHOSH, JB ;

WELLS, CE .

OPERATIONS RESEARCH, 1992, 40 (06) :1148-1155

[5] MINIMIZING WAITING TIME VARIANCE IN SINGLE MACHINE PROBLEM [J].

EILON, S ;

CHOWDHURY, IG .

MANAGEMENT SCIENCE, 1977, 23 (06) :567-575

[6] PROOF OF A CONJECTURE OF SCHRAGE ABOUT THE COMPLETION-TIME VARIANCE PROBLEM [J].

HALL, NG ;

KUBIAK, W .

OPERATIONS RESEARCH LETTERS, 1991, 10 (08) :467-472

[7]

KAHLBACHER HG, 1989, EUR J OPER RES, V43, P111

[8] MINIMIZING VARIATION OF FLOW TIME IN SINGLE-MACHINE SYSTEMS [J].

KANET, JJ .

MANAGEMENT SCIENCE, 1981, 27 (12) :1453-1459

[9]

Karp R. M., 1972, COMPLEXITY COMPUTER, P85

[10]

KUBIAK W, 1991, NEW RESULTS COMPLETI

← 1 2 →