An efficient polynomial time approximation scheme for load balancing on uniformly related machines

DOI10.1007/S10107-013-0706-4zbMATH Open1297.68264arXiv1202.4072OpenAlexW2083173650MaRDI QIDQ463715FDOQ463715

Authors: Leah Epstein, Asaf Levin 

Publication date: 17 October 2014

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1202.4072

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

zbMATH Keywords

approximation algorithmsschedulingload balancingEPTAS

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Parametrized complexity theory.
• Integer Programming with a Fixed Number of Variables
• Title not available (Why is that?)
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Bounds for Certain Multiprocessing Anomalies
• Bounds for LPT Schedules on Uniform Processors
• Title not available (Why is that?)
• Approximation schemes for covering and packing problems in image processing and VLSI
• On the efficiency of polynomial time approximation schemes
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• The Santa Claus problem
• Analysis of Greedy Solutions for a Replacement Part Sequencing Problem
• Scheduling jobs on identical and uniform processors revisited
• Approximation schemes for scheduling on parallel machines
• Tighter bounds on a heuristic for a partition problem
• Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation
• Maximizing the minimum load for selfish agents
• Approximation schemes for scheduling on uniformly related and identical parallel machines
• Approximation schemes for scheduling and covering on unrelated machines
• Title not available (Why is that?)
• An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables
• All-norm approximation algorithms
• Title not available (Why is that?)
• Record Allocation for Minimizing Expected Retrieval Costs on Drum-Like Storage Devices
• Server Scheduling to Balance Priorities, Fairness, and Average Quality of Service
• Ancient and new algorithms for load balancing in the \(\ell_p\) norm

Cited In (13)

• 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
• Fair allocation of indivisible goods: improvement

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)