Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data

DOI10.1016/j.ic.2004.10.002zbMath1062.68144OpenAlexW1969869187MaRDI QIDQ1767979

Leah Epstein, Zhiyi Tan, Yong He

Publication date: 8 March 2005

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2004.10.002

zbMATH Keywords

SchedulingCompetitive ratioAnalysis of algorithmSemi-online

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (5)

A Lower Bound for the On-Line Preemptive Machine Scheduling with ℓ p Norm ⋮ Parallel solutions for ordinal scheduling with a small number of machines ⋮ An improved delayed-start LPT algorithm for a partition problem on two identical parallel machines ⋮ Machine covering with combined partial information ⋮ On-line preemptive machine scheduling with \(\ell _p\) norm on two uniform machines

Cites Work

• Unnamed Item
• Unnamed Item
• The exact LPT-bound for maximizing the minimum completion time
• Semi on-line algorithms for the partition problem
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• Bin stretching revisited
• Ordinal on-line scheduling for maximizing the minimum machine completion time
• Ordinal algorithms for packing with target center of gravity
• Optimal preemptive semi-online scheduling to minimize makespan on two related machines
• Ordinal algorithms for parallel machine scheduling
• Bin packing using semi-ordinal data
• On the Meaningfulness of Optimal Solutions to Scheduling Problems: Can an Optimal Solution be Nonoptimal?
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• Analysis of Greedy Solutions for a Replacement Part Sequencing Problem
• Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation
• On-line machine covering
• Ancient and new algorithms for load balancing in the \(\ell_p\) norm
• Semi-on-line scheduling problems for maximizing the minimum machine completion time
• Randomized on-line scheduling on two uniform machines
• Semi-on-line scheduling with ordinal data on two uniform machines

This page was built for publication: Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data