Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time

被引：9

作者：

Batsyn, Mikhail ^{[1
]}

Goldengorin, Boris ^{[2
,3
]}

Pardalos, Panos M. ^{[1
,2
]}

Sukhov, Pavel ^{[1
]}

机构：

[1] Natl Res Univ, Higher Sch Econ, Lab Algorithms & Technol Networks Anal, Niznhy Novgorod 603093, Russia

[2] Univ Florida, Dept Ind & Syst Engn, Gainesville, FL 32611 USA

[3] Univ Groningen, Dept Operat Management & Operat Res, NL-9747 AE Groningen, Netherlands

来源：

OPTIMIZATION METHODS & SOFTWARE | 2014年 / 29卷 / 05期

关键词：

single machine scheduling; weighted shortest remaining processing time; WSRPT rule; efficient heuristic; RELEASE DATES; AVAILABILITY; ALGORITHM;

D O I：

10.1080/10556788.2013.854360

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The preemptive single machine scheduling problem of minimizing the total weighted completion time with arbitrary processing times and release dates is an important NP-hard problem in scheduling theory. In this paper we present an efficient high-quality heuristic for this problem based on the Weighted Shortest Remaining Processing Time (WSRPT) rule. The running time of the suggested algorithm increases only as a square of the number of jobs. Our computational study shows that very large size instances might be treated within extremely small CPU times and the average error is always less than 0.1%.

引用

页码：955 / 963

页数：9

共 24 条

[1]

Akker J.M., 2010, J SCHEDULING, V13, P561

[2] Online scheduling of a single machine to minimize total weighted completion time [J].

Anderson, EJ ;

Potts, CN .

MATHEMATICS OF OPERATIONS RESEARCH, 2004, 29 (03) :686-697

[3]

[Anonymous], 1983, SOV MATH DOKL, V27, P620

[4]

[Anonymous], 2003, COMBINATORIAL OPTIMI

[5] SCHEDULING WITH RELEASE DATES ON A SINGLE-MACHINE TO MINIMIZE TOTAL WEIGHTED COMPLETION-TIME [J].

BELOUADAH, H ;

POSNER, ME ;

POTTS, CN .

DISCRETE APPLIED MATHEMATICS, 1992, 36 (03) :213-231

[6]

BIETHAN J, 1995, EVOLUTIONARY ALGORIT

[7]

Brucker P., 2004, HDB SCHEDULING ALGOR

[8]

Brucker P., Complexity Results for Scheduling Problems

[9] Scheduling jobs with equal processing times and time windows on identical parallel machines [J].

Brucker, Peter ;

Kravchenko, Svetlana A. .

JOURNAL OF SCHEDULING, 2008, 11 (04) :229-237

[10]

Chen B., 1998, Handbook of Combinatorial Optimization, P1493, DOI [DOI 10.1007/978-1-4613-0303-9_25, 10.1007/978-1-4613-0303-925, DOI 10.1007/978-1-4613-0303-925]

← 1 2 3 →