{"id":"1ee78d70-1feb-4be7-80b7-5cb33b0becd6","arxiv_id":"2506.10405","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"The paper introduces B&B-SPACES, an exact branch-and-bound method with bin-packing heuristics that solves single-machine time-of-use energy scheduling about 100 times faster than prior ILP models on tested benchmarks.","lead":"An exact branch-and-bound scheduler for one machine under time-of-use electricity prices uses bin-packing insights to cut solution times dramatically. It can handle hundreds of jobs and thousands of price intervals, much faster than previous ILP-based solvers.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the paper's own {8,10} limitations are honestly stated and do not contradict the central speedup claim.","rationale":"The reader's weakest_assumption is that the entire speedup rests on the bin-packing heuristic's success, and that the {8,10} failures undermine the claim. I see this as a well-identified soft spot, but not a load-bearing flaw in the paper's actual claim. The paper makes two distinct claims: (1) B&B-SPACES outperforms ILP-SPACES by two orders of magnitude on the standard Shrouf/Benedikt benchmark, and (2) it can solve large instances with real energy prices and 200 jobs more than 100 times faster than existing methods. Claim (1) is strongly supported by Table 1. Claim (2) is supported by Table 2 for all reported processing-time groups except {8,10}, and the paper itself flags {8,10} as the hard group. A claim that an algorithm is 'capable of solving benchmark instances with 200 jobs more than 100 times faster' is a claim about typical or benchmark capability, not a universal guarantee for all processing-time distributions. The paper's own Section 5.3 explains the hardness through the number-partitioning phase transition, which is a plausible and well-grounded explanation. I therefore do not see a fatal internal inconsistency. My main residual concern is the absence of the code and data, which is precisely what the reader's conditional verdict addresses. The fixed-sequence formula in Eq. (4.5) has a notation typo (c(job)_j,pi(l) instead of c(job)_pi(l),i) but this is a typographical slip and is recoverable from context. I partially agree with the reader: the {8,10} failures are a real limitation and should be stated more carefully in the abstract, but they do not overturn the central claim. The concrete test of requesting and rerunning the code is the natural next step, and it matches the conditionality of the reader's verdict. I would keep the verdict CONDITIONAL but for the reason of missing artifacts rather than for a suspected algorithmic flaw.","tokens_in":24208,"tokens_out":2475,"duration_ms":23830,"concrete_test":"Request the authors' code and instance generator, then run B&B-SPACES against ILP-SPACES under the same machine and solver environment on the twelve instances in Table 1 and on the {8,10} group from Table 3. Verify that the reported 10x-100x speedups reproduce, and check whether the {8,10} failures remain failures when the CP Optimizer packing subroutine is replaced by a different bin-packing solver; if the failures disappear or the speedups vanish, the central claim needs revision. As a purely analytic check, recompute the objective of the fixed-sequence example in Figure 1 using the definitions in Section 4.1 to confirm the claimed optimum of 342 and the corrected edge weight formula.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I read the paper in good faith and examined the speedup claim against the paper's own evidence. The central claim is that B&B-SPACES solves large TOU instances more than 100 times faster than ILP-SPACES, and that this speedup comes from bin-packing primal heuristics closing subtrees early. The paper's own Section 5.2 and Table 3 report that for the {8,10} processing-time group, 5 of 20 instances at n=150 and 5 of 20 at n=200 hit the 10-minute limit without proven optimality, with gaps around 0.02%. This is an explicit limitation and it does not contradict the headline claim: the abstract claims the algorithm is capable of solving benchmark instances with 200 jobs more than 100 times faster than existing state-of-the-art methods, and Table 2 shows n=200 solved in 0.61-1.46 s for all groups except {8,10}, so the central claim is supported for the benchmark class it describes. The abstract's '200 jobs' statement could be read as universal, but the paper's own Section 5.3 carefully identifies the {8,9,10} group as the hard region and the conclusion explicitly acknowledges the limitation. I also checked the main mathematical derivation. The job-interval graph lower bound in Section 4.2 and the gcd tightening in Section 4.3 are valid relaxations: splitting jobs into unit jobs cannot decrease cost, and replacing unfixed jobs by gcd-sized jobs is a valid relaxation only if the gcd-sized jobs are interchangeable, which they are because they are identical. The PBin-Pack argument in Section 4.4 is sound as an exact mechanism for proving optimality when the packing succeeds. I found one unattributed equation typo in the fixed-sequence objective: Eq. (4.5) uses the notation c(job)_j,pi(l) but defines c(job)_j,i; this is a notation slip rather than a mathematical error.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper addresses the single-machine scheduling problem 1,TOU|states|TEC with time-of-use energy tariffs and machine states. The authors design an exact branch-and-bound algorithm, B&B-SPACES, that reuses the SPACES precomputation of optimal state switching, computes lower bounds by relaxing unfixed jobs to unit-length or gcd-length jobs, and uses bin-packing-derived primal and initialization heuristics. Extensive experiments on NOSBY/TWOSBY benchmarks and on instances with historical OTE prices report that B&B-SPACES solves most tested instances with 150-200 jobs in under a few seconds, roughly two orders of magnitude faster than the previous ILP-SPACES model, while a hard processing-time group {8,10} is honestly reported to contain instances not solved to optimality within 10 minutes with gaps below 0.03%.","tokens_in":24598,"tokens_out":25339,"duration_ms":327276,"significance":"If correct, B&B-SPACES represents a substantial practical advance for an NP-hard problem: exact solutions for hundreds of jobs over more than a thousand intervals in seconds to minutes. The algorithm has no fitted free parameters, and the lower-bound claims rest on explicit (if concise) mathematical arguments. The experimental protocol is credible, with machine-checkable comparisons against an external ILP solver, and the authors disclose the hard {8,10} instances rather than omitting them. The main limitations are the lack of released code/data and an ambiguity in the model regarding the processing state under negative energy prices, which should be resolved before final acceptance.","major_comments":[{"comment":"The stated model does not explicitly require that the machine be in the processing state only while a job is processed; Condition 2 is one-directional. Because the paper explicitly admits negative energy costs, optimal switching costs c⋆ (Appendix A) may keep the machine in proc during gaps, and the PBin-Pack construction may leave proc intervals with no job. If the intended semantics is that proc is only used for job processing (as in the Shrouf et al. model), then the lower-bound relaxations and the pack-derived feasible schedules need an additional argument to exclude empty-processing solutions; otherwise the algorithm may certify costs that are not attainable in the intended problem. Please clarify the model and, if needed, strengthen the proofs or add a constraint.","section":"Section 2, Conditions 1-4; Propositions 1-2; Section 4.4"}],"minor_comments":[{"comment":"The first term should be c(job)_{π(ℓ), i} and the switching argument should be (i + p_{π(ℓ)} - 1, i'), not (i + p_{π(n)} - 1, i'); as written the indices are inconsistent with (4.6) and with the layer ℓ.","section":"Equation (4.5)"},{"comment":"Use an explicit fraction (1/gcd(...)) · sum p_j' to avoid the ambiguous exponent-like notation 'gcd(J\\bJ)^{-1}'.","section":"Equation (4.10)"},{"comment":"The PBin-Pack formulation packs the whole job set J into the bins Λ_k, even though the lower-bound sequence has already fixed the prefix bπ. This is acceptable if the resulting solution is treated as a global primal bound that may reorder the prefix, but the text should state this explicitly to avoid confusion about the node's partial sequence.","section":"Section 4.4"},{"comment":"The paper does not include code or data; providing the generated instances and the implementation would materially strengthen reproducibility of the speedup claims.","section":"Reproducibility"},{"comment":"The phrase 'with 200 jobs more than 100 times faster' is too broad, given Table 2 reports that for the {8,10} group B&B-SPACES leaves 5/20 instances at n=200 unsolved within the 10-minute limit; please qualify the claim.","section":"Abstract and Section 5.2"},{"comment":"The text contains a typo: 'wheres' should be 'whereas'.","section":"Section 5.1"}],"recommendation":"major_revision","confidential_remarks":"To the editor: The paper is a strong algorithmic contribution with convincing speedups on the tested benchmarks, but the lack of code/data and the modeling ambiguity about empty processing under negative prices are the main points to resolve. The comparison is only to the authors' previous ILP models; while this is the previous state of the art, an independent implementation or a third-party baseline would strengthen the claims. Overall, the work fits the journal's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"What should you know about this one? It is a serious exact algorithm paper. The authors take the SPACES precomputed optimal switchings from Benedikt et al. (2020) and observe that the 'spaces' between processing intervals behave like bins into which jobs must be packed. That reframing drives a lower bound, a primal heuristic, and an initialization scheme, and it pays off: on the standard NOSBY/TWOSBY benchmarks B&B-SPACES is 10–100× faster than the prior ILP-SPACES, and on real OTE price data it solves most n=200 instances in a couple of seconds. The paper is honest about the one hard region: with processing times in {8,10}, 5 of 20 instances at n=150 and 5 of 20 at n=200 hit the 10-minute limit with gaps around 0.02%, and Section 5.3 explains this via a bin-packing phase transition.\n\nThe genuinely new pieces are the gcd-based tightening of the unit-job lower bound, the bin-packing primal heuristic that closes subtrees when the relaxed spaces can be packed by the original jobs, and the bin-finding initialization. The fixed-sequence evaluation is also improved: by folding optimal switching costs into the job-interval graph, the authors get O(h^2 n) per fixed sequence, avoiding the pseudo-polynomial dependence on processing times. The lower-bound proofs are correct; Proposition 2 is terse but the relaxation argument holds because identical gcd-sized jobs are interchangeable.\n\nNow the caveats. No code or data are shipped, which matters for a speedup claim; the experiments are thorough but we cannot rerun them. There are equation typos in the core derivation: Eq. (4.5) writes c⋆(i + pπ(n) − 1, i′) but it should be pπ(ℓ), and the c(job) notation mixes j and π(ℓ). These are slips, not substantive errors, but they need fixing. The abstract's '200 jobs more than 100 times faster' is too sweeping — Table 2 shows it is true for most processing-time groups, but the {8,10} group is a clear exception, and the conclusion should say so in the abstract. That said, the paper itself flags this limitation explicitly, so it is an overstatement in the summary rather than a hidden failure.\n\nWho is this for? Anyone working on exact methods for single-machine scheduling with time-of-use prices and power-saving states. It deserves a serious referee. I would ask for the code or at least the instance generator, and a corrected abstract. The central contribution — seeing the bin-packing structure and exploiting it — is real and likely to generalize.","headline":"A credible exact branch-and-bound for TOU scheduling with real speedups; the bin-packing lens is the real insight, but the abstract oversells the 200-job claim for hard {8,10} instances.","tokens_in":25178,"tokens_out":2614,"would_cite":true,"duration_ms":28296,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90B35","68M20","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that a new exact branch-and-bound algorithm, B&B-SPACES, exploits a hidden bin-packing structure in single-machine time-of-use energy-cost scheduling to solve 200-job instances more than 100 times faster than the…","keywords":["scheduling","time-of-use tariffs","machine states","total energy cost","branch and bound","bin packing","lower bound","job-interval graph"],"falsifier":"Run B&B-SPACES on a family of instances with real TOU prices and processing times drawn only from {8,9,10} at n=200, the parameter region the paper identifies as hardest. If 10-minute time-limit hits persist or grow, and the proven lower bound never closes the gap, then the claimed two-orders-of-magnitude speedup does not hold in the regime where the packing assumption breaks down; the paper’s own Table 3 already shows such failures for {8,10}, so the decisive test is enlarging that class and comparing node counts against an exact bin-packing oracle.","tokens_in":24065,"feed_emoji":"🔋","tokens_out":5698,"duration_ms":69797,"temperature":0.7,"pith_summary":"The paper aims to show that the strongly NP-hard single-machine scheduling problem 1,TOU|states|TEC, where a machine with several states processes jobs over a horizon of time-of-use energy prices, can be solved exactly at much larger scale than previously possible. Its proposed algorithm, B&B-SPACES, interprets the “spaces” left by optimal machine switching as bins into which the jobs must be packed, and uses that viewpoint to build lower bounds, primal heuristics, and initialization routines that close search subtrees early. Reported experiments show speedups of two orders of magnitude over prior mixed-integer linear programming approaches, with many 150–200 job instances over more than a thousand intervals solved in seconds. The practical stake is that exact optimal schedules, not just heuristics, become feasible for week-long horizons at 15-minute resolution, enabling rapid re-scheduling when energy prices move.","feed_headline":"Exact scheduler beats prior ILP by 100x on time-of-use energy costs","feed_subtitle":"A branch-and-bound algorithm exposes hidden bin-packing structure, solving 200-job week-long scheduling in seconds.","key_machinery":"The central object is the set of “spaces”: the maximal consecutive intervals in which the machine is in the processing state in an optimal relaxed schedule, produced from the precomputed optimal switching costs. These spaces act as bins for a packing problem, and the algorithm’s main components are: the job-interval graph for a fixed job sequence, whose shortest path gives the lower bound in polynomial time; the PBin-Pack feasibility problem that tries to pack the original jobs into those bins; the PBin-Find initialization problem that enlarges bins to construct a first feasible upper bound; and the gcd-based relaxation that tightens the lower bound when the remaining processing times are non-coprime.","core_discovery":"The central claim is that the efficiency of an exact algorithm for 1,TOU|states|TEC comes from exposing the bin-packing structure hidden inside the optimal switching problem. For a fixed job sequence, the optimal total energy cost is computed as a shortest path in a job-interval graph whose edge weights already contain the precomputed optimal switching costs, avoiding an explicit pseudo-polynomial state model. While branching on the unfixed jobs, the remaining jobs are relaxed into unit-size jobs (or jobs of size equal to the gcd of the remaining processing times); the optimal relaxed schedule then consists of maximal consecutive processing intervals, called spaces or blocks, which act as bins. If the original jobs can be packed into those bins, the primal solution matches the lower bound and the whole search subtree is pruned. The paper reports that this mechanism solves the standard benchmark set at least 100 times faster than previous ILP models, and that the residual hard cases are concentrated in processing-time groups with long, low-variability jobs such as {8,10}.","pith_inferences":["Testable extension: the same exposed-bin architecture could be carried to other time-of-use scheduling variants by editing the job-interval graph, for instance adding release times and deadlines as edge prunings or handling multiple dedicated processing states as job families, which the paper explicitly lists as plausible next steps.","Our inference: the average-case difficulty of these instances likely follows a phase-transition pattern inherited from number partitioning and bin packing; if so, random processing-time groups near a critical mean or variance, rather than large job counts, should become the natural stress-test benchmark.","Testable extension: replacing the packing oracle inside the primal heuristic with a dedicated exact bin-packing solver or with polynomial-time online heuristics could reduce the remaining {8,10} failures, since the paper’s bottleneck is precisely the frequency with which an exact packing is found.","Our inference: if the speedup transfers to parallel machines or flow shops with stateful resources, then fine-grained whole-factory demand-response scheduling under real-time prices becomes computationally plausible, though the paper does not report such an extension."],"forward_implications":["Exact optimal schedules for 150–200 jobs over more than a thousand time intervals can be computed in seconds to minutes, replacing hours-long ILP runs on realistic time-of-use tariffs.","The standard benchmark instances used since Shrouf et al. (2014) are not hard enough to discriminate methods; harder benchmarks with historical price profiles are needed to expose algorithmic behavior.","The instance hardness is governed less by the number of jobs and more by the structure of the processing times: high variability, especially with short jobs, makes the bin-packing primal heuristic succeed often, while long and nearly uniform processing times such as {8,10} produce the hardest instances.","For the unsolved {8,10} instances at n=150 and n=200, the proven gaps are below 0.026%, so even when optimality is not proven, the method returns solutions that are essentially optimal in practice."],"supporting_citations":[{"why":"Introduces the 1,TOU|states|TEC problem, the transition graph model, and the original ILP formulation that serves as the first baseline.","marker":"Shrouf et al. (2014)"},{"why":"Proves strong NP-hardness of the problem without fixed job order and provides the polynomial-time fixed-sequence solution via a job-interval graph, which the paper extends.","marker":"Aghelinejad et al. (2019)"},{"why":"Supplies the SPACES preprocessing that precomputes optimal switching costs, and the previous state-of-the-art ILP model that B&B-SPACES compares against and outperforms.","marker":"Benedikt et al. (2020)"},{"why":"Provides the ILP model without preprocessing (ILP-REF), used as the second comparison baseline in the experiments.","marker":"Aghelinejad et al. (2018)"},{"why":"Motivates the bin-packing viewpoint that is the main source of algorithmic efficiency in B&B-SPACES.","marker":"Grus et al. (2024)"},{"why":"Supplies the number-partitioning phase-transition analysis used to interpret why certain processing-time groups make instances hard or easy.","marker":"Mertens (2003)"},{"why":"Connects the observed hardness to phase transitions in multiprocessor scheduling, supporting the paper’s explanation of instance difficulty.","marker":"Bauke et al. (2003)"}],"fun_headline_variants":["Branch-and-bound plus bin packing cuts TOU scheduling by 100x","Bin packing unlocks 100x speedup for time-of-use scheduling","Exact TOU scheduling: 200 jobs solved 100x faster via bin packing","Hidden bin packing structure beats ILP 100x on energy scheduling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The speedup depends on the relaxed lower bound frequently producing space-blocks that the original jobs can actually be packed into, so that the primal heuristic closes search subtrees early; when that packing fails, as it does for processing times {8,10}, the algorithm loses its advantage and can hit the time limit without proving optimality.","fun_headline_variants_meta":{"raw":{"variants":["Branch-and-bound plus bin packing cuts TOU scheduling by 100x","Bin packing unlocks 100x speedup for time-of-use scheduling","Exact TOU scheduling: 200 jobs solved 100x faster via bin packing","Hidden bin packing structure beats ILP 100x on energy scheduling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000224,"raw_usage":{"total_tokens":1437,"prompt_tokens":901,"completion_tokens":536,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":517,"completion_tokens_details":{"reasoning_tokens":456}},"tokens_in":517,"tokens_out":536,"duration_ms":5895,"temperature":1.0,"reasoning_tokens":456,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:28:23.599772+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run B&B-SPACES on a family of instances with real TOU prices and processing times drawn only from {8,9,10} at n=200, the parameter region the paper identifies as hardest. If 10-minute time-limit hits persist or grow, and the proven lower bound never closes the gap, then the claimed two-orders-of-magnitude speedup does not hold in the regime where the packing assumption breaks down; the paper’s own Table 3 already shows such failures for {8,10}, so the decisive test is enlarging that class and comparing node counts against an exact bin-packing oracle.","supporting_citations":[{"cited_title":", author Ordieres-Meré, J","cited_arxiv_id":null,"evidence_quote":"Introduces the 1,TOU|states|TEC problem, the transition graph model, and the original ILP formulation that serves as the first baseline."},{"cited_title":", author M \\'o dos, I","cited_arxiv_id":null,"evidence_quote":"Supplies the SPACES preprocessing that precomputes optimal switching costs, and the previous state-of-the-art ILP model that B&B-SPACES compares against and outperforms."},{"cited_title":"The Easiest Hard Problem: Number Partitioning","cited_arxiv_id":"cond-mat/0310317","evidence_quote":"Supplies the number-partitioning phase-transition analysis used to interpret why certain processing-time groups make instances hard or easy."},{"cited_title":", author Mertens, S","cited_arxiv_id":null,"evidence_quote":"Connects the observed hardness to phase transitions in multiprocessor scheduling, supporting the paper’s explanation of instance difficulty."}],"review_version":1}