[Model] SchedulingToMinimizeWeightedCompletionTime

[isPANN]

Important

Build as optimization, not decision. Value = Min<u64>.
Objective: Minimize total weighted completion time Σ C(t)·w(t).
Do not add a bound/threshold field — let the solver find the optimum directly. See #765.

Motivation

SCHEDULING TO MINIMIZE WEIGHTED COMPLETION TIME (P197) from Garey & Johnson, A5 SS13. An NP-complete scheduling optimization problem: given tasks with integer lengths and weights on m identical processors (no precedence), find a schedule minimizing the total weighted completion time. NP-complete even for m = 2 by reduction from PARTITION, and NP-complete in the strong sense for m arbitrary [Lenstra, Rinnooy Kan, and Brucker, 1977].

Associated rules:

• R142: Partition -> Scheduling to Minimize Weighted Completion Time (this model is the target)
• [Rule] SchedulingToMinimizeWeightedCompletionTime to ILP #783: SchedulingToMinimizeWeightedCompletionTime -> ILP (direct ILP companion, bundled in model PR)

Definition

Name: SchedulingToMinimizeWeightedCompletionTime

Reference: Garey & Johnson, Computers and Intractability, A5 SS13

Mathematical definition:

INSTANCE: Set T of tasks, number m ∈ Z⁺ of processors, for each task t ∈ T a length l(t) ∈ Z⁺ and a weight w(t) ∈ Z⁺.

OBJECTIVE: Find an m-processor schedule σ for T that minimizes the total weighted completion time: ∑_{t ∈ T} C(t) · w(t), where C(t) = σ(t) + l(t) is the completion time of task t, and σ(t) is the start time of t in the schedule. Within each processor, tasks are processed sequentially with no idle time.

NOTE: For a given assignment of tasks to processors, the optimal ordering on each processor is given by Smith's rule: sort tasks in non-decreasing order of l(t)/w(t) (length-to-weight ratio).

Variables

• Count: n = |T| (one variable per task)
• Per-variable domain: {0, 1, ..., m − 1} — the processor index to which the task is assigned
• Meaning: p_t ∈ {0, ..., m − 1} is the processor assignment for task t. Given an assignment, the schedule on each processor is determined by Smith's rule (sort by non-decreasing l(t)/w(t) ratio). Therefore the only free variables are the processor assignments, giving dims() = [m; n] (an array of n entries, each equal to m).

Schema (data type)

Type name: SchedulingToMinimizeWeightedCompletionTime
Variants: none (no type parameters)

Field	Type	Description
lengths	Vec<u64>	Length l(t) of each task t ∈ T
weights	Vec<u64>	Weight w(t) of each task t ∈ T
num_processors	usize	Number of identical processors m

Complexity

• Best known exact algorithm: Brute-force enumeration of all m^n processor assignments, with Smith's rule ordering on each processor. NP-complete for m = 2 by reduction from PARTITION; NP-complete in the strong sense for arbitrary m [Lenstra, Rinnooy Kan, and Brucker, 1977]. For fixed m, solvable in pseudo-polynomial time by dynamic programming over load vectors.
• Complexity expression: num_processors^num_tasks
• Special cases: Solvable in polynomial time if all lengths are equal (by matching) or if all weights are equal [Conway et al., 1967; Horn, 1973; Bruno et al., 1974].

Extra Remark

Full book text:

INSTANCE: Set T of tasks, number m in Z+ of processors, for each task t in T a length l(t) in Z+ and a weight w(t) in Z+, and a positive integer K.
QUESTION: Is there an m-processor schedule sigma for T such that the sum, over all t in T, of (sigma(t) + l(t))*w(t) is no more than K?

Reference: [Lenstra, Rinnooy Kan, and Brucker, 1977]. Transformation from PARTITION.

Comment: Remains NP-complete for m = 2, and is NP-complete in the strong sense for m arbitrary [Lageweg and Lenstra, 1977]. The problem is solvable in pseudo-polynomial time for fixed m. These results continue to hold if "preemptive" schedules are allowed [McNaughton, 1959]. Can be solved in polynomial time if all lengths are equal (by matching techniques). If instead all weights are equal, it can be solved in polynomial time even for "different speed" processors [Conway, Maxwell, and Miller, 1967] and for "unrelated" processors [Horn, 1973], [Bruno, Coffman, and Sethi, 1974]. The "preemptive" case for different speed processors also can be solved in polynomial time [Gonzalez, 1977]. If precedence constraints are allowed, the original problem is NP-complete in the strong sense even if all weights are equal, m = 2, and the partial order is either an "in-tree" or an "out-tree" [Sethi, 1977a]. If resources are allowed, the same subcases mentioned under RESOURCE CONSTRAINED SCHEDULING are NP-complete, even for equal weights [Blazewicz, 1977a].

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all m^n assignments of tasks to processors; for each assignment, order tasks on each processor by Smith's rule; compute total weighted completion time; return the minimum.)
• It can be solved by reducing to integer programming. (Binary ILP: x_{t,p} ∈ {0,1} for assignment, ordering variables for sequencing on each processor, and linearized completion time constraints. Direct → ILP rule will be bundled in the model PR per project convention.)
• Other: Pseudo-polynomial DP for fixed m; polynomial when all lengths or all weights are equal.

Example Instance

Input:
T = {t_0, t_1, t_2, t_3, t_4} (n = 5 tasks), m = 2 processors.

Task	Length l(t)	Weight w(t)	l/w ratio
t_0	1	6	0.167
t_1	2	4	0.500
t_2	3	3	1.000
t_3	4	2	2.000
t_4	5	1	5.000

Smith's rule ordering (by non-decreasing l/w): t_0 < t_1 < t_2 < t_3 < t_4.

Optimal assignment (minimum weighted completion time = 47):

Processor 0: {t_0, t_2, t_4}

• Smith's rule order: t_0 (l/w=0.167), t_2 (l/w=1.0), t_4 (l/w=5.0)
• t_0 completes at 1, contribution = 1 × 6 = 6
• t_2 completes at 4, contribution = 4 × 3 = 12
• t_4 completes at 9, contribution = 9 × 1 = 9
• Subtotal = 27

Processor 1: {t_1, t_3}

• Smith's rule order: t_1 (l/w=0.5), t_3 (l/w=2.0)
• t_1 completes at 2, contribution = 2 × 4 = 8
• t_3 completes at 6, contribution = 6 × 2 = 12
• Subtotal = 20

Total weighted completion time = 27 + 20 = 47.

Verification (Python brute-force over all 2^5 = 32 assignments):

• Optimal value: 47, achieved by 2 assignments (mirror pair swapping processor labels)
• Suboptimal assignments: 30
• Cost range: [47, 71], 6 distinct cost values
• The distinct l/w ratios ensure Smith's rule gives a unique ordering on each processor, exercising the weighted aspect of the problem.

Expected Outcome

Optimal objective value: 47 (minimization). The optimal assignment is P0 = {t_0, t_2, t_4}, P1 = {t_1, t_3} (or mirror).

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph; associated rule R142 (Partition → this) planned
Non-trivial	✅ Pass	Distinct scheduling problem with weighted completion time objective — not isomorphic to any existing model
Correctness	✅ Pass	Lenstra, Rinnooy Kan & Brucker 1977 (Annals of Discrete Mathematics 1:343–362) verified; Garey & Johnson A5 SS13 consistent
Well-written	❌ Fail	No concrete complexity bound for declare_variants!; example uses equal weights and lengths (w=l for all tasks); naming convention concern

Overall: 3 passed, 0 warnings, 1 failed

---

Usefulness

SchedulingToMinimizeWeightedCompletionTime does not exist in the current codebase. The problem is a classic NP-complete scheduling problem from Garey & Johnson (A5 SS13) with a planned reduction from Partition (R142).

Non-trivial

This is a genuinely distinct problem. The objective (minimize total weighted completion time) and the input structure (tasks with lengths and weights, processor count, bound K) differ from all existing models. It is not a variant of any existing problem in the codebase.

Correctness

All cited references verified:

• Lenstra, Rinnooy Kan & Brucker, 1977: "Complexity of Machine Scheduling Problems," Annals of Discrete Mathematics 1:343–362. Foundational survey establishing NP-completeness of many scheduling variants, including weighted completion time minimization. The claim of NP-completeness via PARTITION reduction is consistent.
• Garey & Johnson, 1979: A5 SS13 classification confirmed.
• The polynomial special cases (equal lengths, equal weights) are well-known results consistent with the literature.

Well-written

Failures:

1. No concrete complexity bound. The Complexity section lists special cases and references but does not give a specific worst-case time bound for the general NP-complete case (needed for declare_variants!). "Exact approaches use ILP or branch-and-bound" is not a complexity string. The issue should provide a concrete bound, e.g., O*(m^n) for brute-force enumeration, or cite a better exact algorithm if one exists.

2. Example uses equal weights and lengths. In the example, w(t) = l(t) for all tasks (w/l ratio = 1 for all), which means Smith's rule gives no ordering preference. This fails to exercise the "weighted" aspect of the problem — the example should use distinct weights and lengths so that the w/l ordering matters and illustrates why weighted completion time is nontrivial.

3. Naming convention concern. The name SchedulingToMinimizeWeightedCompletionTime is very long. The project convention uses Minimum/Maximum prefix for optimization problems (e.g., MinimumVertexCover, MaximumIndependentSet). However, the issue formulates this as a decision problem (is total weighted completion time ≤ K?), making it a satisfaction problem with Metric = bool. The issue should clarify whether this is implemented as optimization (minimize weighted completion time, no K) or satisfaction (decision with bound K), and name accordingly.

4. Variables section clarity. The mapping describes choosing processor assignments {1, ..., m}, but the actual search space for the decision version also includes orderings within processors. The relationship between the variable encoding and the schema fields is unclear — particularly how dims() would be implemented.

Recommendations

• Provide a concrete complexity string for declare_variants!.
• Redesign the example with different w/l ratios (e.g., tasks where shortest-first vs. highest-weight-first gives different results).
• Clarify optimization vs. satisfaction formulation and adjust naming convention.
• Consider a shorter name if implemented as optimization: e.g., MinimumWeightedCompletionTime.

[isPANN]

Issue Quality Check — Model (Re-check)

Previous check: 2026-03-12. Re-checking with --force.

Check	Result	Details
Usefulness	✅ Pass	Novel multi-machine scheduling problem (GJ SS13); distinct from existing single-machine SequencingToMinimizeWeightedCompletionTime (SS4/SS5); Partition exists as reduction source
Non-trivial	✅ Pass	Different feasibility constraints (m processors, no precedence) vs existing sequencing model (1 processor, precedence constraints)
Correctness	⚠️ Warn	All primary references verified; Horn 1973 date may be off (found 1972 or 1974 publications); no concrete complexity expression provided
Well-written	❌ Fail	No concrete complexity bound for declare_variants!; example uses degenerate w=l for all tasks; decision vs optimization ambiguity; variables/dims unclear

Overall: 2 passed, 1 warning, 1 failed

Changes from previous check: Same verdict. Core issues remain unfixed.

---

Usefulness

Pass. SchedulingToMinimizeWeightedCompletionTime does not exist in the codebase. The existing SequencingToMinimizeWeightedCompletionTime is a genuinely different problem:

	Existing (SS4/SS5)	Proposed (SS13)
Processors	1 (single machine)	m (multiple identical)
Precedence	Yes	No
Formulation	Optimization (minimize)	Decision (≤ K)
Size fields	num_tasks, num_precedences	num_tasks (+ num_processors)

The issue references R142 (Partition → this model). Partition exists in the codebase, so the planned reduction is viable.

Non-trivial

Pass. The problem has genuinely distinct feasibility constraints:

• Multi-processor assignment (combinatorial: m^n assignments vs n! permutations)
• No precedence constraints (different from existing sequencing model)
• The decision-problem formulation with bound K adds another structural difference

Correctness

Pass with warnings.

Reference	Status
Garey & Johnson A5 SS13	✅ Confirmed — scheduling to minimize weighted completion time
Lenstra, Rinnooy Kan & Brucker, 1977	✅ Verified — "Complexity of machine scheduling problems," Annals of Discrete Mathematics 1:343–362
Conway, Maxwell & Miller, 1967	✅ Verified — "Theory of Scheduling," Addison-Wesley
Bruno, Coffman & Sethi, 1974	✅ Verified — "Scheduling independent tasks to reduce mean finishing time," CACM 17:382–387
Horn, 1973	⚠️ Date uncertain — found Horn 1972 (SIAM J. Appl. Math. 23:189–202) and Horn 1974 (Naval Res. Logistics 21:177–185), but not a 1973 publication. Minor discrepancy.

No concrete complexity expression. The Complexity section discusses special cases and general approaches but never provides a specific worst-case time bound suitable for declare_variants!. The brute-force bound is O(m^num_tasks * num_tasks * log(num_tasks)) (enumerate all m^n processor assignments, sort each processor's tasks by Smith's rule in O(n log n)). This should be stated explicitly.

Well-written

Fail. The following issues remain from the previous check:

1. No concrete complexity bound (Fail). The Complexity section says "exact approaches use ILP or branch-and-bound" but provides no O(...) expression for declare_variants!. Needed: e.g., "num_processors^num_tasks" for the brute-force approach, or a better bound if one exists in the literature.

2. Example uses degenerate w=l for all tasks (Fail). Python validation confirms: all w(t)/l(t) ratios equal 1.0, so Smith's rule gives no ordering preference. The "weighted" aspect of the problem — which is the core distinguishing feature — is not exercised. The example should use distinct w/l ratios so that the ordering within each processor actually matters.

Python validation stats:

• Total configurations: 32 (2^5)
• Optimal value: 145 (matches claim ✅)
• Optimal solutions: 2 (symmetric: swap processor labels)
• Suboptimal solutions: 30
• Unique cost values: 10, range [145, 245]
• Arithmetic in the worked example is correct ✅

3. Decision vs optimization ambiguity (Warn). The issue formulates the problem as a decision/satisfaction problem (is total weighted completion time ≤ K?), consistent with G&J. However, the existing SequencingToMinimizeWeightedCompletionTime is implemented as an optimization problem (no bound K). The issue should explicitly state whether this will be a SatisfactionProblem (with bound K in the schema) or an OptimizationProblem (minimize, drop K from schema). This affects the Problem trait implementation, dims(), and evaluate().

4. Variables section unclear about dims() (Warn). The variable description mentions processor assignment {1, ..., m} per task, giving dims = [m, m, ..., m] (n times). But it also mentions "ordering on each processor" via Smith's rule. Since Smith's rule determines a unique ordering for any given assignment (sort by w/l ratio), the ordering is not a free variable — only the assignment matters. This should be stated clearly: dims() = [m; n] where m = num_processors and n = num_tasks.

5. Missing How to solve section for pred show size_fields (Warn). The size_fields should include num_tasks and num_processors. The Schema section does not indicate which fields map to size getters.

Recommendations

• Add concrete complexity: "num_processors^num_tasks" for brute-force (or cite a better exact algorithm).
• Redesign example with distinct w/l ratios, e.g., lengths [2, 5, 3, 4, 6], weights [6, 2, 5, 3, 4] so Smith's rule ordering matters.
• Clarify: if satisfaction problem, keep bound K and use Metric = bool; if optimization, drop K and use Metric = SolutionSize<u64>.
• State explicitly: dims() = [m; n] since Smith's rule removes ordering freedom.
• Consider shorter name MinimumWeightedCompletionTimeScheduling if implemented as optimization.

[isPANN]

Fix-issue changelog

• Switched from decision/satisfaction framing (with bound K) to optimization framing (minimize weighted completion time) — consistent with existing SequencingToMinimizeWeightedCompletionTime
• Removed bound field from Schema (no longer needed without K)
• Added concrete complexity expression: num_processors^num_tasks for declare_variants!
• Replaced degenerate example (all w/l = 1) with new example using distinct l/w ratios (0.167, 0.5, 1.0, 2.0, 5.0) — validated by Python brute-force over all 32 assignments
• Clarified Variables section: dims() = [m; n] since Smith's rule determines ordering (only processor assignment is a free variable)
• Updated Definition to state optimization objective explicitly
• Updated How to solve to reflect optimization (return minimum, not check ≤ K)

Applied by /fix-issue.

[isPANN]

Implementation note: build as optimization

This model should be implemented as an optimization problem (Value = Min<u64> or similar), not a decision problem with a bound field.

• Objective: Minimize total weighted completion time Σ w_i · C_i across all tasks
• Do not add a bound threshold — let the solver find the optimal schedule directly
• Follows the same pattern as the existing SequencingToMinimizeWeightedCompletionTime model (which already uses Min<u64>)

See #765 for context on the decision-vs-optimization policy.