Approximation schedules reduce cost and delay on parallel machines
Approximation algorithms for identical parallel machine scheduling with assignment costs
Data Structures and Algorithms
Summary
The paper addresses how to assign jobs to identical machines efficiently, balancing the time to finish all jobs with costs from assigning specific jobs to specific machines. The authors design algorithms that produce schedules completing nearly as fast as possible while keeping assignment costs no higher than the best known schedules using the same time limits. They also create methods that find schedules minimizing cost among all fastest schedules, improving earlier approaches. These results apply to different cost types and provide guarantees about schedule quality and runtime.
What this means in practice
- •For manufacturing planners: Create schedules that ensure jobs finish nearly as early as possible while controlling machine assignment costs precisely under given deadlines.
- •For data center operators: Plan task distributions over identical servers to minimize total assignment costs without exceeding makespan targets, improving resource cost efficiency.
Authors
Wei Li
Abstract
We study non-preemptive scheduling on identical parallel machines in which assigning job $j$ to machine $M_i$ incurs the cost $c_{ij}=a_iw_j+b_j$. The processing times $p_j$ and the cost weights $w_j$ are independent, and the number of machines is part of the input. For every fixed $\varepsilon\in(0,1]$ and every deadline $T$ for which a schedule with makespan at most $T$ exists, we give a polynomial-time algorithm that computes a schedule with makespan at most $(1+\varepsilon)T$ whose total assignment cost does not exceed the minimum under the deadline $T$. Using this algorithm as a subroutine, we obtain a polynomial-time approximation scheme for minimizing the makespan under a total cost budget whose schedules always satisfy the budget; this answers an open question for costs $c_{ij}=l_ic_j$ with $c_j$ independent of $p_j$. For the lexicographic problem, in which the total assignment cost is minimized among all schedules of minimum makespan, we obtain in polynomial time a schedule with makespan at most $1+\varepsilon$ times the minimum and total assignment cost at most that of a lexicographically optimal schedule; this improves the makespan guarantees of earlier algorithms for additive and multiplicative costs. For costs $c_{ij}=s_i+a_iw_j$, where $s_i$ is charged for each job processed on $M_i$, the same guarantees are obtained in quasi-polynomial time.