Pith. sign in

REVIEW 2 major objections 4 minor 34 references

Scheduling on Identical Machines with Setup Time and Unknown Execution Time

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read Scheduling with unknown runtimes gets tight bounds in four settings.

desk verdict 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. read the letter →

arxiv 2507.11311 v1 pith:EV4HK4MJ submitted 2025-07-15 cs.DS

Yasushi Kawase , Kazuhisa Makino , Vinh Long Phan , Hanna Sumita This is my paper · ORCID
classification cs.DS MSC 68M2090B3568W27
keywords unknownexecutiontimesonlineschedulingcompetitiveanalysissetupbatchnon-clairvoyantmakespanpreemption
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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.

Referee Report

2 major / 4 minor

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.

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 (2)
  1. [Section 2, paragraph beginning 'We assume that the setup time function c...'; Theorems 8, 9; Corollary 2] 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.
  2. [Section 2, Lemma 1 and preceding paragraph] 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.
minor comments (4)
  1. [Abstract and Section 2] 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.
  2. [Section 1, Related work] There is a typo in 'such as cloud computing ... and and production systems'; the duplicated 'and' should be removed.
  3. [Section 4.1, Algorithm 4] 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.
  4. [Section 3.1, Theorem 4 proof] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the analysis is self-contained and the subadditivity reduction, even if questionable, is not a circular step.

full rationale

The paper does not fit parameters, rename a known result, or import a load-bearing conclusion from a self-citation. The competitive ratios are derived from the externally defined offline optimum through Lemma 1, direct makespan bounds on the proposed algorithms, and adversarial lower-bound constructions. The use of the subadditive closure c-bar in Section 2 is presented as a lossless modeling reduction; whether that reduction actually preserves the multi-machine setting is a correctness concern, not a circularity concern, because the upper-bound theorems do not define their conclusion in terms of c-bar. Algorithm 4 is said to be based on a similar idea to [15, Algorithm 1], but the analysis in Theorem 9 is carried out self-containedly and [15] is used as a starting point rather than as the justification of the competitive ratio. No step reduces by definition to its own inputs, and no prediction is statistically forced by a fitted quantity. Therefore the appropriate finding is no significant circularity.

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

The central claims rest on domain assumptions about the setup time function and the non-clairvoyant execution model, plus standard combinatorial tools. No free parameters are fitted, and no new entities are postulated.

assumptions (5)
  • domain assumption Monotone subadditivity of the setup time function c.
    Assumed in Section 2. The paper claims it is without loss of generality, but the closure argument is not fully justified for multi-machine batches.
  • domain assumption The offline optimal schedule can be taken non-preemptive with one batch per machine.
    Stated in Section 2 Preliminaries and used to characterize OPT in Lemma 1. Justified by subadditivity of c.
  • domain assumption Execution times are non-clairvoyant: revealed only at completion, with an adaptive adversary setting 0/1 weights in lower bounds.
    This is the standard non-clairvoyant model (Motwani et al. [26]); it underpins Theorems 6, 7, 10, and 11.
  • domain assumption Preemption overhead is at most c(X)+max p_j for a preempted batch X.
    Stated in Section 2 and used in the proofs of Theorems 5 and 9.
  • standard math Standard combinatorial partition facts: existence of bounded-size k-partitions and the q-splitting invariant for Algorithm 2.
    Used implicitly in Algorithm 1, Algorithm 2, and Algorithm 4; the paper gives only a brief justification.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Scheduling on Identical Machines with Setup Time and Unknown Execution Time." pith.science (2026). https://pith.science/paper/EV4HK4MJ

@misc{pith2026250711311,
  author       = {Pith},
  title        = {Pith review of: Scheduling on Identical Machines with Setup Time and Unknown Execution Time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EV4HK4MJ}},
  note         = {Machine review of arXiv:2507.11311}
}
read the original abstract

In this study, we investigate a scheduling problem on identical machines in which jobs require initial setup before execution. We assume that an algorithm can dynamically form a batch (i.e., a collection of jobs to be processed together) from the remaining jobs. The setup time is modeled as a known monotone function of the set of jobs within a batch, while the execution time of each job remains unknown until completion. This uncertainty poses significant challenges for minimizing the makespan. We address these challenges by considering two scenarios: each job batch must be assigned to a single machine, or a batch may be distributed across multiple machines. For both scenarios, we analyze settings with and without preemption. Across these four settings, we design online algorithms that achieve asymptotically optimal competitive ratios with respect to both the number of jobs and the number of machines.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 24 canonical work pages

  1. [1]

    Allahverdi, C

    A. Allahverdi, C. T. Ng, T. E. Cheng, and M. Y. Kovalyov. A survey of scheduling problems with setup times or costs. European journal of operational research , 187(3):985–1032, 2008. doi: 10.1016/j.ejor.2006.06.060

    doi:10.1016/j.ejor.2006.06.060 2008

  2. [2]

    Ascheuer, S

    N. Ascheuer, S. O. Krumke, and J. Rambau. Online Dial-a-Ride Problems: Minimizing the Com- pletion Time. In Proceedings of the Symposium on Theoretical Aspects of Computer Science, volume 1770, pages 639–650, 2000. doi: 10.1007/3-540-46541-3 53. 14

    work page doi:10.1007/3-540-46541-3

  3. [3]

    Bampis, A

    E. Bampis, A. V. Kononov, G. Lucarelli, and F. Pascual. Non-clairvoyant makespan minimization scheduling with predictions. In S. Iwata and N. Kakimura, editors, Proceedings of the International Symposium on Algorithms and Computation, volume 283 of LIPIcs, pages 9:1–9:15. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2023. doi: 10.4230/LIPIcs.ISAAC...

    work page doi:10.4230/lipics.isaac.2023.9 2023

  4. [4]

    A. Birx. Competitive analysis of the online dial-a-ride problem . PhD thesis, Technische Universit¨ at Darmstadt, 2020

    work page 2020

  5. [5]

    Birx and Y

    A. Birx and Y. Disser. Tight analysis of the smartstart algorithm for online dial-a-ride on the line. SIAM Journal on Discrete Mathematics , 34(2):1409–1443, 2020. doi: 10.1137/19M1268513

    work page doi:10.1137/19m1268513 2020

  6. [6]

    A. Birx, Y. Disser, and K. Schewior. Improved bounds for open online dial-a-ride on the line. In Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), volume 145, 2019. doi: 10.4230/LIPIcs.APPROX-RANDOM. 2019.21

    doi:10.4230/lipics.approx-random 2019

  7. [7]

    Bonifaci, M

    V. Bonifaci, M. Lipmann, and L. Stougie. Online multi-server dial-a-ride problems . SPOR-Report : reports in statistics, probability and operations research. Technische Universiteit Eindhoven, 2006

    work page 2006

  8. [8]

    Christofides

    N. Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Opera- tions Research Forum, 3(1):20, 2022. doi: 10.1007/s43069-021-00101-z

    doi:10.1007/s43069-021-00101-z 2022

Show all 34 references
  1. [9]

    Divakaran and M

    S. Divakaran and M. Saks. An online scheduling problem with job set-ups. DIM ACS Technical Report: 2000 , 34, 2000

    2000

  2. [10]

    Dogeas, T

    K. Dogeas, T. Erlebach, and Y.-C. Liang. Scheduling with Obligatory Tests. In Proceedings of the Annual European Symposium on Algorithms , pages 48:1–48:14, 2024. doi: 10.4230/LIPIcs.ESA. 2024.48

    2024 doi

  3. [11]

    Feuerstein and L

    E. Feuerstein and L. Stougie. On-line single-server dial-a-ride problems. Theoretical Computer Science, 268(1):91–105, 2001. doi: 10.1016/S0304-3975(00)00261-9

    2001 doi

  4. [12]

    G. N. Frederickson, M. S. Hecht, and C. E. Kim. Approximation Algorithms for Some Routing Problems. SIAM Journal on Computing , 7(2):178–193, 1978. doi: 10.1137/0207017

    1978 doi

  5. [13]

    Gambosi and G

    G. Gambosi and G. Nicosia. On-line scheduling with setup costs. Information Processing Letters, 73(1–2):61–68, 2000. doi: 10.1016/S0020-0190(99)00152-0

    2000 doi

  6. [14]

    M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP- Completeness, volume 174. W. H. Freeman, 1979. ISBN 0-7167-1044-7

    1979

  7. [15]

    H. Goko, A. Kawamura, Y. Kawase, K. Makino, and H. Sumita. Online scheduling on identical machines with a metric state space. In Proceedings of the Symposium on Theoretical Aspects of Computer Science, pages 32:1–32:21, 2022. doi: 10.4230/LIPIcs.STACS.2022.32

    2022 doi

  8. [16]

    R. L. Graham. Bounds for Certain Multiprocessing Anomalies. Bell System Technical Journal , 45 (9):1563–1581, 1966. doi: https://doi.org/10.1002/j.1538-7305.1966.tb01709.x

    1966

  9. [17]

    Gusfield

    D. Gusfield. Bounds for naive multiple machine scheduling with release times and deadlines. Journal of Algorithms, 5(1):1–6, 1984. doi: 10.1016/0196-6774(84)90035-X

    1984 doi

  10. [18]

    L. A. Hall and D. B. Shmoys. Approximation schemes for constrained scheduling problems. In Proceedings of Annual Symposium on Foundations of Computer Science , pages 134–139, 1989. doi: 10.1109/SFCS.1989.63468

    1989

  11. [19]

    D. S. Hochbaum and D. B. Shmoys. Using dual approximation algorithms for scheduling problems theoretical and practical results. Journal of the ACM , 34(1):144–162, 1987. doi: 10.1145/7531.7535

    1987

  12. [20]

    H. Hu, K. K. Ng, and Y. Qin. Robust Parallel Machine Scheduling Problem with Uncertainties and Sequence-Dependent Setup Time. Scientific Programming, 2016. doi: 10.1155/2016/5127253. 15

    2016 doi

  13. [21]

    S. Im, R. Kumar, M. M. Qaem, and M. Purohit. Non-clairvoyant scheduling with predictions. ACM Transactions on Parallel Computing , 10(4):1–26, 2023. doi: 10.1145/3593969

    2023 doi

  14. [22]

    S. O. Krumke. Online optimization: Competitive analysis and beyond . PhD thesis, Technische Universit¨ at Berlin, 2001

    2001

  15. [23]

    Lipmann, X

    M. Lipmann, X. Lu, W. E. de Paepe, R. A. Sitters, and L. Stougie. On-Line Dial-a-Ride Problems Under a Restricted Information Model. Algorithmica, 40(4):319–329, 2004. doi: 10.1007/s00453-004-1116-z

    2004 doi

  16. [24]

    M¨ acker, M

    A. M¨ acker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers. Non-clairvoyant scheduling to minimize max flow time on a machine with setup times. In Proceedings of the International Workshop on Approximation and Online Algorithms , pages 207–222. Springer, 2017. doi: 10....

    2017

  17. [25]

    D. M. Miller, H.-C. Chen, J. Matson, and Q. Liu. A hybrid genetic algorithm for the single machine scheduling problem. Journal of Heuristics , 5(4):437–454, 1999. doi: 10.1023/A:1009684406579

    1999 doi

  18. [26]

    Motwani, S

    R. Motwani, S. Phillips, and E. Torng. Nonclairvoyant scheduling. Theoretical computer science, 130(1):17–47, 1994. doi: 10.1016/0304-3975(94)90151-1

    1994 doi

  19. [27]

    Nagano and A

    K. Nagano and A. Kishimoto. Subadditive load balancing, 2019. URL https://arxiv.org/abs/ 1908.09135

    2019 arXiv

  20. [28]

    M. L. Pinedo. Scheduling: Theory, Algorithms, and Systems . Springer Publishing Company, Incor- porated, 2008. doi: 10.1007/978-3-031-05921-6

    2008 doi

  21. [29]

    Pruhs, J

    K. Pruhs, J. Sgall, and E. Torng. Online scheduling. In J. Y. Leung, editor, Hand- book of Scheduling - Algorithms, Models, and Performance Analysis . Chapman and Hall/CRC,

  22. [30]

    V. K. Sahney. Single-server, two-machine sequencing with switching time. Operations Research, 20 (1):24–36, 1972. doi: 10.1287/opre.20.1.24

    1972 doi

  23. [31]

    J. Sgall. On-line scheduling, pages 196–231. Springer Berlin Heidelberg, 1998

    1998

  24. [32]

    D. B. Shmoys, J. Wein, and D. P. Williamson. Scheduling parallel machines on-line. SIAM Journal on Computing , 24(6):1313–1331, 1995. doi: 10.1137/S0097539793248317

    1995 doi

  25. [33]

    Svitkina and L

    Z. Svitkina and L. Fleischer. Submodular approximation: Sampling-based algorithms and lower bounds. SIAM Journal on Computing , 40(6):1715–1737, 2011. doi: 10.1137/100783352. 16

    2011 doi

  26. [2004]

    URL http://www.crcnetbase.com/doi/abs/10.1201/ 9780203489802.ch15

    doi: 10.1201/9780203489802.CH15. URL http://www.crcnetbase.com/doi/abs/10.1201/ 9780203489802.ch15

    doi

Pith tools

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