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