Minimizing Total and Weighted Completion Times in Scheduling

19 concepts14 papers2 proposals

When allocating tasks to machines, what are we actually trying to optimize? The most intuitive answer is often the makespan ($C_{\max}$)—the time at which the very last task finishes. Minimizing makespan ensures high overall throughput, which is vital in physical or tightly coupled operations like multi-crane logistics (Xie et al.), drop-line batch processing (Tian et al.), or autonomous vehicle routing (Xue et al.).

However, makespan has a major blind spot: it treats a schedule where every job finishes early the same as a schedule where every job finishes at the absolute last second, as long as the final completion time is identical. As Lassota et al. point out, minimizing the total completion time ($\sum C_i$) or average latency is often far more practical for user-facing systems. By minimizing the sum of completion times, an algorithm reduces the average time a job spends waiting in the queue, thereby maximizing system responsiveness and minimizing the number of active, unfinished tasks.

When tasks carry different priorities, costs, or urgency, this objective scales into the total weighted completion time ($\sum w_i C_i$). Balancing these min-sum objectives against deadlines (tardiness) and system constraints forms the core of modern scheduling theory.


Online Scheduling and the Power of Priority Rules

In real-world computing environments, schedulers rarely have the luxury of knowing all future tasks in advance. Instead, jobs arrive dynamically over time, forcing algorithms to make irreversible sequencing decisions on the fly.

To build intuition for why online algorithms can achieve strong performance guarantees, we look to classical offline scheduling. On a single machine, Smith's ratio rule proves that sorting jobs by their "density"—the ratio of their weight to their processing time ($w_i / p_i$)—is strictly optimal. Intuitively, you want to clear out high-value, short-duration tasks first to drop the cumulative waiting cost as fast as possible.

But how does this intuition hold up when jobs arrive over time on parallel machines? Andreas S. Schulz demonstrates that simple extensions of this ratio rule can achieve near-optimal competitive ratios in both preemptive and nonpreemptive parallel machine environments. By greedily applying density-based prioritization as jobs arrive, the system maintains a tight bound against an omniscient offline scheduler.

Ratio Rule Intuition:
High Weight, Short Time  --> Clear immediately (Drastically lowers sum of completion times)
Low Weight, Long Time    --> Defer to the end

Rather than reacting purely greedily to every arrival, more sophisticated online frameworks decouple the problem into selection and sequencing phases. Khuller et al. introduce a "select and permute" framework. This approach periodically buffers arriving jobs, uses an offline approximation algorithm to select a well-structured subset, and then permutes them efficiently. This blending of offline foresight with online execution yields state-of-the-art competitive ratios across complex environments like concurrent open shops and coflows.

Handling Strategic Agents and Stochasticity

In distributed systems, the parameters of a job ($w_i$ and $p_i$) are often reported by selfish agents who might lie to get their tasks processed faster. Taub et al. address this by designing "prompt" online mechanisms. These algorithms provide agents with immediate, immutable scheduling decisions while remaining incentive-compatible, ensuring that truth-telling is the dominant strategy for minimizing the global sum of completion times.

Furthermore, processing times are rarely deterministic. Schedulers frequently face situations where a job's duration is a random variable, only fully realized upon completion. Vredeveld et al. bridge this gap through Stochastic Online Scheduling (SOS). They prove that simple, combinatorial priority policies can maintain robust performance guarantees even when the scheduler only knows the probability distribution of job durations, showing that the underlying structural properties of the ratio rule resist stochastic noise.


Tightening Mathematical Formulations for Exact Solutions

For offline scenarios, finding the absolute mathematically optimal schedule is notoriously difficult because scheduling is fundamentally combinatorial. Standard Mixed-Integer Linear Programming (MILP) formulations often suffer from weak linear programming (LP) relaxations. In an LP relaxation, the solver allows jobs to be fractionally processed (e.g., running 50% of Job A and 50% of Job B simultaneously on the same machine). This creates a massive "gap" between the fractional lower bound and the true integer solution, causing branch-and-bound algorithms to stall.

To solve large instances exactly, researchers must restructure the decision space to eliminate these unrealistic fractional solutions.

Time-Indexed Formulations and Cutting Planes

One approach is to discretize time into integer steps, creating binary variables that dictate whether a job starts at a specific time. However, even time-indexed models can be loose when sequence-dependent setup times or strict time windows are introduced. Rosa et al. resolve this by introducing new families of valid inequalities (cutting planes). These mathematical constraints explicitly forbid overlapping fractional allocations, shrinking the linear relaxation gap from over 37% to under 6% and allowing standard solvers to find exact solutions rapidly.

Flow-Based Formulations via Decision Diagrams

An alternative to time-indexing is to view scheduling as a network flow problem. Kowalczyk et al. leverage Binary Decision Diagrams (BDDs) to construct a flow-based formulation for parallel machine scheduling with weighted tardiness.

Standard MILP: Loose algebraic bounds -> Slow branch-and-bound search
BDD Formulation: Paths represent valid schedules -> Network flow yields ultra-tight LP bounds

By representing the space of all feasible job sequences as paths through a BDD graph, the authors extract exceptionally tight lower bounds. When embedded within a branch-and-price framework, this flow-based representation allows the exact solution of complex scheduling instances that were previously completely intractable.


When scheduling problems incorporate highly non-linear real-world constraints—such as time-dependent processing speeds, job incompatibility cliques (Lassota et al.), or earliness-tardiness penalties (Rosa et al.)—the problem often becomes APX-hard. When exact mathematical formulations fail to scale, metaheuristics step in.

The challenge for any local search heuristic is avoiding local minima. If an algorithm only changes a schedule by swapping two adjacent jobs, it can easily get stuck in a suboptimal arrangement. To circumvent this, Angel et al. (2005) utilize a multi-start dynasearch algorithm for single-machine scheduling where job processing times are time-dependent. Dynasearch uses dynamic programming to search an exponentially large neighborhood of independent job swaps simultaneously in polynomial time. This allows the algorithm to make sweeping, coordinated adjustments to the schedule that traditional local search would never discover.

Other approaches adapt nature-inspired metaheuristics to discrete scheduling spaces. For instance, Chen et al. adapt Particle Swarm Optimization (PSO) to handle discrete task assignments in grid computing environments, mapping continuous velocity vectors to discrete job-to-machine allocations to minimize total completion time.

Yet, even within complex metaheuristic frameworks, structural scheduling insights remain vital. For parallel machine scheduling with weighted late work criteria, Xu et al. demonstrate that while metaheuristics like Simulated Annealing provide high-quality solutions, a simple, targeted heuristic called "Largest Density First" (LDF) can deliver highly competitive results with drastically shorter runtimes. This underscores a recurring truth across the scheduling literature: whether designing online priority rules, tightening exact integer programs, or guiding metaheuristics, the most effective solutions leverage the fundamental mathematical relationship between a job's weight and its duration.

Key Foundational Work

A multi-start dynasearch algorithm for the time dependent single-machine total weighted tardiness scheduling problem (2005) — contributed 1 concept elements to this direction.
On-line scheduling to minimize average completion time revisited (2004) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_makespan_minimization_average_latency_mi_571f8a28,
  title = {makespan minimization (average latency minimization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/makespan-minimization-average-latency-minimization/rdr_571f8a282032468aa1773cadf13be1b4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_makespan_minimization_average_latency_mi_571f8a28_v1,
  title = {makespan minimization (average latency minimization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/makespan-minimization-average-latency-minimization/rdr_571f8a282032468aa1773cadf13be1b4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake