Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data
From MaRDI portal
Publication:1767979
DOI10.1016/j.ic.2004.10.002zbMath1062.68144MaRDI 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
68W40: Analysis of algorithms
90B35: Deterministic scheduling theory in operations research
68M20: Performance evaluation, queueing, and scheduling in the context of computer systems
Related Items
Parallel solutions for ordinal scheduling with a small number of machines, Machine covering with combined partial information, On-line preemptive machine scheduling with \(\ell _p\) norm on two uniform machines, An improved delayed-start LPT algorithm for a partition problem on two identical parallel machines, A Lower Bound for the On-Line Preemptive Machine Scheduling with ℓ p Norm
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