A new approximation algorithm for multi-agent scheduling to minimize makespan on two machines

DOI10.1007/s10951-015-0460-yzbMath1341.90061OpenAlexW2285763352MaRDI QIDQ283263

Manzhan Gu, Kejun Zhao, Xi-wen Lu

Publication date: 13 May 2016

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-015-0460-y

zbMATH Keywords

approximation algorithmmakespanidentical machinesmulti-agent schedulingperformance ratio vector

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

Two-agent parallel-machine scheduling with rejection, Two-agent vehicle scheduling problem on a line-shaped network, Two-agent scheduling on a single machine with release dates, An approximation algorithm for multi-agent scheduling on two uniform parallel machines, An algorithm for multi-agent scheduling to minimize the makespan on \(m\) parallel machines

Cites Work

• A decomposition scheme for single stage scheduling problems
• Analyzing scheduling with transient failures
• Approximation algorithms for multi-agent scheduling to minimize total weighted completion time
• A Lagrangian approach to single-machine scheduling problems with two competing agents
• Unbounded parallel-batching scheduling with two competitive agents
• Bounded parallel-batching scheduling with two competing agents
• Multi-agent scheduling on a single machine with max-form criteria
• Multi-agent single machine scheduling
• Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs
• Competitive Two-Agent Scheduling and Its Applications
• Scheduling Problems with Two Competing Agents
• Multiagent Scheduling
• Bounds on Multiprocessing Timing Anomalies