Source-linked AI summary
Serial-batch scheduling to minimise the total weighted late work
Yao-Wen Sang, Naiming Xie, Jian Chen, Malgorzata Sterna, Jacek Blazewicz
TL;DR
Serial-batch scheduling with weighted late work had not previously been studied, and its complexity matters for directing research on more complex models. The paper develops pseudo-polynomial dynamic programming algorithms and acceleration techniques for the general problem and two special cases. In the tested instances, the algorithms outperform Gurobi, including on larger instances where it times out.
Problem
Serial-batch processing had not previously been studied with late-work minimization, and determining the basic model’s complexity is presented as important for directing research on more complex models.
Source: §1 · p. 2Method
The paper develops pseudo-polynomial dynamic programming for the general problem, with acceleration bounds and specialized algorithms for common-due-date and agreeable cases.
Source: §3.1 · p. 9, §3.2 · p. 22, §5 · p. 29Results
The algorithms significantly outperformed Gurobi in the tested instances; at n = 15 and γ = 0.5, DP-FA solved all 10 in 4.33 seconds versus Gurobi’s 855.94 seconds, with Gurobi failing on 4.
Source: §6.3 · p. 33, §7 · p. 36Takeaways & Limitations
The common-due-date problem is NP-hard even with unit weights, and this hardness implies NP-hardness for more general weighted serial-batch variants.
Source: §7 · p. 36The agreeable-case analysis is limited to due dates and processing times increasing while weights decrease; the increasing-weight variant is not investigated because it lacks the structural property used for a more efficient algorithm.
Source: §5 · p. 29
Abstract
from arXiv · showhide
We study the problem of scheduling jobs on a serial-batch machine with the aim of minimising the total weighted late work. In a serial-batch setting, jobs within a batch are processed sequentially, and none are removed from the machine until the last job in the batch completes its processing. The processing time of a batch is the sum of the processing times of the jobs within it, and the completion time for each job in the batch is equal to the makespan of the jobs in the batch. When a new batch begins, a constant setup time is required for the machine. We show that minimising the total weighted late work in this environment is $NP$-hard even if all jobs have a common due date and unit weight. For the general problem, we present a pseudo-polynomial time dynamic programming algorithm. Additionally, we explore two special cases, i.e., one with a common due date and another with an agreeable condition among due dates, processing times and weights. For both special cases, we develop specialised pseudo-polynomial time dynamic programming algorithms. The proposed approaches are equipped with specialised acceleration techniques to enhance their computational performance. The extended experiments demonstrate that the dynamic programming algorithms outperform Gurobi in time efficiency.
1. Introduction
This paper introduces serial-batch scheduling with total weighted late work, a setting not previously studied, and examines its computational complexity. It motivates this analysis with industrial scheduling scenarios and positions the problem against prior single-machine and batching results.
1. Introduction
- Serial-batch jobs are processed sequentially and remain on the machine until the batch finishes; each job’s late work is the processing performed after its due date.Batch processing time is the sum of its jobs’ processing times, and each job’s completion time is the batch completion time; starting a batch requires a constant setup time.Source: §1 · p. 2
- Serial-batch processing had not been studied for late-work minimization, so the paper focuses on complexity results that can guide research on more complex models.The paper frames its model using established scheduling concepts and motivations rooted in real-world applications.Source: §1 · pp. 2, 4
- Cold-chain fulfillment and aerospace composite cutting illustrate settings where batching, setup operations, and due-date delays can affect freshness, delivery, or material quality.The paper also names aluminium-making, production management, semiconductor manufacturing, and fuel-injector drilling as serial-batch applications.Source: §1 · pp. 2–3
- Prior work found common-due-date late-work problems polynomially solvable on a single machine, while late-work criteria in batching had been studied for parallel, not serial, batches.Potts and Van Wassenhove (1992) and Hariri et al. (1995) give the single-machine results; Zhang and Lin (2005) and Ren et al. (2009) studied parallel-batch variants.Source: §1 · p. 5
- The paper outlines a general pseudo-polynomial algorithm, specialized algorithms for common-due-date and agreeable cases, acceleration techniques, and computational comparisons with Gurobi.The general problem is 1|s-batch|Yw; the agreeable case concerns due dates, processing times, and weights.Source: §1 · pp. 4–5
2. Problem Description
The paper defines total weighted late work on a serial-batch machine and proves hardness using a common-due-date, unweighted special case. It then extends the hardness result to more general variants and describes a pseudo-polynomial dynamic program.
2. Problem Description
- The general model assigns each job a processing time, due date, and weight; batches have summed processing times, constant setup time, and a shared completion time for their jobs.A job’s late work is the portion of its processing time scheduled after its due date, capped at the job’s processing time; total weighted late work sums each job’s late work times its weight.Source: §2 · pp. 6–7
- 1|s-batch, dj = d|Y is NP-hard, so the weighted common-date and varying-date variants are also NP-hard.The proof reduces from Partition to the decision counterpart of the unweighted common-due-date problem.Source: §2 · pp. 7–8
- For the reduction, the constructed jobs use processing times pj = aj and common due date B + 1; the decision question is whether a schedule has Y ≤ B.The decision counterpart has a solution if and only if the Partition instance has a solution.Source: §2 · p. 7
- The general weighted problem has a pseudo-polynomial dynamic program that also applies to the common-due-date and agreeable-condition special cases.The agreeable case orders due dates and processing times increasingly and weights decreasingly.Source: §2 · p. 8
3. Problem 1|s-batch|Yw
This section develops a pseudo-polynomial dynamic programming algorithm for the general 1|s-batch|Yw problem and techniques to accelerate its computation. It specifies the algorithm’s initialization and auxiliary-table preprocessing, then presents DP-F and the exact acceleration framework DP-FA, which preserves DP-F’s recurrences while pruning states that cannot yield an optimal solution.
3. Problem 1|s-batch|Yw
- The proposed pseudo-polynomial time algorithm is accompanied by an acceleration framework to enhance its computational performance.Source: §3 · p. 8
3.1. Dynamic Programming Algorithm
- An optimal schedule can place all late jobs after the non-late jobs and arrange non-late jobs so an earlier-due-date job is at most one batch behind a later-due-date job.Jobs are classified as non-late when Cj ≤ dj + pj and late when Cj > dj + pj.Source: §3.1 · p. 8
- Algorithm DP-F processes jobs in earliest-due-date order, deciding backwards whether each job is non-late or late, with late jobs placed in a final batch.The algorithm considers the first two successive batches containing non-late jobs when constructing a partial schedule.Source: §3.1 · pp. 9, 11
- The empty state has value 0, all other states have value ∞, and the optimum is minimized over the specified initial one- or two-batch states.Source: §3.1 · p. 19
- Auxiliary tables reduce each state transition involving inner minimization to O(1) time when computed between successive job iterations.The tables aggregate recurrence values; due-date minima can be computed in a linear pass, while one case uses suffix minima over completion times.Source: §3.1 · p. 20
- Theorem 2 establishes that Algorithm DP-F solves problem 1|s-batch|Yw.The supplied theorem passage is incomplete, so its stated complexity bound is not available here.Source: §3.1 · p. 21
3.2. Acceleration Framework for Dynamic Programming Algorithm
- DP-FA accelerates DP-F through early termination, an initial upper bound, two lower bounds, and transition-domain reduction.The framework preserves the original recurrences and eliminates states unable to lead to an optimal solution.Source: §3.2 · p. 22
- If a zero-late-work schedule is attainable, an O(n^2) maximum-lateness check lets DP-F terminate immediately with objective value zero.The early termination test is equivalent to checking whether Lmax ≤ 0.Source: §3.2 · p. 22
- EDD-formed feasible schedules provide an upper bound that reduces the state space and tightens transition domains.An optimal schedule stays close to EDD order, with any job delayed by at most one batch.Source: §3.2 · p. 22
- The preemptive lower bound takes O(n log n), while a state-dependent capacity bound checks excess early-due-date processing before either non-late batch; states exceeding the upper bound are pruned.The capacity bound multiplies excess processing by the minimum weight among the affected unscheduled jobs; pruning occurs when accumulated cost plus the maximum of the two lower bounds exceeds UB.Source: §3.2 · pp. 22–23
- The upper bound also restricts a job’s feasible batch completion time during state transitions, reducing the search space.For job Jj, the passage gives t ≤ dj + floor((UB − c)/wj).Source: §3.2 · p. 23
4. Problem 1|s-batch, dj = d|Yw
The common-due-date weighted late-work problem is weakly NP-hard, and the paper gives a specialized dynamic program based on the structure of optimal schedules. It divides those schedules into three cases and solves them with pseudo-polynomial time complexity.
4. Problem 1|s-batch, dj = d|Yw
- The common-due-date weighted late-work problem is weakly NP-hard.Source: §4 · p. 23
- An optimal schedule places late jobs after non-late jobs, has at most two non-late batches, and, if there are two, the second contains one partially early job.The second batch's single job is partially early with respect to the due date.Source: §4 · p. 23
- The dynamic program handles one non-late batch ending by the due date, one ending after it, or two non-late batches with a single straddling job.For the two-batch case, it evaluates each candidate straddling job using prefix and suffix sets, then merges their batch lengths.Source: §4 · pp. 24–25
- O(npmaxd) time for n ≤ pmax and O(n^2d) time for n > pmax solves the common-due-date problem.The three cases cover all possible structures of an optimal schedule.Source: §4 · pp. 25–26
5. Problem 1|s-batch, dj ↑pj ↑wj ↓|Yw
Under the agreeable ordering of due dates, processing times, and weights, the problem remains weakly NP-hard but admits useful schedule structure. Algorithm DP-G uses that structure to solve the case in O(n(sum_i p_i)) time.
5. Problem 1|s-batch, dj ↑pj ↑wj ↓|Yw
- An optimal schedule groups all late jobs at the end and orders non-late batches by non-decreasing due dates.These properties follow under the ordering dj ↑pj ↑wj ↓.Source: §5 · p. 26
- The agreeable case remains weakly NP-hard, despite the structural properties used to design its dynamic program.The paper focuses on the ordering dj ↑pj ↑wj ↓; the dj ↑pj ↑wj ↑ case is handled by the general Algorithm DP-F.Source: §5 · pp. 26, 29
- DP-G processes jobs backward, deciding whether each is late or placed in a non-late batch, with late jobs collected in a final batch.Its transitions consider placing a job with other jobs in the first batch or as that batch's only job.Source: §5 · pp. 27–28
- A precomputed auxiliary function reduces the transition for L = p_j to O(1) lookup time.The auxiliary table aggregates subproblem values for the next job.Source: §5 · p. 28
- O(n(sum_i p_i)) time suffices for Algorithm DP-G on the agreeable case.The bound follows from the algorithm's iterations over jobs and its state-update procedure.Source: §5 · pp. 28–29
6. Computational Experiments
The experiments compare dynamic programs with Gurobi on generated small-scale general instances and large-scale special-case instances. Across the tested settings, the algorithms solve instances that Gurobi often times out on, while performance depends on job count and due-date tightness.
6. Computational Experiments
- The experiments compare C++17 dynamic programs with a Gurobi MILP benchmark, using Python for instance generation and result aggregation.Runs were conducted on an Apple M4 Max system with 36 GB of unified memory.Source: §6 · pp. 29–30
6.1. Instance Generation
- Tests evaluate small-scale general Instant O2O delivery instances for DP-F and DP-FA, alongside large-scale trunk-line cases: common due dates for DP-H and agreeable properties for DP-G.For common-due-date cases, all jobs share a due date with γ ∈ {0.5, 0.7, 0.9}.Source: §6.1 · pp. 30–31
6.2. Performance Metrics
- The study reports mean CPU time and mean number of DP states explored, with each setting run on 10 independent instances.CPU time is capped at 1800 seconds, with unsolved instances recorded at that limit; the superscript indicates the number solved optimally.Source: §6.2 · p. 32
6.3. Computational Results for Algorithms DP-F and DP-FA
- At n=15 and γ=0.5, DP-F and DP-FA solve all 10 instances in 21.85 s and 4.33 s, respectively, while Gurobi needs 855.94 s and misses four.At larger n, Gurobi and DP-F frequently time out, while DP-FA maintains high solvability; pruning suboptimal states curbs DP-F’s state-space growth beyond 2 billion at n=20.Source: §6.3 · p. 33, Table 5 · p. 34
6.4. Computational Results for Algorithm DP-H
- At n=5000, DP-H converges in 1.22 s versus Gurobi’s 565.05 s; at n≤500, DP-H averages under 0.02 s while Gurobi takes up to 1.01 s.For n=5000, increasing γ from 0.5 to 0.9 expands the state space about 1.3 times and raises average CPU time from 0.77 s to 1.22 s.Source: §6.4 · pp. 34–35, Table 6 · p. 35
6.5. Computational Results for Algorithm DP-G
- At n=4000, DP-G solves 9 of 10 instances at γ=0.9, while at n=5000 and γ=0.5 it averages 1272.23 s and Gurobi is entirely intractable.Raising γ from 0.5 to 0.9 at n=4000 expands the state space about 2.3 times and raises DP-G’s average CPU time from 730.97 s to 1736.97 s.Source: §6.5 · pp. 35–36, Table 7 · p. 36
7. Conclusions and Future Research
The paper establishes complexity results for serial-batch scheduling with late-work objectives and develops dynamic programs for the general problem and special cases. Experiments report that the proposed algorithms outperform Gurobi, while future work targets approximation methods and parallel-machine variants.
7. Conclusions and Future Research
- The common-due-date problem is NP-hard even with unit weights, and a pseudo-polynomial dynamic program classifies the general problem as weakly NP-hard.The paper also develops more time-efficient dedicated dynamic programs for the common-due-date and agreeable special cases.Source: §7 · p. 36
- Experiments on test instances of varied characteristics show that the proposed algorithms significantly outperform Gurobi.Table 8 summarizes the paper’s theoretical results.Source: §7 · p. 36, Table 8 · p. 37
- Future work will investigate approximation schemes, parallel-machine late-work problems, and heuristic and metaheuristic approaches.The authors motivate approximation work by the NP-hardness of even special cases on a single serial-batch machine.Source: §7 · p. 37
Appendix: Mathematical formulation
The appendix formulates the general serial-batch weighted late-work problem as a mixed-integer linear program. Its variables and constraints encode job-to-batch assignment, batch usage and completion times, and each job’s late work.
Appendix: Mathematical formulation
- Binary x_jk marks whether job j is assigned to batch k, u_k marks whether batch k is non-empty, and z_j marks whether job j is fully late.The formulation includes nonnegative completion-time and late-work variables, as well as binary decision variables.Source: Appendix: Mathematical formulation · p. 41
- The MILP minimizes total weighted late work, with constraints governing job assignment, consecutive batch use, and batch completion times.The formulation also enforces the late-work definition using an auxiliary binary variable indicating whether a job is fully late.Source: Appendix: Mathematical formulation · pp. 41–42
- The formulation remains valid for common-due-date and agreeable-condition variants, with the common due date substituted for individual due dates in the relevant constraint.Under the agreeable condition, due dates and processing times are nondecreasing while weights are nonincreasing.Source: Appendix: Mathematical formulation · p. 42