SCHEDULING AROUND A SMALL COMMON DUE DATE

被引：86

作者：

HOOGEVEEN, JA

VANDEVELDE, SL

机构：

[1] Centre for Mathematics and Computer Science, 1009 AB Amsterdam

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1991年 / 55卷 / 02期

关键词：

SINGLE MACHINE SCHEDULING; NP-HARDNESS; PSEUDOPOLYNOMIAL ALGORITHM;

D O I：

10.1016/0377-2217(91)90228-N

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

A set of n jobs has to be scheduled on a single machine which can handle only one job at a time. Each job requires a given positive uninterrupted processing time and has a positive weight. The problem is to find a schedule that minimizes the sum of weighted deviations of the job completion times from a given common due date d, which is smaller than the sum of the processing times. We prove that this problem is NP-hard even if all job weights are equal. In addition, we present a pseudopolynomial algorithm that requires O(n2d) time and O(nd) space.

引用

页码：237 / 242

页数：6

共 11 条

[1]

BAGACHI U, 1987, NAV RES LOG, V34, P739

[2] MINIMIZING MEAN ABSOLUTE DEVIATION OF COMPLETION TIMES ABOUT A COMMON DUE DATE [J].

BAGCHI, U ;

SULLIVAN, RS ;

CHANG, YL .

NAVAL RESEARCH LOGISTICS, 1986, 33 (02) :227-240

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

BAKER, KR ;

SCUDDER, GD .

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

[4]

EMMONS H, 1987, NAV RES LOG, V34, P803, DOI 10.1002/1520-6750(198712)34:6<803::AID-NAV3220340605>3.0.CO

[5]

2-2

[6] ONE-PROCESSOR SCHEDULING WITH SYMMETRIC EARLINESS AND TARDINESS PENALTIES [J].

GAREY, MR ;

TARJAN, RE ;

WILFONG, GT .

MATHEMATICS OF OPERATIONS RESEARCH, 1988, 13 (02) :330-348

[7]

HALL NG, IN PRESS OPERATIONS, V39

[8] MINIMIZING THE AVERAGE DEVIATION OF JOB COMPLETION TIMES ABOUT A COMMON DUE DATE [J].

KANET, JJ .

NAVAL RESEARCH LOGISTICS, 1981, 28 (04) :643-651

[9]

Smith W.E., 1956, NAV RES LOGIST Q, V3, P59, DOI DOI 10.1002/NAV.3800030106

[10]

SZWARC W, 1989, NAV RES LOG, V36, P663, DOI 10.1002/1520-6750(198910)36:5<663::AID-NAV3220360510>3.0.CO

← 1 2 →