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

被引：0
作者：
Rico Walter
机构：
[1] Fraunhofer Institute for Industrial Mathematics ITWM,Department of Optimization
来源：
Central European Journal of Operations Research | 2017年 / 25卷
关键词：
Scheduling; Identical parallel machines; Sum of squares of machine completion times; Makespan; Approximation algorithms;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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
页数：5
相关论文
共 15 条
[1]  
Chandra AK(1975)Worst-case analysis of a placement algorithm related to storage allocation SIAM J Comput 4 249-263
[2]  
Wong CK(1976)Record allocation for minimizing expected retrieval costs on drum-like storage devices J ACM 23 103-115
[3]  
Cody RA(1999)A tight upper bound for the Oper Res Lett 24 164-173
[4]  
Coffman EG(2000)-partition problem on ideal sets Eur J Oper Res 123 585-592
[5]  
Goldberg RR(1969)Partitioning under the SIAM J Appl Math 17 416-429
[6]  
Shapiro J(2008) norm Eur J Oper Res 187 660-666
[7]  
Goldberg RR(1988)Bounds on multiprocessing timing anomalies Discret Appl Math 20 233-242
[8]  
Shapiro J(1995)An improved delayed-start LPT algorithm for a partition problem on two identical parallel machines Inf Process Lett 56 51-57
[9]  
Graham RL(undefined)Multiprocessor scheduling: combining LPT and MULTIFIT undefined undefined undefined-undefined
[10]  
Koulamas C(undefined)Tighter bounds on a heuristic for a partition problem undefined undefined undefined-undefined
12