Order acceptance and scheduling in capacitated job shops

Florian Lin{\ss}; Janis S. Neufeld; Mike Hewitt; Udo Buscher

REVIEW 3 major objections 5 minor 11 references

Order acceptance and scheduling in capacitated job shops

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A time-indexed MIP formulation solves capacitated job-shop order acceptance to proven optimality on instances with up to 1,000 jobs when capacity is loose, while tight capacity stays hard.

desk verdict New problem, clean MIP, but the 'very large instances' claim is confounded by a fixed short horizon (H ≤ 75) in every test instance. read the letter →

arxiv 2411.19363 v1 pith:GYJYPEYI submitted 2024-11-28 math.OC cs.DM

Florian Lin{ss} , Mike Hewitt , Janis S. Neufeld , Udo Buscher This is my paper · ORCID

classification math.OCcs.DM MSC 90B3590C11

keywords orderacceptancecapacitatedjobshopthroughputmaximizationmixed-integerprogrammingtime-indexedformulationschedulingcapacityplanningagriculturalR&Dpipeline

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that a time-indexed mixed-integer program can solve a capacitated job-shop order-acceptance problem to proven optimality on much larger instances than prior work has addressed, provided that capacity is not tight. The motivating setting is an agricultural research-and-development pipeline in which thousands of candidate projects compete for machines that can process several operations at once, with each project having a release date, a due date, and its own sequence of operations. Because only a small share of projects becomes commercial products, the objective is throughput, the number of projects started. In the computational study, the model proves optimality for every tested instance with up to 1,000 jobs when the capacity factor is 2.0, while tight-capacity instances remain hard; this is the practical payoff the paper argues for.

What carries the argument

The load-bearing object is a time-indexed MIP with binary variables $x_{ijt}$ indicating that job $j$ starts operation $i$ on its required machine at time $t$, and binary variables $z_j$ indicating that job $j$ is accepted. From the release and due dates and processing times, each operation is restricted to a precomputed time window $T_{\sigma_{ij}}=[\alpha_{\sigma_{ij}},\beta_{\sigma_{ij}}]$, which keeps the index set compact. Constraint set (4) is the piece that makes the model capacitated: for every machine and every time slot, the sum of capacity usages $q_{ij}$ over all active operations may not exceed the machine capacity $Q_i$. Precedence constraints chain a job's operations, and acceptance constraints link the decision to start a job with the decision to start every one of its operations, so the objective counts precisely the jobs that can be completed.

What would settle it

Run the same formulation on a real historical set of agricultural R&D projects with about 1,000 jobs and a capacity factor of 2.0; if the solver cannot close the optimality gap within the 1,200-second limit, the claim that loose capacity makes up-to-1,000-job instances provably optimal would be contradicted.

Watch

Extended reading notes

Core claim

The central claim, stated on the paper's own terms, is that the proposed time-indexed MIP formulation is an effective exact method for the combined order-acceptance and capacitated job-shop problem. The model maximizes $\sum_{j\in J}z_j$, the number of accepted jobs, subject to operation-start constraints, precedence constraints, and machine-capacity constraints that allow several jobs to occupy a machine simultaneously. In experiments on 1,680 generated instances with up to 2,000 jobs, the model solved every instance with up to 1,000 jobs to proven optimality at capacity factor $f=2.0$; at $f=5.0$ it solved all instances at every tested size, including 2,000 jobs. Average optimality gaps stay below 7.5% for instances with up to 500 jobs across all capacity factors, whereas the unit-capacity job-shop case averages 11.9%, supporting the paper's conclusion that loose capacity is the key to tractability and that the formulation can support real-world pipeline decisions.

Load-bearing premise

The results depend on the generated test instances faithfully representing a real agricultural R&D pipeline, with processing times, capacity needs, and release dates drawn from the uniform distributions described in Section 3; if real pipelines have tens of thousands of jobs or a different dependency structure, the observed tractability pattern may not carry over.

Editorial extensions

If this is right

At capacity factor $f=2.0$, every tested instance with up to 1,000 jobs is solved to proven optimality, so exact scheduling of loose-capacity R&D pipelines of that size is feasible without heuristics.
Tight capacity is the hard regime, with average optimality gaps reaching 11.9% in the unit-capacity job-shop case, so near-saturated pipelines need heuristic or decomposition methods.
Acceptance rates track capacity but stay below the capacity factor; at $f=2.0$ only 97.8% of jobs are accepted on average, meaning some capacity is lost to release-date and sequencing misalignment.
The length of the due-date time window $w$ has no relevant effect on the acceptance rate, so widening due dates does not by itself increase throughput in the tested instances.
The formulation can provide decision support for real-world pipeline planning, but scaling to tens of thousands of jobs calls for further developments such as heuristics or constraint programming.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

An extension the paper leaves implicit is profit-weighted order acceptance: replacing the unweighted objective with one weighted by per-job profit keeps the same capacity and precedence constraints, and the loose-capacity regime may remain tractable.
Because the capacity factor so strongly predicts difficulty, a testable managerial claim is that adding short-term capacity buffers or shifting release dates could move a hard tight-capacity instance into the provably optimal regime; the paper does not run that experiment.
The uniform synthetic generator may understate real dependencies between projects in an R&D portfolio, so rerunning the same instance design with correlated processing times and project predecessors would show whether the loose-capacity result is an artifact of the generator.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

First, the good news: this paper defines a genuinely new problem — order acceptance in a job shop where each machine can process multiple jobs at once — and the proposed time-indexed MIP is a clean, correct adaptation of Ku and Beck's model. The literature review is honest, and the computational study covers a wide range of job counts and capacity factors. There is no circularity here; the authors do not fit parameters to data.

The main weakness is the horizon. The generator sets d_j = r_j + sum_i p_ij + w, with p_ij in [1,5], m=5, and w in {10,20,30}. That means every due date is at most 75, and the entire planning horizon H never exceeds 75 time periods. So the models are large in the number of jobs (2,000) but tiny in the time dimension. The binary variable count is roughly n*m*(w+1), around 310k for n=2,000 — a moderate MIP by modern standards. The claim that the MIP 'can prove optimality even for very large instances' therefore only applies to instances with a short, narrow horizon. Real R&D pipelines have tens of thousands of jobs and far longer horizons, and the paper gives no evidence that the model scales on the temporal axis. The smooth behavior under loose capacity may be an artifact of narrow time windows making conflicts local, rather than of the capacity factor itself.

Other soft spots: there is no baseline of any kind — a greedy heuristic or CP-SAT would give the numbers context. No code or instances are provided, which makes the experiments hard to reproduce. And the f=1.5 column has bizarre jumps (76% and 223% gaps for n=1,000 and 2,000) that the authors dismiss as outliers; those deserve a real look, since they might indicate a generator or solver issue.

That said, the formulation is sound and the problem is worth having in the literature. The paper deserves serious peer review; a revision should add a horizon sensitivity analysis, soften the 'very large' claim, and ideally release the test instances. I'd send it to review.

Referee Report

3 major / 5 minor

Summary. The paper studies a capacitated job shop scheduling problem with order acceptance, motivated by an agricultural R&D pipeline. A time-indexed MIP is formulated and solved with CPLEX on 1,680 synthetically generated instances with up to 2,000 jobs. The main empirical claim is that the MIP proves optimality for very large instances when capacity is less restrictive, while tight capacity is more challenging. The paper also analyzes the influence of capacity factor and time-window width on acceptance rate and solver performance.

Significance. If the computational claims hold, the formulation could serve as a practical decision-support tool for the motivating application, and the study provides a useful starting point for a problem combination (order acceptance plus capacitated job shop) that appears understudied. The paper's strengths include a clear MIP formulation, a substantial computational study with tabulated results, honest acknowledgment that heuristic approaches are needed for tens of thousands of jobs, and no circular fitting of parameters. However, the scalability claim is weakened by the artificially short planning horizon in the instance generator and by the absence of any baseline comparison; the evidence for 'very large instances' is mixed, with an average gap of 42% for n=2,000 and extreme gap values for f=1.5 at large n. The results are of moderate significance but need stronger support before the central claim can be accepted.

major comments (3)

[Section 3, instance generation parameters] The instance generator fixes r_j ∈ [1,20], m=5, p_ij ∈ [1,5], and d_j = r_j + Σ_i p_ij + w with w ∈ {10,20,30}; consequently every due date is at most 20 + 25 + 30 = 75, so the entire scheduling horizon is never longer than 75 periods and each operation's time window has at most 31 possible start times. The time-indexed model therefore has O(n·m·(w+1)) binary variables and a fixed temporal width: for n=2,000, m=5, w=30 this is roughly 310,000 binaries. The abstract's 'very large instances' claim is thus confined to instances with a short planning horizon and narrow time windows; the paper does not demonstrate scalability in the temporal dimension, which is precisely the dimension that makes time-indexed formulations grow in the long-horizon settings described in the introduction. This is a load-bearing limitation because the motivating problem is stated to involve thousands of jobs, and the conclusion itself acknowledges that heuristics are needed for tens of thousands of jobs. Please either extend the experiments with longer horizons and wider time windows, or carefully rescope the claim.
[Section 3, Table 3 and following paragraph] The reported average gaps for f=1.5 at n=1,000 (76.3%) and n=2,000 (223.1%) are dramatically higher than the neighboring capacity factors, yet the text dismisses them with 'mainly caused by outliers' without presenting any supporting statistics. Since f=1.5 corresponds to a 90.6% average acceptance rate, the non-monotone jump in gap values is itself an important phenomenon that the current explanation does not substantiate. Moreover, Table 2 reports a 42.0% average gap for n=2,000 across all capacity factors, so the statement that the MIP 'can prove optimality for very large instances' overstates the aggregate evidence. Please report the distribution of gaps per cell (median, maximum, count of timeouts, count of instances with extreme gaps) and reassess the wording of the abstract and conclusions.
[Section 3, computational study design] The paper contains no comparison with any alternative solution method. The claim that the proposed MIP is 'efficient' rests entirely on absolute CPLEX gaps for this single model. Since the formulation is described as adapted from Ku and Beck (2016), a baseline comparison against at least one reasonable alternative—for example, a compact event-based model, a constraint-programming formulation, or a dedicated heuristic—is needed to support the claim that the formulation itself, rather than CPLEX's default machinery on a small and highly structured search space, is responsible for the observed performance. Without such a baseline, the contribution of the MIP formulation relative to existing approaches is not established.

minor comments (5)

[Abstract] The phrase 'each of which can process multiple operations simultaneously' would be clearer as 'each machine has a capacity that can be shared by multiple operations simultaneously,' which matches the model's capacity constraint.
[Section 2, Table 1] The notation T_{σ_ij} for the start-time window is introduced only in the text; a formal definition in the table or in a numbered equation would improve readability.
[Section 3, first paragraph] The description of the instance generator does not state the number of replications per (n, f, w) combination; Tables 2 and 3 report 240 instances per n, but the per-cell sample size is unclear from the text. Please specify how many instances were generated for each parameter combination.
[Section 3, text after Table 3] The sentence about 'Intel(R) Xenon(R)' contains a typo; the processor is the Intel Xeon. Please verify hardware names.
[Section 3, capacity factor definition] The interpretation of f as 'the expected acceptance rate if all jobs were equal and evenly distributed over the planning horizon' is informal; providing the exact formula used to set Q_i from f and the generated data would remove ambiguity.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the MIP formulation is an externally adapted model evaluated on generated instances; no prediction reduces to a fitted parameter or self-citation.

full rationale

The paper's contribution is a time-indexed MIP formulation and a computational study. There is no derivation in which an output is defined in terms of an input. The model is adapted from Ku and Beck (2016), an external source, and the instance parameters (p_ij, q_ij, r_j, d_j, f) are experimental design choices, not fitted values. The central claim—that CPLEX can prove optimality for large instances when capacity is loose—is an empirical observation about solver behavior on 1,680 generated instances. The capacity factor f multiplies the average required capacity usage to set Q_i, but the acceptance rate and optimality gap are measured outputs, not inputs to the model. Likewise, the time windows T_sigma_ij are derived directly from release dates, processing times, and due dates, which is definitional but not circular in the prohibited sense. The conclusion's limitation that real pipelines can have tens of thousands of jobs is acknowledged as future work and does not load a self-citation. No reference chain to prior work by the same authors is load-bearing; in fact, the authors cite no prior work of their own. The concern that the short horizon H <= 75 limits scalability is a correctness or external-validity challenge, not a circularity one. Therefore no circular step is present.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The model rests on the standard job shop definition (fixed operation sequence, constant capacity consumption) and on an experimental design that assumes the random instance generator captures the real R&D pipeline. No free parameters are fitted; the capacity factor f and time-window width w are experimental settings, not model parameters.

assumptions (3)

domain assumption Each job's operations must be processed in the given sequence sigma and each operation occupies a constant capacity qij for a fixed processing time pij.
This defines the capacitated job shop problem; it is stated in Section 2 and is standard for the model.
domain assumption The time windows T_sigma_ij derived from release dates, due dates, and processing times are sufficient to enforce that a job's operations can be scheduled in order without considering machine availability when deriving the windows.
The model derives early start and late finish times for each operation from rj and dj; this assumes non-preemptive operations and that the due date constraint is only at the job level. It is a modeling simplification used in constraints (2)-(4).
ad hoc to paper The capacity factor f multiplied by average total required capacity usage yields a meaningful capacity level that corresponds to the expected acceptance rate.
The paper defines machine capacity as f times the average total capacity usage; this identification of f with expected acceptance rate is only approximate for heterogeneous jobs and workloads, yet the paper uses it to interpret acceptance rates versus capacity.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Order acceptance and scheduling in capacitated job shops." pith.science (2026). https://pith.science/paper/GYJYPEYI

@misc{pith2026241119363,
  author       = {Pith},
  title        = {Pith review of: Order acceptance and scheduling in capacitated job shops},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GYJYPEYI}},
  note         = {Machine review of arXiv:2411.19363}
}

read the original abstract

We consider a capacitated job shop problem with order acceptance. This research is motivated by the management of a research and development project pipeline for a company in the agricultural industry whose success depends on regularly releasing new and innovative products. The setting requires the consideration of multiple problem characteristics not commonly considered in scheduling research. Each job has a given release and due date and requires the execution of an individual sequence of operations on different machines (job shop). There is a set of machines of fixed capacity, each of which can process multiple operations simultaneously. Given that typically only a small percentage of jobs yield a commercially viable product, the number of potential jobs to schedule is in the order of several thousands. Due to limited capacity, not all jobs can be started. Instead, the objective is to maximize the throughput. Namely, to start as many jobs as possible. We present a Mixed Integer Programming (MIP) formulation of this problem and study how resource capacity and the option to delay jobs can impact research and development throughput. We show that the MIP formulation can prove optimality even for very large instances with less restrictive capacity constraints, while instances with a tight capacity are more challenging to solve.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

[1]

Christ, Q., Dauzère-Pérès, S., and Lepelletier, G. (2022). A three-step approach for decision support in operational production planning of complex manufacturing systems.International Journal of Production Research, pages 1–26

work page 2022
[2]

Ebben, M. J. R., Hans, E. W., and Weghuis, F. M. O. (2005). Workload based order acceptance in job shop environ- ments. OR Spectrum, 27(1):107–122

work page 2005
[3]

and Briskorn, D

Hartmann, S. and Briskorn, D. (2022). An updated survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 297(1):1–14

work page 2022
[4]

and Beck, J

Ku, W.-Y . and Beck, J. C. (2016). Mixed integer programming models for job shop scheduling: A computational analysis. Computers & Operations Research, 73:165–173

work page 2016
[5]

and Cao, S.-Q

Lei, D.-M. and Cao, S.-Q. (2017). Order acceptance and job shop scheduling: A new neighborhood search. In 2017 Chinese Automation Congress (CAC). IEEE

work page 2017
[6]

Naderi, B., Ruiz, R., and Roshanaei, V . (2023). Mixed-integer programming vs. constraint programming for shop scheduling problems: New results and outlook. INFORMS Journal on Computing

work page 2023
[7]

and Aarts, E

Nuijten, W. and Aarts, E. (1996). A computational study of constraint satisfaction for multiple capacitated job shop scheduling. European Journal of Operational Research, 90(2):269–284

work page 1996
[8]

Slotnick, S. A. (2011). Order acceptance and scheduling: A taxonomy and review. European Journal of Operational Research, 212(1):1–11

work page 2011

Show all 11 references

[9]

Verhoeven, M. (1998). Tabu search for resource-constrained scheduling. European Journal of Operational Research, 106(2-3):266–276

1998
[10]

and Mönch, L

Wang, H.-K. and Mönch, L. (2021). A matheuristic for making order acceptance decisions in multi-product, multi- stage manufacturing systems. Applied Soft Computing, 111:107640

2021
[11]

Xiong, H., Shi, S., Ren, D., and Hu, J. (2022). A survey of job shop scheduling problem: The types and models. Computers & Operations Research, 142:105731. 5

2022

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Christ, Q., Dauzère-Pérès, S., and Lepelletier, G. (2022). A three-step approach for decision support in operational production planning of complex manufacturing systems.International Journal of Production Research, pages 1–26

work page 2022

[2] [2]

Ebben, M. J. R., Hans, E. W., and Weghuis, F. M. O. (2005). Workload based order acceptance in job shop environ- ments. OR Spectrum, 27(1):107–122

work page 2005

[3] [3]

and Briskorn, D

Hartmann, S. and Briskorn, D. (2022). An updated survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 297(1):1–14

work page 2022

[4] [4]

and Beck, J

Ku, W.-Y . and Beck, J. C. (2016). Mixed integer programming models for job shop scheduling: A computational analysis. Computers & Operations Research, 73:165–173

work page 2016

[5] [5]

and Cao, S.-Q

Lei, D.-M. and Cao, S.-Q. (2017). Order acceptance and job shop scheduling: A new neighborhood search. In 2017 Chinese Automation Congress (CAC). IEEE

work page 2017

[6] [6]

Naderi, B., Ruiz, R., and Roshanaei, V . (2023). Mixed-integer programming vs. constraint programming for shop scheduling problems: New results and outlook. INFORMS Journal on Computing

work page 2023

[7] [7]

and Aarts, E

Nuijten, W. and Aarts, E. (1996). A computational study of constraint satisfaction for multiple capacitated job shop scheduling. European Journal of Operational Research, 90(2):269–284

work page 1996

[8] [8]

Slotnick, S. A. (2011). Order acceptance and scheduling: A taxonomy and review. European Journal of Operational Research, 212(1):1–11

work page 2011