An efficient polynomial time approximation scheme for load balancing on uniformly related machines
From MaRDI portal
(Redirected from Publication:463715)
Abstract: We consider basic problems of non-preemptive scheduling on uniformly related machines. For a given schedule, defined by a partition of the jobs into m subsets corresponding to the m machines, C_i denotes the completion time of machine i. Our goal is to find a schedule which minimizes or maximizes sum_{i=1}^m C_i^p for a fixed value of p such that 0<p<infty. For p>1 the minimization problem is equivalent to the well-known problem of minimizing the ell_p norm of the vector of the completion times of the machines, and for 0<p<1 the maximization problem is of interest. Our main result is an efficient polynomial time approximation scheme (EPTAS) for each one of these problems. Our schemes use a non-standard application of the so-called shifting technique. We focus on the work (total size of jobs) assigned to each machine and introduce intervals of forbidden work. These intervals are defined so that the resulting effect on the goal function is sufficiently small. This allows the partition of the problem into sub-problems (with subsets of machines and jobs) whose solutions are combined into the final solution using dynamic programming. Our results are the first EPTAS's for this natural class of load balancing problems.
Recommendations
- A unified framework for designing EPTAS's for load balancing on parallel machines
- A unified framework for designing EPTAS for load balancing on parallel machines
- Publication:4938775
- An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
Cites work
- scientific article; zbMATH DE number 5764829 (Why is no real title available?)
- scientific article; zbMATH DE number 1306871 (Why is no real title available?)
- scientific article; zbMATH DE number 1182760 (Why is no real title available?)
- scientific article; zbMATH DE number 6472625 (Why is no real title available?)
- A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
- A polynomial-time approximation scheme for maximizing the minimum machine completion time
- All-norm approximation algorithms
- An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables
- Analysis of Greedy Solutions for a Replacement Part Sequencing Problem
- Ancient and new algorithms for load balancing in the \(\ell_p\) norm
- Approximation schemes for covering and packing problems in image processing and VLSI
- Approximation schemes for scheduling and covering on unrelated machines
- Approximation schemes for scheduling on parallel machines
- Approximation schemes for scheduling on uniformly related and identical parallel machines
- Bounds for Certain Multiprocessing Anomalies
- Bounds for LPT Schedules on Uniform Processors
- Exact and Approximate Algorithms for Scheduling Nonidentical Processors
- Integer Programming with a Fixed Number of Variables
- Maximizing the minimum load for selfish agents
- On the efficiency of polynomial time approximation schemes
- Parametrized complexity theory.
- Record Allocation for Minimizing Expected Retrieval Costs on Drum-Like Storage Devices
- Scheduling jobs on identical and uniform processors revisited
- Server Scheduling to Balance Priorities, Fairness, and Average Quality of Service
- The Santa Claus problem
- Tighter bounds on a heuristic for a partition problem
- Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation
Cited in
(13)- Fair allocation of indivisible goods: improvement
- Fair allocation of indivisible goods: beyond additive valuations
- Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints
- Approximate separable multichoice optimization over monotone systems
- EPTAS for load balancing problem on parallel machines with a non-renewable resource
- EPTAS for load balancing problem on parallel machines with a non-renewable resource
- Online scheduling with rejection and reordering: exact algorithms for unit size jobs
- The benefit of preemption with respect to the \(\ell_p\) norm
- A unified framework for designing EPTAS for load balancing on parallel machines
- Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs
- Fixed-parameter approximation schemes for weighted flowtime
- EPTAS for parallel identical machine scheduling with time restrictions
- Load balancing: the long road from theory to practice
This page was built for publication: An efficient polynomial time approximation scheme for load balancing on uniformly related machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q463715)
