CS Paper Radar

Serial-batch scheduling to minimise the total weighted late work

Yao-Wen Sang, Naiming Xie, Jian Chen, Malgorzata Sterna, Jacek Blazewicz

cs.DS ·submitted 2026-09-16 02:49 UTC · v1

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Asymmetric Weighted Earliness-Tardiness: Scheduling with a Nonrestrictive Common Due Date

cs.CC math.OCcs.DMmath.CO ·2026-09-12 ·Nicholas G. Hall, Hans Kellerer, Miao Song
similarity 0.67
Abstract · 268 pages, 12 figures, 29 tables

Single-machine asymmetric weighted earliness--tardiness (AWET) scheduling asks how to sequence jobs around a common synchronization date when early and late completion incur unrelated job-dependent penalties. At the boundary nonrestrictive date $d=\sum_jp_j$, a compact V-shaped schedule reduces the continuous-time problem to a quadratic choice of a nonempty early set. We establish four complementary results for this model. First, the positive-integer problem is strongly NP-complete by a unary-polynomial reduction from Restricted Exact Cover by 3-Sets. Second, unrestricted AWET admits a polynomial-time $(3+2\sqrt2+\varepsilon)$-approximation based on an anchored semidefinite relaxation and deterministic marginal thresholding. Third, when the earliness and tardiness ratio orders are strict reversals, the problem is weakly NP-complete but has an exact two-resource pseudopolynomial dynamic program. Fourth, for fixed total refinements whose ratio permutation is separable, an exact separating-tree recurrence and coordinated geometric trimming yield an FPTAS. The proofs use different manifestations of the same canonical objective: scale-separated prefix penalties, positive-semidefinite minimum-kernel covariance, a dominant completed load square, and a bounded four-coordinate decomposition interface. Together, the results show that the decisive issue is not merely whether the two ratio orders agree, but whether their interaction can be controlled by a global certificate or compressed into a bounded constructive interface.

0.21

Approximation algorithms for identical parallel machine scheduling with assignment costs

cs.DS ·2026-10-24 ·Wei Li
similarity 0.67
Abstract

We study non-preemptive scheduling on identical parallel machines in which assigning job $j$ to machine $M_i$ incurs the cost $c_{ij}=a_iw_j+b_j$. The processing times $p_j$ and the cost weights $w_j$ are independent, and the number of machines is part of the input. For every fixed $\varepsilon\in(0,1]$ and every deadline $T$ for which a schedule with makespan at most $T$ exists, we give a polynomial-time algorithm that computes a schedule with makespan at most $(1+\varepsilon)T$ whose total assignment cost does not exceed the minimum under the deadline $T$. Using this algorithm as a subroutine, we obtain a polynomial-time approximation scheme for minimizing the makespan under a total cost budget whose schedules always satisfy the budget; this answers an open question for costs $c_{ij}=l_ic_j$ with $c_j$ independent of $p_j$. For the lexicographic problem, in which the total assignment cost is minimized among all schedules of minimum makespan, we obtain in polynomial time a schedule with makespan at most $1+\varepsilon$ times the minimum and total assignment cost at most that of a lexicographically optimal schedule; this improves the makespan guarantees of earlier algorithms for additive and multiplicative costs. For costs $c_{ij}=s_i+a_iw_j$, where $s_i$ is charged for each job processed on $M_i$, the same guarantees are obtained in quasi-polynomial time.

0.24

An EPTAS for Vector Scheduling with Time Intervals

cs.DS cs.CC ·2026-09-27 ·Junho Hwang
theory similarity 0.67
Abstract · 18 pages, 4 figures. v2: extended to several resources and unrelated machines, with a new title and simplified proofs

We study vector scheduling in which each job is active during a fixed time interval. A job uses several resources and stays on one machine for its entire interval; its resource requirements may depend on the machine. The objective is to minimize the largest resource load over all machines and times. For $r$ machines and $d$ resources, we give a deterministic $(1+\varepsilon)$-approximation in $f(r,d,1/\varepsilon)N^{O(1)}$ time, where $N$ is the binary input length. This gives an efficient polynomial-time approximation scheme for fixed $r$ and $d$, extending approximation schemes for scalar temporary tasks assignment. The algorithm merges jobs into blocks whose time intervals are fixed before any machine is chosen, and assigns the blocks by dynamic programming over a balanced recursive split of the time line. We also prove strong NP-hardness and an exponential lower bound in $1/\varepsilon$ under the Exponential Time Hypothesis, already for two identical machines and one resource.

0.13

Strong NP-Hardness and Approximation Algorithm for Weighted Tardiness with Release Dates and Identical Processing Times

cs.CC cs.DMmath.CO ·2026-09-23 ·Zhi-Long Chen, Nicholas G. Hall
theory similarity 0.64
Abstract · 38 pages, 2 figures, 5 tables

We study nonpreemptive scheduling on a single machine with release dates, due dates, positive job weights, and a common processing time. The objective is to minimize total weighted tardiness. Although closely related equal-processing-time problems admit polynomial-time algorithms, the complexity of this problem has remained open in the literature since 2010. We prove that its decision version is strongly NP-complete, even when every job can meet its due date if processed immediately upon release. The reduction is from unweighted MAX-CUT and uses a quadratic number of jobs with polynomially bounded numerical data. Its main ingredient is a constructive normalization theorem that converts every sufficiently inexpensive feasible schedule into a binary choice for each graph vertex; after normalization, total weighted tardiness equals a constant minus a scaled cut value. We also give a deterministic polynomial-time phase-grid assignment algorithm for the shifted objective $Φ=F+p\sum_jw_j$, where $F$ is total weighted tardiness. The algorithm enumerates at most $N$ release-date residues modulo $p$, solves one minimum-cost assignment problem for each residue, and returns the best phase-grid schedule. It runs in $O(N^5)$ arithmetic operations and achieves the tight ratio $3/2-1/(2N)$ for this algorithm. Because the added term $p\sum_jw_j$ is independent of how the jobs are scheduled, the shifted and original objectives have exactly the same optimal schedules. However, the approximation guarantee applies to the shifted objective; for the original objective, the analysis provides an additive bound. Thus, the paper both resolves the long-standing complexity question and provides a complementary worst-case guarantee for the phase-grid assignment algorithm.

0.21

Scheduling to Maximize Weighted Throughput with an Active-Time Budget

cs.DS ·2026-08-29 ·Susanne Albers, G. Wessel van der Heijden
publishedtheory similarity 0.64
Abstract · 16 pages, 5 figures, To appear at WAOA 2026

We study the active-time scheduling problem with weighted throughput maximization. In this setting, a set of $n$ jobs $J$ arrive at integer release times, each with an integer processing time and integer deadline. Jobs may be preempted at integer time slot boundaries. A schedule assigns jobs to time slots, with at most $m$ jobs assigned to the same time slot. A slot is called \emph{active} if at least one job is scheduled in it. Instead of scheduling all jobs to minimize the number of active time slots, we consider the more general variant of \emph{weighted throughput} with an active-time budget $K$, where each job $j\in J$ has a weight $w_j$. The objective is to maximize the total weight of \emph{completed} jobs using at most $K$ active time slots. This means that partially scheduled jobs do not count towards the objective. The classical active-time minimization problem is recovered by asking whether all jobs can be completed within a given active-time budget. We give hardness, approximation, and exact algorithmic results. For general intervals with unbounded parallelism, we prove NP-hardness, rule out an FPTAS unless $\mathrm{P}=\mathrm{NP}$, and give a pseudo-polynomial time $Ω(1/\log K)$-approximation. For proper intervals, we prove a canonical structural lemma and obtain an exact $(nK)^{O(m)}$-time algorithm. For laminar intervals, we give an exact $f(K,m)\cdot n^{O(1)}$-time algorithm.

0.25

Compressing the Lawler-Moore Dynamic Program for Weighted Tardy Jobs

cs.DS ·2026-10-30 ·Klaus Jansen, Björn Schumacher, Corinna Wambsganz
similarity 0.63
Abstract

The classic scheduling problem of minimizing the total weight of tardy jobs ($P_m||\sum_jw_jU_j$) asks for a schedule of jobs each with a processing time, weight, and due date on a constant number of parallel identical machines. A job is late in a schedule if it completes after its due date, and an optimal schedule is one where the total weight of all late jobs is minimized. The classic dynamic programming algorithm of Lawler and Moore [Manag. Sci., 1969] solves this problem in $O(nd_{\max}^m)$ where $n$ is the number of jobs, $d_{\max}$ is the maximum due date of any job, and $m$ is the number of identical machines. We show that it is sufficient to only compute part of the dynamic program and obtain the running time $\tilde{O}(n + d_{\max}^{m + 1})$ where $\tilde{O}$ suppresses polylogarithmic factors. This affirmatively answers the open question posed by Hermelin, Molter, and Shabtay [INFORMS J. Comput., 2024], whether a running time of $\tilde{O}(n + d_{\max}^2)$ is possible on a single machine.

0.24

An FPTAS for Two-Machine Open-Shop Scheduling with a Single Unavailability Interval

cs.DM ·2026-09-10 ·Hao Lu, Yuan Yuan, Xingwu Liu, Xin Han, Yong Zhou
similarity 0.61
Abstract

We consider the two-machine open-shop scheduling problem in which one machine is unavailable during a fixed interval. We study the resumable setting: an operation interrupted by the unavailability interval may resume, without penalty, when the machine becomes available. The objective is to minimize the makespan. Although the problem is NP-hard and several approximation algorithms are known, whether it admits a fully polynomial-time approximation scheme (FPTAS) has remained open for two decades. We resolve this question affirmatively by giving the first FPTAS, thereby strengthening the previously known polynomial-time approximation scheme (PTAS). As an intermediate result, we develop a new pseudo-polynomial dynamic program with seven state dimensions, improving on the ten-dimensional formulation in the literature.

0.33

What to Predict for Efficient Scheduling on Parallel Machines

cs.DS ·2026-11-10 ·Evripidis Bampis, Bruno Escoffier, Dimitris Fotakis, Giorgos Mitropoulos, Michalis Xefteris
top venue similarity 0.61
Abstract · Accepted at NeurIPS 2026

We study learning-augmented algorithms for scheduling on multiple parallel machines under the objectives of minimizing the makespan or the total weighted completion time. We assume that the algorithm has access to noisy information (the prediction) about an optimal solution, expressed through a solution encoding that implicitly quantifies both the amount of information provided and the nature of noise (errors in the prediction). Our central question is to determine the maximum level of noise that still allows for efficiently recovering this optimal solution. We observe that information guiding greedy scheduling to optimality or revealing the optimal assignment of tasks to machines is very sensitive to noise, and prove that recovering an optimal solution from solution encodings capturing either is computationally hard, even for a small (non-constant) number of errors. On the positive side, we show that an order-based encoding, which leads to errors that are dispersed locally, is robust to noise. We present a dynamic programming framework that utilizes this encoding and solves optimally several classical scheduling problems, including makespan and total weighted completion time minimization on identical or unrelated machines.

0.36