A note on minimizing the sum of squares of machine completion times on two identical parallel machines

被引：3

作者：

Walter, Rico ^{[1
]}

机构：

[1] Fraunhofer Inst Ind Math ITWM, Dept Optimizat, Fraunhofer Pl 1, D-67663 Kaiserslautern, Germany

来源：

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH | 2017年 / 25卷 / 01期

关键词：

Scheduling; Identical parallel machines; Sum of squares of machine completion times; Makespan; Approximation algorithms; PARTITION PROBLEM; BOUNDS; LPT;

D O I：

10.1007/s10100-015-0429-0

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this short note, we address the coherence between minimizing the sum of squares of machine completion times and minimizing makespan on two identical parallel machines. We show equivalence of the two objectives and identify interesting and useful relations which allow us to transfer worst-case ratios of approximation algorithms from one problem to the other.

引用

页码：139 / 144

页数：6

共 10 条

[1]

Alon N, 1997, PROCEEDINGS OF THE EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P493

[2]

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

[3]

Chandra A. K., 1975, SIAM Journal on Computing, V4, P249, DOI 10.1137/0204021

[4] RECORD ALLOCATION FOR MINIMIZING EXPECTED RETRIEVAL COSTS ON DRUM-LIKE STORAGE DEVICES [J].

CODY, RA ;

COFFMAN, EG .

JOURNAL OF THE ACM, 1976, 23 (01) :103-115

[5] A tight upper bound for the k-partition problem on ideal sets [J].

Goldberg, RR ;

Shapiro, J .

OPERATIONS RESEARCH LETTERS, 1999, 24 (04) :165-173

[6] Partitioning under the Lp norm [J].

Goldberg, RR ;

Shapiro, J .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 123 (03) :585-592

[7] BOUNDS ON MULTIPROCESSING TIMING ANOMALIES [J].

GRAHAM, RL .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1969, 17 (02) :416-&

[8] An improved delayed-start LPT algorithm for a partition problem on two identical parallel machines [J].

Koulamas, Christos ;

Kyparisis, George J. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 187 (02) :660-666

[9] MULTIPROCESSOR SCHEDULING - COMBINING LPT AND MULTIFIT [J].

LEE, CY ;

MASSEY, JD .

DISCRETE APPLIED MATHEMATICS, 1988, 20 (03) :233-242

[10] TIGHTER BOUNDS ON A HEURISTIC FOR A PARTITION PROBLEM [J].

LEUNG, JYT ;

WEI, WD .

INFORMATION PROCESSING LETTERS, 1995, 56 (01) :51-57

← 1 →