{"id":"aeff9f7c-ccb1-4307-aa83-1ea7a4863c79","arxiv_id":"2507.11311","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper proves asymptotically optimal competitive ratios for four online scheduling settings with known setup times and unknown execution times, from Θ(m) and Θ(n^{1/3}) down to Θ(log n / log log n).","lead":"This paper introduces an online scheduling model where jobs have known setup costs that depend on the batch, but execution times that are revealed only when a job finishes. For four variants, single-machine versus multi-machine batches and preemptive versus non-preemptive, the authors give asymptotically optimal worst-case performance ratios.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed w.l.o.g. reduction to subadditive setup times (Section 2) is not justified for multi-machine batch allocation; the stated algorithms fail on a simple non-subadditive instance unless modified to split batches, so the upper bounds currently hold only for subadditive setup functions.","rationale":"The reader's weakest_assumption identifies exactly the point that is most load-bearing: the unproved 'without loss of generality' passage from arbitrary monotone setup times to their subadditive closure. The paper's central claim in the abstract is for a 'known monotone function', not explicitly subadditive, and the upper-bound theorems are stated under the subadditive assumption after the w.l.o.g. claim. If that claim fails, the main results no longer apply to the stated model. My concrete counterexample shows that the failure is not merely cosmetic: applying Algorithm 3 after substituting c̄ for c on a four-job, four-machine instance with a large non-subadditive pair cost yields a makespan of 1000 instead of the optimal 1. The lower bounds in the paper use constant or type-specific setup times, which are subadditive, so they remain valid. Thus the paper's asymptotic tightness for all monotone setup functions is not established. The reader's verdict of CONDITIONAL is appropriate: the results hold conditional on either restricting the model to subadditive setups or providing an explicit transformation that splits batches and preserves the competitive-ratio analysis. I do not see a more serious issue in the core proofs beyond this assumption; the combinatorial arguments in Theorems 4-11 appear internally consistent once subadditivity is granted.","tokens_in":18094,"tokens_out":14410,"duration_ms":174115,"concrete_test":"Implement the claimed reduction on the instance m = 4, n = 4, c({j}) = 1 for singletons, c(X) = 1000 for |X| ≥ 2, and all p_j = 0. Run Algorithm 3 after substituting c̄ for c, as the w.l.o.g. passage prescribes: compute a 2-partition minimizing max c̄(X_i) and assign each batch to ⌊m/k⌋ = 2 machines. If the resulting makespan is 1000 while the optimal offline makespan is 1, the w.l.o.g. is invalid as stated. Then test a modified version that, whenever the algorithm forms a batch X, splits X into the sub-batches attaining c̄(X) and schedules those sub-batches separately: verify whether the O(√m) bound is recovered on this instance and on the type-specific examples in Section 2.1. If the modified algorithm does not recover the bound with the same analysis, the results should be restated as applying to monotone subadditive setup functions only.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2 asserts that for any monotone setup function c, replacing it by the subadditive closure c̄(X) = min over partitions of X of Σ c(X_i) loses no generality. This reduction is load-bearing for all upper bounds, especially the mUETS algorithms. The algorithms are described and analyzed using c directly: Algorithm 3 computes a k-partition minimizing max c(X_i) and then assigns each batch X_i as a whole to ⌊m/k⌋ machines. If c is not subadditive, c̄(X) can be much smaller than c(X) for every batch of size at least 2, so replacing c by c̄ changes the partition chosen, while the actual incurred setup remains c(X), not c̄(X). Realizing c̄(X) requires splitting X into sub-batches, which changes how machines are allocated and is not accounted for in the proofs. Concretely, take m = 4, n = 4, c({j}) = 1 for each job j, and c(X) = 1000 for every |X| ≥ 2, with all p_j = 0. Under c̄ the algorithm would choose two batches of size 2 (max c̄ = 2) and assign each to 2 machines, but the actual setup per machine is 1000, giving makespan 1000. The optimal offline schedule puts each job on its own machine, makespan 1. This contradicts the claimed O(√m) = O(2) competitive ratio if the w.l.o.g. reduction is used. Lower bounds are unaffected because they use already-subadditive instances, but the upper-bound claims for arbitrary monotone setup functions are unsupported without an explicit splitting construction and a matching analysis.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the UETS problem: scheduling n jobs with known setup times modeled as a monotone set function c and unknown execution times p_j on m identical machines, with the goal of minimizing makespan. It studies four settings—whether a batch can be assigned to one machine or distributed over several machines, and whether preemption is allowed—and claims asymptotically optimal competitive ratios for each: Θ(m) and Θ(n^{1/3}) for non-preemptive sUETS, Θ(log n / log log n) for preemptive sUETS, Θ(√m) and Θ(n^{1/4}) for non-preemptive mUETS, and Θ(log m / log log m) and Θ(log n / log log n) for preemptive mUETS. The upper bounds are obtained by batch-partitioning and multi-phase preemptive algorithms; the lower bounds use adversarial placement of 'heavy' jobs. The paper also gives a release-time reduction via the IGNORE strategy. A central methodological step is the assertion that, without loss of generality, any monotone setup function can be replaced by its subadditive closure; the correctness of the mUETS upper bounds for arbitrary monotone functions rests on this assertion.","tokens_in":18420,"tokens_out":30397,"duration_ms":368157,"significance":"If the results are read as applying to monotone subadditive setup times, the paper gives a tight and largely self-contained classification of four natural non-clairvoyant scheduling models. The lower bounds are standard adversarial arguments, the algorithms are simple, and there are no fitted parameters or circular steps. The release-time reduction and the explicit remarks on approximation algorithms are useful. The main weakness is the unsupported 'without loss of generality' reduction from monotone to subadditive setup functions: it is load-bearing for the mUETS upper bounds and even for the characterization of the offline optimum in Lemma 1, and it is not justified by the arguments given in Section 2.","major_comments":[{"comment":"The asserted without-loss-of-generality reduction from monotone to monotone subadditive setup times is not valid for the mUETS setting, and it is load-bearing for the upper bounds. The subadditive closure c̄(X) is attained by partitioning X into sub-batches, but the mUETS algorithms in Section 4 do not split batches; when Algorithm 3 assigns a batch X_i as a whole to ⌊m/k⌋ machines, each machine incurs c(X_i), not c̄(X_i). Concretely, take m = n = 4, p_j = 0, c({j}) = 1 for every job j, and c(X) = 1000 for every |X| ≥ 2. The c̄-optimal 2-partition is two pairs, with c̄ = 2 for each pair; Algorithm 3 assigns each pair to two machines, incurring an actual setup of 1000 per machine and makespan 1000, while the optimal offline schedule uses four singleton batches and has makespan 1. This contradicts the claimed O(√m) bound. The same issue affects Algorithm 4 and hence the preemptive mUETS upper bound. The lower bounds are unaffected because they use already-subadditive instances, but the upper bounds for arbitrary monotone setup functions are unsupported without an explicit splitting construction and a matching analysis.","section":"Section 2, paragraph beginning 'We assume that the setup time function c...'; Theorems 8, 9; Corollary 2"},{"comment":"The characterization of the optimal schedule as a partition of jobs into m batches, one per machine, already presupposes subadditivity. For a non-subadditive monotone c the lemma is false. For example, with m = 2, n = 4, c({j}) = 1 for singletons, c(X) = 100 for every |X| ≥ 2, and all p_j = 0, the true optimal makespan is 2 (each machine processes two singleton batches), whereas the lemma's lower bound min over 2-partitions of max_i c(X_i) is 100. Thus replacing c by c̄ cannot be treated as a cosmetic change: it alters the offline benchmark itself. The paper either needs a formal reduction that preserves the true optimum and the online algorithm's costs, or the model must be explicitly restricted to monotone subadditive setup functions.","section":"Section 2, Lemma 1 and preceding paragraph"}],"minor_comments":[{"comment":"The abstract and the problem statement say the setup time is a known monotone function, while the proofs assume monotone subadditivity. If the WLOG claim is removed, the model definition should be corrected to 'monotone subadditive' throughout, or the broader claim must be proved.","section":"Abstract and Section 2"},{"comment":"There is a typo in 'such as cloud computing ... and and production systems'; the duplicated 'and' should be removed.","section":"Section 1, Related work"},{"comment":"The definition of q is inconsistent between the text, which states q^q > m ≥ (q−1)^{q−1}, and the pseudocode, which states q^q ≥ m > (q−1)^{q−1}; these should be aligned.","section":"Section 4.1, Algorithm 4"},{"comment":"The sentence 'the total execution time of jobs in phase k is at most p(R(k−1) \\ R(k)) + pmax · ⌊m/q⌋' in the proof of Theorem 5 could be more precise: at most one partially executed job per uncompleted machine, so the additive term is indeed at most ⌊m/q⌋ · pmax, but this reasoning should be stated explicitly.","section":"Section 3.1, Theorem 4 proof"}],"recommendation":"major_revision","confidential_remarks":"The lower-bound arguments and the proofs for the subadditive case appear sound, so the paper is likely salvageable by explicitly restricting the model to monotone subadditive setup functions, which still includes all examples discussed in Section 2.1. The broader claim for arbitrary monotone setup functions, especially the mUETS upper bounds, would require genuinely new algorithmic ideas and is not supported by the current manuscript. If the editors consider the monotone-only formulation essential to the contribution, the paper in its present form would not be acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear Colleague,\n\nThe paper is worth reading for anyone in online scheduling. It introduces the UETS model, gives tight competitive ratios for four settings, and the lower bounds are clean. For subadditive setup times, the results appear correct: Θ(m) and Θ(n^{1/3}) for non-preemptive sUETS, Θ(log n/log log n) for preemptive sUETS, Θ(√m) and Θ(n^{1/4}) for non-preemptive mUETS, and Θ(log m/log log m) for preemptive mUETS.\n\nBut there is a load-bearing flaw: the 'without loss of generality' reduction to subadditive setup times in Section 2 is not justified. The paper defines c̄ as the subadditive closure and claims it doesn't change the problem. It does. For the multi-machine settings, splitting a batch into sub-batches to realize c̄ changes how many machines each sub-batch uses, and the actual setup cost remains c(X), not c̄(X). Concrete instance: m=4, n=4, c({j})=1, c(X)=1000 for |X|≥2, p_j=0. The optimal makespan is 1. Algorithm 3, using the closure, would form two batches of size 2 (c̄=2) and assign each to two machines, incurring 1000 per machine, makespan 1000. That violates the claimed O(√m) bound. The same issue affects the sUETS upper bounds, since Theorem 2 relies on subadditivity to bound c(J) against the optimal partition. So as written, the upper bounds hold only for subadditive setup functions, not for all monotone functions as the abstract implies.\n\nThe lower bounds are unaffected because they use subadditive instances. The computational hardness of the partition step is acknowledged with approximation variants, which is fine for a theory paper. The preemptive mUETS algorithm is explicitly adapted from Goko et al., so the novelty there is limited, but the new applications and the other three settings are original.\n\nBottom line: this is a solid paper for the subadditive case, and the model is natural. It deserves a serious referee, but the authors need to either prove the reduction properly (with an explicit splitting construction and a matching cost analysis) or state the results for subadditive setup functions and adjust the abstract. I would not cite the paper in its current form.\n\nRecommendation: send it to peer review, but with a strong request to fix the w.l.o.g. claim before acceptance.","headline":"Good tight bounds for a natural online scheduling model, but the claimed w.l.o.g. reduction to subadditive setup times is unjustified and the upper bounds as written only hold for subadditive functions.","tokens_in":18963,"tokens_out":5778,"would_cite":false,"duration_ms":64058,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68M20","90B35","68W27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Scheduling with unknown runtimes gets tight bounds in four settings.","keywords":["unknown execution times","online scheduling","competitive analysis","setup times","batch scheduling","non-clairvoyant scheduling","makespan","preemption"],"falsifier":"To settle the claim for multi-machine batches, construct a monotone setup function $c$ for which the subadditive closure $\\bar c$ is strictly cheaper, and compare the mUETS algorithm run with $\\bar c$ against the true $c$ schedule; if a single instance violates the claimed $O(\\sqrt m)$ or $O(n^{1/4})$ ratio (or $O(\\log m/\\log\\log m)$ in the preemptive case) because sub-batch splitting reduces per-sub-batch machine counts, the assumed equivalence fails. If no such instance exists, the reduction is vindicated.","tokens_in":17894,"feed_emoji":"⚙️","tokens_out":8388,"duration_ms":91801,"temperature":0.7,"pith_summary":"When a machine must spend a known setup time to prepare a batch before running jobs whose execution times are only learned at completion, no algorithm can know in advance which batches are cheap. This paper asks how much that ignorance costs, measured by the competitive ratio against an offline schedule that knows all execution times. It establishes asymptotically tight ratios for all four combinations: one machine or many machines per batch, with or without preemption. For non-preemptive single-machine batches the ratios are $\\Theta(m)$ and $\\Theta(n^{1/3})$; for preemptive single-machine batches $\\Theta(m)$ and $\\Theta(\\log n / \\log\\log n)$; for non-preemptive multi-machine batches $\\Theta(\\sqrt{m})$ and $\\Theta(n^{1/4})$; for preemptive multi-machine batches $\\Theta(\\log m / \\log\\log m)$ and $\\Theta(\\log n / \\log\\log n)$. The lower bounds hold even for constant setup times or unweighted type-specific setup times, so the difficulty is the unknown execution times themselves, not exotic setup structure.","feed_headline":"Scheduling with unknown runtimes gets tight bounds in four settings","feed_subtitle":"Matching upper and lower bounds for single-machine or multi-machine batches, with and without preemption.","key_machinery":"The central objects are a monotone subadditive set function $c(X)$ giving the setup time of a batch $X$, and the four problem variants sUETS (one batch on one machine) and mUETS (one batch spread over several machines), each in non-preemptive and preemptive form. The upper bounds are carried by three constructions: a one-batch-everything algorithm that is $m$-competitive; a batched list-scheduling algorithm that minimizes maximum setup time over a partition with bounded batch size, giving $O(\\sqrt{n/m})$; and a phase algorithm that uses $q\\approx \\log n/\\log\\log n$ or $q\\approx \\log m/\\log\\log m$ rounds to complete a $(1-1/q)$-fraction of the remaining jobs or batches per round, giving the logarithmic ratios. The lower bounds are carried by adversary arguments in which the online algorithm is observed and then heavy jobs are placed where they force either $\\Omega(m)$, $\\Omega(n^{1/3})$, $\\Omega(\\sqrt m)$, $\\Omega(n^{1/4})$, or $\\Omega(\\log n/\\log\\log n)$ setup or execution cost. A preliminary reduction lets all analyses assume release time zero.","core_discovery":"The paper's central claim is that the online UETS problem has the four tight competitive-ratio regimes listed above, and that each is achieved by an explicit online algorithm. The algorithms work by arranging jobs into a small number of setup-efficient batches and then either processing them list-scheduling style (non-preemptive) or running a sequence of phases that repeatedly completes a constant fraction of the remaining work while keeping enough machines busy (preemptive). The matching lower bounds come from adversary constructions in which the algorithm is forced to concentrate heavy jobs on too few machines or to pay for too many setups; the adversary chooses which jobs are heavy only after seeing the algorithm's batching choices. A constant-factor reduction from arbitrary release times to release time zero means the ratios transfer to release-time settings as well.","pith_inferences":["Editorial extension: the paper's lower bounds use only constant or unweighted type-specific setup times, so the same ignorance-of-execution-time cost should appear in any monotone setup family that contains those classes; applying the results to richer setup families such as TSP-based or library-based setup times should not require new lower-bound ideas.","Editorial extension: the phase algorithms suggest a practical heuristic for cloud or production settings: repeatedly shrink the active job set by a constant fraction, re-batching and restarting setup after preemption, while keeping the number of active machines proportional to the remaining batch count; the analysis gives a worst-case guarantee but not a throughput or average-case one.","Editorial extension: if splitting a batch across machines is constrained so that a machine cannot simultaneously contribute to two sub-batches of the same logical batch, the paper's subadditive-closure reduction would need a separate argument; testing the mUETS algorithms on a concrete non-subadditive setup function is a cheap way to see whether the claimed generality holds."],"forward_implications":["For non-preemptive sUETS, every online algorithm must pay at least $\\Theta(m)$ and $\\Theta(n^{1/3})$ in the worst case, and the paper's two algorithms together meet both bounds simultaneously.","Preemption strictly improves the dependence on $n$ for single-machine batches: the ratio drops from $\\Theta(n^{1/3})$ to $\\Theta(\\log n/\\log\\log n)$.","Allowing one batch to be spread over many machines strictly improves the dependence on $m$: $\\Theta(m)$ becomes $\\Theta(\\sqrt m)$ non-preemptively and $\\Theta(\\log m/\\log\\log m)$ preemptively.","The release-time reduction means a $\\rho$-competitive zero-release-time algorithm becomes $(2\\rho+1)$-competitive with arbitrary release times, so all four ratios carry over up to a constant factor.","Using an $\\alpha$-approximation to compute the setup-minimizing partition degrades the ratios only by an $\\alpha$-factor (or a square-root factor in the machine regime), so the bounds survive computational hardness of the partition step."],"supporting_citations":[{"why":"Supplies the release-time reduction used in Theorem 1 and the classical list-scheduling optimality bound this paper extends.","marker":"[32]"},{"why":"Provides the metric-state-space scheduling model whose preemptive multi-machine case Algorithm 4 is based on.","marker":"[15]"},{"why":"Defines non-clairvoyant scheduling, the model of unknown execution times that the UETS problem adopts.","marker":"[26]"},{"why":"Gives the zero-setup list-scheduling ratio that serves as the baseline from which setup-time results are measured.","marker":"[16]"},{"why":"Provides the dual-approximation load-balancing PTAS used to handle the setup-partition subproblem in the remarks.","marker":"[19]"},{"why":"Gives submodular setup-time load-balancing approximation and lower bounds, framing the hardness of the partition step.","marker":"[33]"}],"fun_headline_variants":["Setup-aware scheduling with unknown runtimes: tight bounds","Four tight competitive ratios for online scheduling with setups","Unknown execution times, setup costs: asymptotically optimal ratios","Scheduling with setup times and unknown job lengths: optimal ratios","Tight bounds for four scheduling models with setup costs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that replacing the setup-time function by its cheapest split-batch version does not change the scheduling problem, even when a batch spans several machines and splitting reduces the machines available to each piece.","fun_headline_variants_meta":{"raw":{"variants":["Setup-aware scheduling with unknown runtimes: tight bounds","Four tight competitive ratios for online scheduling with setups","Unknown execution times, setup costs: asymptotically optimal ratios","Scheduling with setup times and unknown job lengths: optimal ratios","Tight bounds for four scheduling models with setup costs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000899,"raw_usage":{"total_tokens":3815,"prompt_tokens":831,"completion_tokens":2984,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":447,"completion_tokens_details":{"reasoning_tokens":2906}},"tokens_in":447,"tokens_out":2984,"duration_ms":25756,"temperature":1.0,"reasoning_tokens":2906,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:14:05.521933+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"To settle the claim for multi-machine batches, construct a monotone setup function $c$ for which the subadditive closure $\\bar c$ is strictly cheaper, and compare the mUETS algorithm run with $\\bar c$ against the true $c$ schedule; if a single instance violates the claimed $O(\\sqrt m)$ or $O(n^{1/4})$ ratio (or $O(\\log m/\\log\\log m)$ in the preemptive case) because sub-batch splitting reduces per-sub-batch machine counts, the assumed equivalence fails. If no such instance exists, the reduction is vindicated.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the metric-state-space scheduling model whose preemptive multi-machine case Algorithm 4 is based on."},{"cited_title":"Svitkina and L","cited_arxiv_id":null,"evidence_quote":"Gives submodular setup-time load-balancing approximation and lower bounds, framing the hardness of the partition step."}],"review_version":1}