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

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

TL;DR

This paper tackles the challenging problem of scheduling jobs on a single machine to minimize a non-linear cost function, specifically $\sum w_j C_j^\beta$. The authors introduce and prove a "local-global conjecture" that significantly simplifies scheduling decisions by showing that a local ordering property implies a global one for $\beta \ge 1$. This work leads to substantial speedups in exact algorithms for this problem.

What Problem Does This Paper Address?

The paper addresses the single-machine scheduling problem with the objective of minimizing the sum of weighted completion times raised to a power $\beta$, i.e., $\sum w_j C_j^\beta$. For $\beta=1$, this is the classic weighted sum of completion times problem, which is efficiently solved by Smith's rule (ordering jobs by decreasing $w_j/p_j$). However, for $\beta \neq 1$, the problem becomes significantly harder, and its complexity status is open. A key difficulty is that the optimal ordering of two jobs might depend on their positions in the schedule and the presence of other jobs, making it hard to establish simple ordering rules. This paper aims to provide a more general characterization of job ordering properties that can simplify the search for optimal schedules.

Methods

The core of the paper's contribution lies in characterizing the "local order property" ($i \prec_e j$, meaning job $i$ can be locally swapped before job $j$ without increasing cost) and the "global order property" ($i \prec_g j$, meaning job $i$ must precede job $j$ in any optimal schedule). The authors introduce a function $\phi_{ij}(t)$ to analyze the local order property and derive several technical lemmas about the properties of the cost function $f(t) = t^\beta$.

The main theoretical achievement is proving the "Local-Global Conjecture" for $\beta \ge 1$: $i \prec_g j$ if and only if $i \prec_e j$. This is a significant result because it implies that a simple local exchange condition is sufficient to guarantee a global ordering, greatly simplifying the problem structure. The proofs involve intricate polynomial manipulations and carefully chosen inequalities. For the case $0 < \beta < 1$, they provide partial results and characterizations.

The paper also includes an experimental study using an A* search algorithm to evaluate the impact of these new dominance properties on pruning the search space.

Datasets

The paper does not introduce new datasets. Instead, it uses:

  • Randomly generated instances: For experimental evaluation, instances are generated based on models described in prior work (Höhn and Jacobs 2012a). These models involve generating processing times and weights, with specific distributions for Smith-ratios to control instance hardness.
  • Test sets from prior work: For performance measurements specifically for $\beta=2$, they use test sets from Höhn and Jacobs (2012a, 2012b).

Key Insights and Ideas

  • The Local-Global Conjecture: The most significant insight is the proof that for $\beta \ge 1$, the local ordering condition ($i \prec_e j$) is equivalent to the global ordering condition ($i \prec_g j$). This is a powerful simplification, as local pairwise comparisons can now directly inform global optimal ordering.
  • Generalization of Smith's Rule: While Smith's rule ($\beta=1$) is based on a simple ratio, this work extends the understanding of ordering principles to non-linear costs, revealing that the local-global equivalence holds for a broad range of $\beta$ values.
  • Impact on Exact Algorithms: The derived dominance properties significantly prune the search space for exact algorithms like A*. The experimental results show speedups of up to $10^4$ times, demonstrating the practical utility of these theoretical findings.
  • Complexity of $0 < \beta < 1$: The paper highlights that the case $0 < \beta < 1$ is more complex, with the local-global equivalence not holding in general, requiring more nuanced conditions.

Key Results

  • Proof of Local-Global Conjecture for $\beta \ge 1$: The paper proves that for $\beta \ge 1$, $i \prec_g j \iff i \prec_e j$. This is achieved through detailed mathematical analysis of polynomial properties.
  • Partial Results for $0 < \beta < 1$: For the case $0 < \beta < 1$, the paper provides some sufficient conditions for the global order property, particularly for $p_j \le p_i$.
  • Experimental Speedup: The application of the derived dominance properties in an A* search algorithm resulted in improvements in the number of generated search nodes by factors of up to $10^4$ for some instances.
  • Characterization of Order Properties: The paper provides detailed characterizations of local and global order properties for various ranges of $\beta$ and job parameter relationships, visualized in Figure 1.

Limitations and Future Work

  • Open Problem for $0 < \beta < 1$: While partial results are presented, a complete characterization of the local-global conjecture for $0 < \beta < 1$ remains an open problem. The authors believe it likely holds but acknowledge its complexity and the need for new analytical techniques.
  • Generalization to Other Cost Functions: The paper suggests exploring the class of objective functions for which the local-global conjecture holds, indicating a broader research direction beyond the specific $t^\beta$ cost function.
  • Experimental Limitations: The experimental study, while showing significant improvements, relies on specific random instance generation models and an A* search algorithm. Further studies with different algorithms or instance generation methods could provide broader insights.

Summary updated

Abstract

We consider the classical scheduling problem on a single machine, on which we need to schedule sequentially n given jobs. Every job j has a processing time \(p_j\) and a priority weight \(w_j\), and for a given schedule a completion time \(C_j\). In this paper, we consider the problem of minimizing the objective value \(\sum _j w_j C_j^\beta \) for some fixed constant \(\beta >0\). This non-linearity is motivated for example by the learning effect of a machine improving its efficiency over time, or by the speed scaling model. For \(\beta =1\), the well-known Smith’s rule that orders job in the non-increasing order of \(w_j/p_j\) gives the optimum schedule. However, for \(\beta \ne 1\), the complexity status of this problem is open. Among other things, a key issue here is that the ordering between a pair of jobs is not well defined, and might depend on where the jobs lie in the schedule and also on the jobs between them. We investigate this question systematically and substantially generalize the previously known results in this direction. These results lead to interesting new dominance properties among schedules which lead to huge speed up in exact algorithms for the problem. An experimental study evaluates the impact of these properties on the exact algorithm A*.
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},
}

Loading related content...

Figure