Optimal online algorithm for scheduling on two identical machines with machine availability constraints.

DOI10.1016/S0020-0190(02)00211-9zbMath1043.90033OpenAlexW2046781886MaRDI QIDQ1853092

Zhiyi Tan, Yong He

Publication date: 21 January 2003

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00211-9

zbMATH Keywords

SchedulingCompetitive ratioAnalysis of algorithmsOnline

Mathematics Subject Classification ID

Analysis of algorithms (68W40) 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 (12)

Online and semi-online scheduling to minimize makespan on single machine with an availability constraint ⋮ Semi-online scheduling on a single machine with unexpected breakdown ⋮ A SEMI-ON-LINE SCHEDULING PROBLEM OF TWO PARALLEL MACHINES WITH COMMON MAINTENANCE TIME ⋮ Online algorithms for scheduling with machine activation cost on two uniform machines ⋮ An on-line scheduling problem of parallel machines with common maintenance time ⋮ An improved semi-online algorithm for scheduling on a single machine with unexpected breakdown ⋮ Minimizing total weighted completion time with an unexpected machine unavailable interval ⋮ Scheduling on same-speed processors with at most one downtime on each machine ⋮ Multi-machine scheduling with deteriorating jobs and scheduled maintenance ⋮ An optimal semi-online algorithm for 2-machine scheduling with an availability constraint ⋮ Optimal algorithms for online scheduling on parallel machines to minimize the makespan with a periodic availability constraint ⋮ Online scheduling to minimize modified total tardiness with an availability constraint

Cites Work

• Unnamed Item
• Parallel machines scheduling with nonsimultaneous machine available time
• Two-machine flowshop scheduling with availability constraints
• The worst-case analysis of the MULTIFIT algorithm for scheduling nonsimultaneous parallel machines
• Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint
• Current trends in deterministic scheduling
• Two-machine flowshop scheduling with consecutive availability constraints
• Parallel machines scheduling with machine shutdowns
• A note on parallel machine scheduling with non-simultaneous machine available time

This page was built for publication: Optimal online algorithm for scheduling on two identical machines with machine availability constraints.