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

DOI10.1007/S10951-015-0460-YMaRDI QIDQ283263zbMATHOpenAlexFDO

Authors Kejun Zhao, Manzhan Gu, Xiwen 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

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

Recommendations

• An algorithm for multi-agent scheduling to minimize the makespan on \(m\) parallel machines
• An approximation algorithm for multi-agent scheduling on two uniform parallel machines
• Two approximation algorithms for two-agent scheduling on parallel machines to minimize makespan
• Approximation schemes for two-agent scheduling on parallel machines
• Approximation algorithms for multi-agent scheduling to minimize total weighted completion time

Cites work

• A Lagrangian approach to single-machine scheduling problems with two competing agents
• 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
• Bounded parallel-batching scheduling with two competing agents
• Bounds on Multiprocessing Timing Anomalies
• Competitive two-agent scheduling and its applications
• Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs
• Multi-agent scheduling on a single machine with max-form criteria
• Multi-agent single machine scheduling
• Multiagent scheduling. Models and algorithms
• Scheduling Problems with Two Competing Agents
• Unbounded parallel-batching scheduling with two competitive agents

Cited in

(11)

• Approximation schemes for two-agent scheduling on parallel machines
• Multi-agent scheduling on a single machine with a fixed number of competing agents to minimize the weighted sum of number of tardy jobs and makespans
• Scheduling two interfering job sets on identical parallel machines with makespan and total completion time minimization
• An approximation algorithm for scheduling on three dedicated machines
• Approximation algorithms for multi-agent scheduling to minimize total weighted completion time
• An approximation algorithm for multi-agent scheduling on two uniform parallel machines
• Two-agent scheduling on a single machine with release dates
• Two-agent parallel-machine scheduling with rejection
• An algorithm for multi-agent scheduling to minimize the makespan on \(m\) parallel machines
• Two approximation algorithms for two-agent scheduling on parallel machines to minimize makespan
• Two-agent vehicle scheduling problem on a line-shaped network

This page was built for publication: A new approximation algorithm for multi-agent scheduling to minimize makespan on two machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q283263)