The local-global conjecture for scheduling with non-linear cost

Nikhil Bansal, Christoph Dürr, Kim Thang Nguyen, Óscar C. Vásquez

Abstract

This paper resolves a long-standing question in scheduling theory regarding the relationship between local improvements and global optimality for non-linear cost functions. We prove the "Local-Global Conjecture" for cost functions with an exponent $\beta \geq 1$. By showing that local pairwise optimality implies global dominance, we enable the creation of pruning rules that accelerate exact algorithms, such as A* search, by up to 10,000x.

Introduction

In classical single-machine scheduling, the goal is to find an ordering of $n$ jobs that minimizes a specific cost function. For linear costs, such as the weighted sum of completion times ($\sum w_j C_j$), Smith’s Rule (1956) provides an efficient solution: jobs should be ordered by their weight-to-processing-time ratio ($w_j/p_j$).

However, many modern applications, including energy-efficient speed scaling and learning-effect modeling, require non-linear cost functions like $\sum w_j C_j^\beta$. For $\beta \neq 1$, the problem is significantly more complex because the optimal relative order of two jobs may depend on their position in the schedule or the jobs surrounding them. This paper investigates dominance properties—conditions under which job $i$ must precede job $j$ in any optimal schedule—and specifically addresses the Local-Global Conjecture.

The Local-Global Conjecture

The conjecture posits that if it is always locally better to place job $i$ before job $j$ when they are adjacent, then $i$ must precede $j$ in any global optimal ordering, regardless of their distance. Proving this link is crucial for reducing the search space of scheduling problems.

Theoretical Proof for $\beta \geq 1$

The authors provide a rigorous proof that the Local-Global Conjecture holds for all convex cost functions where $\beta \geq 1$. The proof utilizes properties of polynomials and log-concavity, employing induction and carefully constructed weighted combinations of inequalities to show that local optimality is "strong" enough to dictate global structure.

Dominance regions for the convex case ($\beta > 1$), where local properties successfully define global dominance boundaries.

As shown in the figure above, for $\beta > 1$, the regions of global dominance ($i <_g j$ and $j <_g i$) are clearly delineated by boundaries derived from local pairwise comparisons. This simplification transforms a complex combinatorial search into a series of straightforward pairwise tests.

Experimental Validation and Pruning Power

To evaluate the practical impact of these theoretical findings, the authors implemented an A* search algorithm using the proven dominance properties as pruning rules. Testing on synthetic datasets with 20 to 60 jobs, they found that these rules dramatically reduce the number of states explored.

For "hard" instances—where jobs have similar Smith-ratios—the pruning rules provided a massive performance boost. The number of nodes explored by the A algorithm decreased by factors of 1,000 to 10,000* compared to algorithms without these rules.

The Concave Case and Future Work

While the conjecture is fully proven for $\beta \geq 1$, the concave case ($0 < \beta < 1$) remains a challenge. The mathematical tools used for convex costs do not directly translate, and the relationship between local and global dominance is more intricate.

Dominance regions for the concave case ($0 < \beta < 1$), illustrating the more complex relationship between local ($<_l$) and global ($<_g$) optimality.

Although the authors provided new sufficient conditions that improve performance for $0 < \beta < 1$, a full proof of the conjecture for this range remains an open question. Future research will also focus on determining the formal computational complexity (P vs. NP-hard) of the problem for $\beta \neq 1$ and extending these results to broader classes of objective functions.

Summary updated

BibTeX
@article{bansal2017local,
  author = {Nikhil Bansal and Christoph Dürr and Kim Thang Nguyen and Óscar C. Vásquez},
  title = {{The local-global conjecture for scheduling with non-linear cost}},
  journal = {J. Sched.},
  year = {2017},
  url = {https://openreview.net/forum?id=KZUyyqwTjB},
}
Figure