A new approximation algorithm for UET-scheduling with chain-type precedence constraints

CSpace

	A new approximation algorithm for UET-scheduling with chain-type precedence constraints
	Han, JY ; Wen, JJ ; Zhang, GC
	1998-09-01
发表期刊	COMPUTERS & OPERATIONS RESEARCH
ISSN	0305-0548
卷号	25 期号:9 页码:767-771
摘要	In this paper a new approximation algorithm with worst case performance ratio 3/2 is presented for the problem of scheduling unit execution time jobs on two parallel machines with the objective of minimizing the makespan where each job can be processed on only one machine and there are chain-type precedence constraints in the jobs. This result answers an open problem in Jansen et al. [Jansen, K., Woeginger, G. J. and Yu, Z., UET-Scheduling with chain-type precedence constraints. Report 277, Technische Universitat Graz, Institut fur Mathematik, Graz, Austria, 1993.]: "Does there exist a polynomial time heuristic with worst-case guarantee better than 5/3 for the problem U2Chain?". The new approximation algorithm is also applied to the problem J2\pmtn\C-max. (C) 1998 Elsevier Science Ltd. All rights reserved.
关键词	precedence constraints parallel machines makespan approximation algorithm
语种	英语
WOS研究方向	Computer Science ; Engineering ; Operations Research & Management Science
WOS类目	Computer Science, Interdisciplinary Applications ; Engineering, Industrial ; Operations Research & Management Science
WOS记录号	WOS:000074574700007
出版者	PERGAMON-ELSEVIER SCIENCE LTD
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/13740
专题	中国科学院数学与系统科学研究院
通讯作者	Han, JY
作者单位	1.Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China 2.Graz Tech Univ, Inst Math, A-8010 Graz, Austria
推荐引用方式 GB/T 7714	Han, JY,Wen, JJ,Zhang, GC. A new approximation algorithm for UET-scheduling with chain-type precedence constraints[J]. COMPUTERS & OPERATIONS RESEARCH,1998,25(9):767-771.
APA	Han, JY,Wen, JJ,&Zhang, GC.(1998).A new approximation algorithm for UET-scheduling with chain-type precedence constraints.COMPUTERS & OPERATIONS RESEARCH,25(9),767-771.
MLA	Han, JY,et al."A new approximation algorithm for UET-scheduling with chain-type precedence constraints".COMPUTERS & OPERATIONS RESEARCH 25.9(1998):767-771.