{"id":"fcceca1b-f1c0-45dc-9703-a6e5e731ba05","arxiv_id":"2411.19363","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A time-indexed MIP for order acceptance and capacitated job shop scheduling is shown to prove optimality for many large instances when capacity is loose, with tighter capacities remaining hard.","lead":"This paper builds a mixed-integer programming model for scheduling research and development projects in a job shop where each machine can run several jobs at once, and where not every job can be accepted. It tests the model on 1,680 generated instances and finds that large problems with up to 2,000 jobs can often be solved to optimality when machine capacity is plentiful.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claim of solving 'very large' instances is confounded by an artificially short planning horizon (H ≤ 75 periods), so scalability to real-world horizons is unproven.","rationale":"The strongest claim is the empirical scalability of the MIP. For that claim to hold, the large-n instances must be genuinely large in the dimension that drives MIP difficulty. In time-indexed formulations, the number of variables grows with the length of the time windows (roughly n·m·W where W is the window length). The generator sets W = w+1 ≤ 31 and the horizon H ≤ 75. Consequently, the largest instances have only about 3×10^5 binary variables, which is routine for CPLEX. The paper labels n=2,000 as 'very large' but the temporal dimension—where time-indexed MIPs typically blow up—is held artificially tiny. Real agricultural R&D pipelines span months or years with hundreds or thousands of planning periods; the paper itself acknowledges tens of thousands of jobs as future work. Thus the central claim generalizes to practice only if the short-horizon artifact is not the cause of solvability. The reader's concern about distributional representativeness is valid but less precise; the specific mechanism here is that release/due-date ranges force H ≤ 75. This is directly testable. I agree with the reader's CONDITIONAL verdict, but the condition should explicitly include re-running with realistic horizons and reporting model sizes. The MIP formulation itself appears correct—constraints (2)–(4) properly enforce acceptance, precedence, and cumulative capacity—so this is not an internal correctness flaw but an external validity gap in the central scalability claim.","tokens_in":5184,"tokens_out":9578,"duration_ms":80156,"concrete_test":"Rerun the n=2,000, f=2.0 experiments with the same distributions except extend the time horizon: set rj ~ U[1,500] and w ∈ {100,200,500} (keeping pij and qij as before), so the maximum due date grows to about 1,025 while the capacity factor definition is unchanged. If the optimality gap for n=2,000 degrades substantially (e.g., from the reported 23.8% to above 50% or unsolved within 1,200 seconds), the reported scalability is an artifact of the ≤75-period horizon. As a secondary check, report the number of binary variables and constraints for the largest instances to contextualize what 'very large' means.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that the time-indexed MIP proves optimality for very large instances when capacity is loose. However, the instance generator fixes release dates rj ∈ [1,20] and due dates dj = rj + Σ_i pij + w with w ∈ {10,20,30}. Since each job has m=5 operations and pij ∈ [1,5], the maximum total processing time is 25, so every due date is at most 20+25+30 = 75. Thus the entire scheduling horizon H is at most 75 time periods, independent of n. The time-indexed model has O(n·m·(w+1)) binary variables—for n=2,000, m=5, w=30 this is about 310,000 binaries, a moderate-size MIP by modern standards. The 'very large' label refers only to the number of jobs, not to the temporal dimension; real R&D pipelines the paper cites have tens of thousands of jobs and far longer planning horizons. The proved optimality under f=2.0/5.0 may be driven by the narrow time windows and short horizon that make capacity conflicts localized and the LP relaxation easy, rather than by loose capacity alone. Without varying the horizon length, the abstract's claim that the MIP 'can prove optimality even for very large instances with less restrictive capacity constraints' is not supported for realistic problem sizes.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":5430,"tokens_out":5357,"duration_ms":48054,"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":[{"comment":"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":"Section 3, instance generation parameters"},{"comment":"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":"Section 3, Table 3 and following paragraph"},{"comment":"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.","section":"Section 3, computational study design"}],"minor_comments":[{"comment":"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":"Abstract"},{"comment":"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":"Section 2, Table 1"},{"comment":"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":"Section 3, first paragraph"},{"comment":"The sentence about 'Intel(R) Xenon(R)' contains a typo; the processor is the Intel Xeon. Please verify hardware names.","section":"Section 3, text after Table 3"},{"comment":"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.","section":"Section 3, capacity factor definition"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope for math.OC, but the central scalability claim needs substantial qualification. The bounded-horizon concern in the stress-test assessment is valid and should be addressed by either extending experiments with longer horizons or explicitly limiting the claim to short-horizon instances. The lack of any baseline comparison is also a nontrivial weakness for a journal submission. The extreme gap values at f=1.5 and large n require a more principled explanation than 'outliers.'"},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nOther 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.\n\nThat 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.","headline":"New problem, clean MIP, but the 'very large instances' claim is confounded by a fixed short horizon (H ≤ 75) in every test instance.","tokens_in":5965,"tokens_out":3468,"would_cite":true,"duration_ms":28591,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90B35","90C11"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["order acceptance","capacitated job shop","throughput maximization","mixed-integer programming","time-indexed formulation","scheduling","capacity planning","agricultural R&D pipeline"],"falsifier":"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.","tokens_in":4952,"feed_emoji":"🌱","tokens_out":11778,"duration_ms":91356,"temperature":0.7,"pith_summary":"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.","feed_headline":"Scheduling model proves 1,000-job pipelines solvable","feed_subtitle":"A time-indexed model proves optimality when capacity is loose; tight capacity remains hard to solve.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"It supplies the base time-indexed job-shop MIP model that the paper adapts by adding machine capacities and acceptance variables.","marker":"Ku and Beck (2016)"},{"why":"It defines the capacitated job shop with simultaneous operation processing, the modeling convention the paper follows.","marker":"Nuijten and Aarts (1996)"},{"why":"It provides the order-acceptance taxonomy and the throughput-maximizing framing for the acceptance decision.","marker":"Slotnick (2011)"},{"why":"It represents prior work on order acceptance in job shops without simultaneous machine processing, which the paper extends.","marker":"Ebben et al. (2005)"},{"why":"It supplies the recent survey of resource-constrained project scheduling used to position the problem.","marker":"Hartmann and Briskorn (2022)"},{"why":"It formulates a resource-constrained scheduling variant with simultaneous resource use, a close relative of the model studied here.","marker":"Verhoeven (1998)"}],"fun_headline_variants":["MIP cracks 1,000-job job shops with loose capacity","Exact scheduling for 2,000-job pipelines when capacity eases","Order-acceptance MIP scales to 1,000 jobs at high capacity","Job-shop solver proves 1,000 jobs, struggles when capacity tight"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["MIP cracks 1,000-job job shops with loose capacity","Exact scheduling for 2,000-job pipelines when capacity eases","Order-acceptance MIP scales to 1,000 jobs at high capacity","Job-shop solver proves 1,000 jobs, struggles when capacity tight"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00024,"raw_usage":{"total_tokens":1524,"prompt_tokens":957,"completion_tokens":567,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":573,"completion_tokens_details":{"reasoning_tokens":486}},"tokens_in":573,"tokens_out":567,"duration_ms":4683,"temperature":1.0,"reasoning_tokens":486,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T10:14:28.909993+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"and Aarts, E","cited_arxiv_id":null,"evidence_quote":"It defines the capacitated job shop with simultaneous operation processing, the modeling convention the paper follows."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It provides the order-acceptance taxonomy and the throughput-maximizing framing for the acceptance decision."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It represents prior work on order acceptance in job shops without simultaneous machine processing, which the paper extends."},{"cited_title":"and Briskorn, D","cited_arxiv_id":null,"evidence_quote":"It supplies the recent survey of resource-constrained project scheduling used to position the problem."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It formulates a resource-constrained scheduling variant with simultaneous resource use, a close relative of the model studied here."}],"review_version":1}