Paper Info
Title
An approximation algorithm for multi-agent scheduling on two uniform parallel machines
Abstract
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+ \frac{\sqrt{17}-3}{4}\) times its optimal makespan, in which \(\frac{\sqrt{17}-3}{4}\) is the relative error of the LPT rule for the single-agent problem \(Q2||C_{\max }\). Furthermore, an example is introduced to show the tightness of the performance analysis.
Year
DOI
Venue
2019
10.1007/s11590-018-1298-y
Optimization Letters
Keywords
Field
DocType
Scheduling, Multi-agent, LPT, Makespan
Approximation algorithm,Discrete mathematics,Mathematical optimization,Job shop scheduling,Scheduling (computing),Mathematics,Approximation error
Journal
Volume
Issue
ISSN
13.0
4.0
1862-4480
Citations 
PageRank 
References 
0
0.34
20
Authors
3
Name
Order
Citations
PageRank
Manzhan Gu1364.99
Xiwen Lu218221.03
Jinwei Gu368739.49