An Almost Tight Lower Bound for the Scheduling Problem to Meet Two Min-Sum Objectives

Donglei Du, Dachuan XuJournal of the Operations Research Society of China 2013 · DOI

TL;DR

This paper provides a significantly improved lower bound for a classic bi-criteria scheduling problem: minimizing both total completion time and weighted completion time on a single machine. By constructing a clever worst-case scenario, the authors prove that the theoretical limit of how well we can simultaneously approximate both objectives is much stricter than previously thought, narrowing the gap between known upper and lower bounds to a constant factor.

What Problem Does This Paper Address?

In the world of scheduling, we often want to satisfy multiple goals at once. A common problem involves a single machine and a set of jobs, where we want to minimize:

  1. Total Completion Time ($\sum C_j$): The sum of the times when each job finishes.
  2. Total Weighted Completion Time ($\sum w_j C_j$): The sum of completion times, where each job is scaled by a "weight" representing its priority.

Usually, a schedule that is optimal for one objective is poor for the other. Researchers look for "simultaneous approximation" schedules—a single job sequence that is within a factor of $(1 + 1/r)$ for the first objective and $(1 + ar)$ for the second.

Previous work by Angel et al. (2007) established an upper bound of $(1 + 1/r, 1 + r)$, meaning such a schedule always exists. However, the known lower bounds (the proof that you cannot do better than a certain ratio) were quite loose—only in the order of $\Omega(1)$ or $\Omega(\sqrt{r})$. This paper aims to find an "almost tight" lower bound to see just how close to the $1+r$ limit we are forced to stay.

Methods

This is a theoretical paper that uses a mathematical proof based on instance construction. To prove a lower bound, the authors designed a specific "nightmare" scenario (an instance) where any possible schedule will inevitably perform poorly on at least one of the two objectives.

The authors constructed an instance with $n$ jobs:

  • $n-1$ "light" jobs: These have a processing time of 1 and a weight of 0.
  • 1 "heavy" job: This job has a very large processing time ($p_n$) and a weight of 1.

They then analyzed the trade-off: to minimize total completion time, the heavy job should go last. To minimize weighted completion time, the heavy job (which has all the weight) should go first. By mathematically analyzing the ratios as the position of this heavy job shifts, they derived the new bound.

Datasets

Not discussed in the paper. As a theoretical work in combinatorial optimization, the paper relies on mathematical proofs and constructed instances rather than empirical datasets or benchmarks.

Key Insights and Ideas

  • The Power of Simplicity: The authors showed that you don't need a complex set of jobs to prove a strong lower bound. A single job with high processing time and high weight versus many jobs with low time and no weight is enough to expose the fundamental conflict between the two objectives.
  • Closing the Gap: Previous researchers found lower bounds that grew slowly (like the square root of $r$). This paper identifies a lower bound that grows linearly with $r$ ($\Omega(r)$), which matches the growth rate of the known upper bound.
  • Asymptotic Analysis: The proof relies on looking at what happens as the number of jobs ($n$) and the processing time of the heavy job ($p_n$) become very large, allowing them to reach the $1 + \frac{1}{2}r$ threshold.

Key Results

  • Theorem 3: The authors prove that for the bi-criteria scheduling problem, there exists an instance such that no $(1 + 1/r, 1 + \frac{1}{2}r - \epsilon)$-approximation schedule exists for any $r > 0$ and $\epsilon > 0$.
  • Improved Tightness: This result improves the lower bound from the previous $\Omega(\sqrt{r})$ to $\Omega(r)$.
  • Corollary 1: Combined with previous upper bounds, the paper establishes that for any $(1 + 1/r, 1 + ar - \epsilon)$-approximation, the coefficient $a$ must fall between $1/2$ and $1$. This means the current best algorithms are already within a factor of 2 of being perfectly optimal.

Limitations and Future Work

  • The Remaining Gap: While "almost tight," there is still a small gap between the lower bound ($\approx 1 + 0.5r$) and the upper bound ($1 + r$). Future research could attempt to close this remaining constant factor.
  • Scope: The results are specific to the single-machine environment ($1 || \{\sum C_j, \sum w_j C_j\}$). The authors do not discuss how these bounds might change in multi-machine environments or with different constraints like release dates or precedence.

Summary updated

BibTeX
@article{du2013almost,
  author = {Donglei Du and Dachuan Xu},
  title = {{An Almost Tight Lower Bound for the Scheduling Problem to Meet Two Min-Sum Objectives}},
  journal = {Journal of the Operations Research Society of China},
  year = {2013},
  doi = {10.1007/s40305-012-0002-7},
}
Figure