An approximation algorithm for multi-agent scheduling on two uniform parallel machines

doi:10.1007/s11590-018-1298-y

CORC > 上海财经大学 > 上海财经大学

	An approximation algorithm for multi-agent scheduling on two uniform parallel machines
	Gu, Manzhan 1; Lu, Xiwen 2; Gu, Jinwei 3
刊名	OPTIMIZATION LETTERS
	2019-06
卷号	13 期号:4 页码:907-933
关键词	Scheduling Multi-agent LPT Makespan
ISSN号	1862-4472
DOI	10.1007/s11590-018-1298-y
英文摘要	This paper considers a multi-agent scheduling problem, in which each agent has a set of non-preemptive jobs, and all jobs are to be processed on two uniform parallel machines with the objective to minimize the makespan of each agent. Given an instance of the multi-agent scheduling problem, we first devise a measure on the optimal makespan of the single-agent instance for each agent. Then an approximation algorithm is proposed for the multi-agent scheduling problem, in which agents are scheduled in the non-decreasing order of the measure values, and all jobs of each agent are scheduled generally subject to the longest processing time first (LPT) rule. In the obtained schedule, we prove the makespan of the ith completed agent is at most i+times its optimal makespan, in which is the relative error of the LPT rule for the single-agent problem Q2\|\|Cmax. Furthermore, an example is introduced to show the tightness of the performance analysis.
WOS研究方向	Operations Research & Management Science ; Mathematics
语种	英语
出版者	SPRINGER HEIDELBERG
WOS记录号	WOS:000467500700018
内容类型	期刊论文
源URL	[http://10.2.47.112/handle/2XS4QKH4/233]
专题	上海财经大学
通讯作者	Gu, Jinwei
作者单位	1.Shanghai Univ Finance & Econ, Sch Math, Shanghai, Peoples R China; 2.East China Univ Sci & Technol, Dept Math, Shanghai, Peoples R China; 3.Shanghai Univ Elect Power, Sch Econ & Management, Shanghai, Peoples R China
推荐引用方式 GB/T 7714	Gu, Manzhan,Lu, Xiwen,Gu, Jinwei. An approximation algorithm for multi-agent scheduling on two uniform parallel machines[J]. OPTIMIZATION LETTERS,2019,13(4):907-933.
APA	Gu, Manzhan,Lu, Xiwen,&Gu, Jinwei.(2019).An approximation algorithm for multi-agent scheduling on two uniform parallel machines.OPTIMIZATION LETTERS,13(4),907-933.
MLA	Gu, Manzhan,et al."An approximation algorithm for multi-agent scheduling on two uniform parallel machines".OPTIMIZATION LETTERS 13.4(2019):907-933.