Parallel machine scheduling to maximize the minimum load with nonsimultaneous machine available times

CSpace

	Parallel machine scheduling to maximize the minimum load with nonsimultaneous machine available times
	Lin, GH ; Yao, EY ; He, Y
	1998-03-01
发表期刊	OPERATIONS RESEARCH LETTERS
ISSN	0167-6377
卷号	22 期号:2-3 页码:75-81
摘要	We consider a generalized version of the classical parallel machine scheduling problem, in which the m machines are available at time a(j) greater than or equal to 0, j = 1, 2, ..., m. The objective function is to maximize the minimum machine completion time. Using the conventional weighting function technique, previously, a lower bound of 5/8 has been shown for the worst-case performance ratio of the famous Longest Processing Timing (LPT) approximation. In this paper, we develop a new method, called matching, and show that the worst-case performance ratio of LPT is exactly (2m - 1)/(3m - 2). We also give an instance to indicate the tightness of this ratio. (C) 1998 Elsevier Science B.V. All rights reserved.
关键词	multiprocessor scheduling approximation matching LPT
语种	英语
WOS研究方向	Operations Research & Management Science
WOS类目	Operations Research & Management Science
WOS记录号	WOS:000076602300004
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/13698
专题	中国科学院数学与系统科学研究院
通讯作者	Lin, GH
作者单位	1.Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China 2.Zhejiang Univ, Dept Appl Math, Hangzhou 310027, Peoples R China
推荐引用方式 GB/T 7714	Lin, GH,Yao, EY,He, Y. Parallel machine scheduling to maximize the minimum load with nonsimultaneous machine available times[J]. OPERATIONS RESEARCH LETTERS,1998,22(2-3):75-81.
APA	Lin, GH,Yao, EY,&He, Y.(1998).Parallel machine scheduling to maximize the minimum load with nonsimultaneous machine available times.OPERATIONS RESEARCH LETTERS,22(2-3),75-81.
MLA	Lin, GH,et al."Parallel machine scheduling to maximize the minimum load with nonsimultaneous machine available times".OPERATIONS RESEARCH LETTERS 22.2-3(1998):75-81.