The time dependent machine makespan problem is strongly NP-complete

被引：9

作者：

Cheng, TCE ^{[1
]}

Ding, Q

机构：

[1] Hong Kong Polytech Univ, Off Vice President Res & Postgrad Studies, Kowloon, Peoples R China

[2] Hong Kong Polytech Univ, Dept Management, Kowloon, Peoples R China

来源：

COMPUTERS & OPERATIONS RESEARCH | 1999年 / 26卷 / 08期

关键词：

scheduling; sequencing; time dependence; computational complexity;

D O I：

10.1016/S0305-0548(98)00093-8

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The computational complexity of the problem of scheduling a set of start-time dependent tasks with deadlines and identical decreasing rates of processing times on a single machine to minimize the makespan is open. In this paper we show that the problem is strongly NP-complete by a reduction from 3-Partition. (C) 1999 Published by Elsevier Science Ltd. All rights reserved.

引用

页码：749 / 754

页数：6

共 8 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2] A NOTE ON SINGLE-PROCESSOR SCHEDULING WITH TIME-DEPENDENT EXECUTION TIMES [J].

CHEN, ZL .

OPERATIONS RESEARCH LETTERS, 1995, 17 (03) :127-129

[3] The complexity of scheduling starting time dependent tasks with release times [J].

Cheng, TCE ;

Ding, Q .

INFORMATION PROCESSING LETTERS, 1998, 65 (02) :75-79

[4] RESOURCE OPTIMAL-CONTROL IN SOME SINGLE-MACHINE SCHEDULING PROBLEMS [J].

CHENG, TCE ;

JANIAK, A .

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1994, 39 (06) :1243-1246

[5] The complexity of single machine scheduling with two distinct deadlines and identical decreasing rates of processing times [J].

Cheng, TCE ;

Ding, Q .

COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1998, 35 (12) :95-100

[6]

CHENG TCE, 1998, 02978 HONG KONG POL

[7] COMPLEXITY OF SCHEDULING TASKS WITH TIME-DEPENDENT EXECUTION TIMES [J].

HO, KIJ ;

LEUNG, JYT ;

WEI, WD .

INFORMATION PROCESSING LETTERS, 1993, 48 (06) :315-320

[8] SCHEDULING WITH TIME-DEPENDENT EXECUTION TIMES [J].

WOEGINGER, GJ .

INFORMATION PROCESSING LETTERS, 1995, 54 (03) :155-156

← 1 →