The complexity of mean flow time scheduling problems with release times

被引：19

作者：

Baptiste, Philippe ^{[1
]}

Brucker, Peter

Chrobak, Marek

Durr, Christoph

Kravchenko, Svetlana A.

Sourd, Francis

机构：

[1] Ecole Polytech, CNRS, LIX, F-91128 Palaiseau, France

[2] Univ Osnabruck, Fachbereich Math Informat, D-49069 Osnabruck, Germany

[3] Univ Calif Riverside, Dept Comp Sci, Riverside, CA 92521 USA

[4] United Inst Informat Problems, Minsk 220012, BELARUS

[5] Univ Paris 06, CNRS, LIP6, F-75005 Paris, France

来源：

JOURNAL OF SCHEDULING | 2007年 / 10卷 / 02期

基金：

美国国家科学基金会;

关键词：

scheduling theory; preemption; linear programming;

D O I：

10.1007/s10951-006-0006-4

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

We study the problem of preemptive scheduling of n} jobs with given release times on m identical parallel machines. The objective is to minimize the average flow time. In this paper, show that when all jobs have equal processing times then the problem can be solved in polynomial time using linear programming. Our algorithm can also be applied to the open-shop problem with release times and unit processing times. For the general case (when processing times are arbitrary), we show that the problem is unary NP-hard.

引用

页码：139 / 146

页数：8

共 11 条

[1]

Baptiste P., 1999, Journal of Scheduling, V2, P245, DOI 10.1002/(SICI)1099-1425(199911/12)2:6<245::AID-JOS28>3.0.CO

[2]

2-5

[3]

BAPTISTE P, IN PRESS J SCHEDULIN

[4]

Brucker P., 1993, ZOR, Methods and Models of Operations Research, V37, P59, DOI 10.1007/BF01415528

[5] MINIMIZING MEAN FLOW TIME WITH RELEASE TIME CONSTRAINT [J].

DU, JZ ;

LEUNG, JYT ;

YOUNG, GH .

THEORETICAL COMPUTER SCIENCE, 1990, 75 (03) :347-355

[6] PREEMPTIVE SCHEDULING OF EQUAL LENGTH JOBS ON 2 MACHINES TO MINIMIZE MEAN FLOW TIME [J].

HERRBACH, LA ;

LEUNG, JYT .

OPERATIONS RESEARCH, 1990, 38 (03) :487-494

[7] On the complexity of minimizing the number of late jobs in unit time open shop [J].

Kravchenko, SA .

DISCRETE APPLIED MATHEMATICS, 2000, 100 (1-2) :127-132

[8] PREEMPTIVE SCHEDULING TO MINIMIZE MEAN WEIGHTED FLOW TIME [J].

LEUNG, JYT ;

YOUNG, GH .

INFORMATION PROCESSING LETTERS, 1990, 34 (01) :47-50

[9]

SCHRIJVER A, 2003, COMBINATIORIAL OPTIM

[10] A STRONGLY POLYNOMIAL ALGORITHM TO SOLVE COMBINATORIAL LINEAR-PROGRAMS [J].

TARDOS, E .

OPERATIONS RESEARCH, 1986, 34 (02) :250-256

← 1 2 →