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

2012/02/18 by Epstein, Leah, Levin, Asaf
#68Q25 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1202.4072

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 ∑_i=1^m C_i^p for a fixed value of p such that 01 the minimization problem is equivalent to the well-known problem of minimizing the ℓ_p norm of the vector of the completion times of the machines, and for 0

Related

• Scheduling to Approximate Minimization Objectives on Identical Machines
• Minimum total weighted completion time: Faster approximation schemes
• Job Scheduling under Base and Additional Fees, with Applications to Mixed-Criticality Scheduling
• Generalized Unrelated Machine Scheduling Problem
• Scheduling on (Un-)Related Machines with Setup Times