pith. sign in

arxiv: 2605.23675 · v1 · pith:LLEMT743new · submitted 2026-05-22 · 🧮 math.OC

Simulation Strategies for an Efficient Local Search to solve Stochastic Scheduling Problems

Philip de Bruin , Bram Elderhorst , Marjan van den Akker , Han Hoogeveen This is my paper

Pith reviewed 2026-05-25 03:56 UTC · model grok-4.3

classification 🧮 math.OC
keywords stochastic schedulinglocal searchsimulationt-testsstopping rulesparallel machine schedulingelectric vehicle scheduling
0
0 comments X

The pith

A t-test stopping rule for simulations lets local search solve stochastic scheduling problems with fewer runs while matching the quality of fixed large simulation counts.

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

Scheduling problems with uncertain task durations produce stochastic objective values that cannot be computed exactly, so local search relies on simulation to estimate expected performance. Performing many simulations at every iteration is accurate but slow, creating a performance penalty. The paper compares several techniques for limiting simulations and introduces a t-test method that stops once the estimate meets a statistical reliability threshold. On the Stochastic Parallel Machine Scheduling Problem and the Stochastic Electric Vehicle Scheduling Problem the t-test approach reduces runtime while retaining solution quality better than the alternatives tested. This matters because it makes optimization under uncertainty practical without requiring exhaustive computation at each step.

Core claim

The t-test based simulation stopping rule is the most effective among the techniques studied for reducing the number of simulations inside local search on both the Stochastic Parallel Machine Scheduling Problem and the Stochastic Electric Vehicle Scheduling Problem, delivering lower runtimes while keeping solution quality comparable to the quality obtained with a fixed large number of simulations per iteration.

What carries the argument

The t-test stopping rule, which halts additional simulations once statistical evidence indicates the current sample mean is sufficiently accurate.

If this is right

  • Local search can be applied to stochastic scheduling problems with substantially lower per-iteration simulation cost on the two tested problem classes.
  • The t-test method outperforms the other simulation-reduction techniques examined in both case studies.
  • Solution quality remains comparable to exhaustive-simulation baselines while runtime decreases.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same stopping rule could be inserted into other local-search or metaheuristic frameworks that rely on Monte Carlo estimates of stochastic objectives.
  • Combining the t-test rule with variance-reduction sampling methods might produce further efficiency gains on the same problems.
  • Repeating the experiments on instances with heavier-tailed or correlated duration distributions would test whether the observed advantage persists.

Load-bearing premise

The t-test stopping rule produces estimates accurate enough for the local search to converge to solutions whose true expected performance is comparable to those obtained with a fixed large number of simulations.

What would settle it

Evaluating the final schedules from both the t-test local search and a fixed-large-simulation local search with an independent, much larger number of simulations and finding that the t-test solutions have statistically higher true expected costs.

read the original abstract

In scheduling problems, deterministic task durations are often assumed. This usually does not capture reality and may lead to schedules that are not robust to (small) changes to these task lengths. The use of stochastic task durations therefore seems preferable. Including these in local search, which is the way to find good solutions for difficult scheduling problems, is not straightforward, though. The objective value becomes stochastic then too, and computing the expected value is often not possible. One way out of this it to approximate this value by using simulation. This is quite easy to implement in a local search algorithm, but it may require many simulations each iteration to get a reliable estimate. Hence such an approach comes with a performance penalty. In this paper, we study techniques to limit the number of simulations. Besides comparing known techniques, we propose our own method for this, which is based on $t$-tests. We evaluate these techniques on the Stochastic Parallel Machine Scheduling Problem and the Stochastic Electric Vehicle Scheduling Problem. In these case studies, we show the effectiveness of using such methods to reduce runtime while retaining solution quality. Our method using $t$-tests turns out to be most effective in both problems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper addresses the challenge of incorporating stochastic task durations into local search for scheduling problems by approximating expected objective values via simulation. It compares existing techniques for limiting simulation counts per iteration and proposes a new method based on t-tests for early stopping. The approach is evaluated on two case studies—the Stochastic Parallel Machine Scheduling Problem and the Stochastic Electric Vehicle Scheduling Problem—where the t-test method is reported to be most effective at reducing runtime while retaining solution quality.

Significance. If the t-test stopping rule produces final solutions whose true expected performance is comparable to those found under fixed large simulation budgets, the method could meaningfully improve the practicality of simulation-based local search for stochastic combinatorial optimization problems without sacrificing solution robustness.

major comments (2)
  1. [Case studies / experimental evaluation] The central empirical claim—that the t-test method retains solution quality while reducing runtime—requires that final reported solutions from variable-simulation trajectories have their true expected costs verified under an independent high-fidelity estimator never used inside the search. The manuscript provides no indication that such a re-evaluation step was performed on the two case studies; without it, apparent quality retention may reflect bias in the stopping rule rather than comparable true performance.
  2. [Evaluation on Stochastic Parallel Machine Scheduling Problem and Stochastic Electric Vehicle Scheduling Problem] The comparison of techniques relies on reported solution quality and runtime, but the load-bearing assumption that the t-test stopping rule produces estimates accurate enough for the local search to converge to equivalent basins is not tested via any cross-validation or statistical comparison of true expectations across methods.
minor comments (1)
  1. [Abstract] The abstract states that 'our method using t-tests turns out to be most effective in both problems' but does not define the precise metrics (e.g., average expected cost, best-found cost, statistical significance) used to declare superiority.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments, which highlight important aspects of the empirical validation. We address each major comment below and will revise the manuscript to incorporate additional verification steps.

read point-by-point responses

  1. Referee: [Case studies / experimental evaluation] The central empirical claim—that the t-test method retains solution quality while reducing runtime—requires that final reported solutions from variable-simulation trajectories have their true expected costs verified under an independent high-fidelity estimator never used inside the search. The manuscript provides no indication that such a re-evaluation step was performed on the two case studies; without it, apparent quality retention may reflect bias in the stopping rule rather than comparable true performance.

    Authors: We agree that an independent high-fidelity re-evaluation of final solutions strengthens the claim of retained solution quality. The current experiments assess quality via the simulation estimates used during search, which could introduce bias. We will add a post-processing step in the revised manuscript: all final solutions from every method will be re-evaluated using a fixed, large simulation budget (independent of the search) to compute true expected costs, with results reported alongside the original metrics. revision: yes

  2. Referee: [Evaluation on Stochastic Parallel Machine Scheduling Problem and Stochastic Electric Vehicle Scheduling Problem] The comparison of techniques relies on reported solution quality and runtime, but the load-bearing assumption that the t-test stopping rule produces estimates accurate enough for the local search to converge to equivalent basins is not tested via any cross-validation or statistical comparison of true expectations across methods.

    Authors: We acknowledge that the manuscript does not include explicit cross-validation or statistical tests comparing true expected values across methods. To address this, the revised version will include a statistical comparison (e.g., paired t-tests or Wilcoxon tests) of the independently re-evaluated expected costs across all techniques on both case studies, confirming whether the t-test method converges to statistically equivalent basins. revision: yes

Circularity Check

0 steps flagged

No circularity: purely empirical comparison with no derivations or self-referential fits

full rationale

The paper contains no equations, derivations, or claimed first-principles predictions. It describes an empirical study comparing simulation-reduction techniques (including a proposed t-test method) on two scheduling case studies, reporting runtime and solution quality. No load-bearing step reduces to a fit, self-citation chain, or definitional equivalence; the central claim rests on direct experimental outcomes rather than any internal construction that would force the reported superiority.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no information on free parameters, axioms, or invented entities.

pith-pipeline@v0.9.0 · 5745 in / 902 out tokens · 19255 ms · 2026-05-25T03:56:27.308920+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [1]

    (2002) Simulation-based optimization using simulated annealing with ranking and selection

    Ahmed M.A., Alkhamis T.M. (2002) Simulation-based optimization using simulated annealing with ranking and selection. Computers & Operations Research 29(4):387--402. doi:10.1016/S0305-0548(00)00073-3

    work page doi:10.1016/s0305-0548(00)00073-3 2002

  2. [2]

    (2013) Finding Robust Solutions for the Stochastic Job Shop Scheduling Problem by Including Simulation in Local Search

    van den Akker M., van Blokland K., Hoogeveen H. (2013) Finding Robust Solutions for the Stochastic Job Shop Scheduling Problem by Including Simulation in Local Search . In: Bonifaci V., Demetrescu C., Marchetti-Spaccamela A. (eds) Experimental Algorithms, 12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013. Proceedings, Lecture Notes in Co...

    work page doi:10.1007/978-3-642-38527-8_35 2013

  3. [3]

    (2004) Simulation-based optimization using simulated annealing with confidence interval

    Alkhamis T., Ahmed M. (2004) Simulation-based optimization using simulated annealing with confidence interval. In: Proceedings of the 2004 Winter Simulation Conference, 2004., vol 1. IEEE, p 519, doi:10.1109/WSC.2004.1371356

    work page doi:10.1109/wsc.2004.1371356 2004

  4. [4]

    (1999) Simulated annealing for discrete optimization with estimation

    Alkhamis T.M., Ahmed M.A., Tuan V.K. (1999) Simulated annealing for discrete optimization with estimation. European Journal of Operational Research 116(3):530--544. doi:10.1016/S0377-2217(98)00112-X

    work page doi:10.1016/s0377-2217(98)00112-x 1999

  5. [5]

    (1999) A Simulated Annealing Algorithm with Constant Temperature for Discrete Stochastic Optimization

    Alrefaei M.H., Andradóttir S. (1999) A Simulated Annealing Algorithm with Constant Temperature for Discrete Stochastic Optimization . Management Science 45(5):748--764. doi:10.1287/mnsc.45.5.748

    work page doi:10.1287/mnsc.45.5.748 1999

  6. [6]

    (2016) Simulation optimization: a review of algorithms and applications

    Amaran S., Sahinidis N.V., Sharda B., Bury S.J. (2016) Simulation optimization: a review of algorithms and applications. Annals of Operations Research 240(1):351--380. doi:10.1007/s10479-015-2019-x

    work page doi:10.1007/s10479-015-2019-x 2016

  7. [7]

    SIAM Review53(3), 464–501 (2011)

    Bertsimas D., Brown D.B., Caramanis C. (2011) Theory and Applications of Robust Optimization . SIAM Review 53(3):464--501. doi:10.1137/080734510

    work page doi:10.1137/080734510 2011

  8. [8]

    (2009) A survey on metaheuristics for stochastic combinatorial optimization

    Bianchi L., Dorigo M., Gambardella L.M., Gutjahr W.J. (2009) A survey on metaheuristics for stochastic combinatorial optimization. Natural Computing 8(2):239--287. doi:10.1007/s11047-008-9098-4

    work page doi:10.1007/s11047-008-9098-4 2009

  9. [9]

    (1997) Introduction to Stochastic Programming

    Birge J.R., Louveaux F. (1997) Introduction to Stochastic Programming . Springer New York, doi:10.1007/978-1-4614-0237-4

    work page doi:10.1007/978-1-4614-0237-4 1997

  10. [10]

    (2026) Scheduling electric vehicles by simulated annealing with recombination through ILP

    ten Bosch W., Hoogeveen J.A., van Kooten Niekerk M.E., de Bruin P. (2026) Scheduling electric vehicles by simulated annealing with recombination through ILP . Public Transport doi:10.1007/s12469-026-00424-2

    work page doi:10.1007/s12469-026-00424-2 2026

  11. [11]

    (2023) Scheduling Electric Buses with Stochastic Driving Times

    de Bruin P., van den Akker M., Hoogeveen H., van Kooten Niekerk M. (2023) Scheduling Electric Buses with Stochastic Driving Times . Schloss Dagstuhl – Leibniz-Zentrum für Informatik, doi:10.4230/OASICS.ATMOS.2023.14

    work page doi:10.4230/oasics.atmos.2023.14 2023

  12. [12]

    (2000) Simulation budget allocation for further enhancing the efficiency of ordinal optimization

    Chen C., Lin J., Y \" u cesan E., Chick S.E. (2000) Simulation budget allocation for further enhancing the efficiency of ordinal optimization. Discrete Event Dynamic Systems 10(3):251--270. doi:10.1023/A:1008349927281

    work page doi:10.1023/a:1008349927281 2000

  13. [13]

    (2024) Adaptive budget allocation in simheuristics applied to stochastic home healthcare routing and scheduling

    Clapper Y., Berkhout J., Bekker R. (2024) Adaptive budget allocation in simheuristics applied to stochastic home healthcare routing and scheduling. Computers & Industrial Engineering 198:110651. doi:10.1016/j.cie.2024.110651

    work page doi:10.1016/j.cie.2024.110651 2024

  14. [14]

    (2007) A combined procedure for discrete simulation-optimization problems based on the simulated annealing framework

    Ghiani G., Legato P., Musmanno R., Vocaturo F. (2007) A combined procedure for discrete simulation-optimization problems based on the simulated annealing framework. Computational Optimization and Applications 38(1):133--145. doi:10.1007/s10589-007-9010-7

    work page doi:10.1007/s10589-007-9010-7 2007

  15. [15]

    (1999) An explanation of ordinal optimization: Soft computing for hard problems

    Ho Y.C. (1999) An explanation of ordinal optimization: Soft computing for hard problems. Information Sciences 113(3):169--192. doi:10.1016/s0020-0255(98)10056-7

    work page doi:10.1016/s0020-0255(98)10056-7 1999

  16. [16]

    (2015) A review of simheuristics: Extending metaheuristics to deal with stochastic combinatorial optimization problems

    Juan A.A., Faulin J., Grasman S.E., Rabe M., Figueira G. (2015) A review of simheuristics: Extending metaheuristics to deal with stochastic combinatorial optimization problems. Operations Research Perspectives 2:62--72. doi:10.1016/j.orp.2015.03.001

    work page doi:10.1016/j.orp.2015.03.001 2015

  17. [17]

    (2022) Simheuristics: An Introductory Tutorial

    Juan A.A., Li Y., Ammouriova M., Panadero J., Faulin J. (2022) Simheuristics: An Introductory Tutorial . In: 2022 Winter Simulation Conference (WSC), pp 1325--1339, doi:10.1109/WSC57314.2022.10015318

    work page doi:10.1109/wsc57314.2022.10015318 2022

  18. [18]

    (2006) Chapter 17 Selecting the Best System

    Kim S.H., Nelson B.L. (2006) Chapter 17 Selecting the Best System . In: Henderson S.G., Nelson B.L. (eds) Simulation, Handbooks in Operations Research and Management Science, vol 13. North-Holland, p 501--534, doi:10.1016/s0927-0507(06)13017-0

    work page doi:10.1016/s0927-0507(06)13017-0 2006

  19. [19]

    (2003) Optimization by direct search: New perspectives on some classical and modern methods

    Kolda T.G., Lewis R.M., Torczon V. (2003) Optimization by direct search: New perspectives on some classical and modern methods. SIAM Review 45(3):385--482. doi:10.1137/S003614450242889

    work page doi:10.1137/s003614450242889 2003

  20. [20]

    (2015) Simulation Modeling and Analysis , 5th edn

    Law A.M. (2015) Simulation Modeling and Analysis , 5th edn. McGraw-Hill

    work page 2015

  21. [21]

    (2010) A review of optimal computing budget allocation algorithms for simulation optimization problem

    Lee L.H., Chen C.H., Chew E.P., Li J., Pujowidianto N.A., Zhang S. (2010) A review of optimal computing budget allocation algorithms for simulation optimization problem. International Journal of Operations Research 7(2):19--31

    work page 2010

  22. [22]

    (2025) Robustness Measures for Stochastic Parallel Machine Scheduling and Train Unit Shunting

    Loman C., Pascual L., van den Akker M., van den Broek R., Hoogeveen H. (2025) Robustness Measures for Stochastic Parallel Machine Scheduling and Train Unit Shunting . doi:10.48550/arXiv.2512.15471

    work page doi:10.48550/arxiv.2512.15471 2025

  23. [23]

    (2025) A new, efficient approach to speed up local search by estimating the solution quality: an application to stochastic, parallel machine scheduling

    Passage G., van den Akker M., Hoogeveen H. (2025) A new, efficient approach to speed up local search by estimating the solution quality: an application to stochastic, parallel machine scheduling. Journal of Heuristics 31(3). doi:10.1007/s10732-025-09562-5

    work page doi:10.1007/s10732-025-09562-5 2025

  24. [24]

    (2022) Electric bus planning & scheduling: A review of related problems and methodologies

    Perumal S.S.G., Lusby R.M., Larsen J. (2022) Electric bus planning & scheduling: A review of related problems and methodologies. European Journal of Operational Research 301(2):395--413. doi:10.1016/j.ejor.2021.10.058

    work page doi:10.1016/j.ejor.2021.10.058 2022

  25. [25]

    (1978) On two-stage selection procedures and related probability-inequalities

    Rinott Y. (1978) On two-stage selection procedures and related probability-inequalities. Communications in Statistics - Theory and Methods 7(8):799--811. doi:10.1080/03610927808827671

    work page doi:10.1080/03610927808827671 1978

  26. [26]

    (2019) Simulated annealing based simulation optimization method for solving integrated berth allocation and quay crane scheduling problems

    Tasoglu G., Yildiz G. (2019) Simulated annealing based simulation optimization method for solving integrated berth allocation and quay crane scheduling problems. Simulation Modelling Practice and Theory 97:101948. doi:10.1016/j.simpat.2019.101948

    work page doi:10.1016/j.simpat.2019.101948 2019

  27. [27]

    (2005) The Use of Buffers in Project Management: The Trade-Off between Stability and Makespan

    Van de Vonder S., Demeulemeester E., Herroelen W., Leus R. (2005) The Use of Buffers in Project Management: The Trade-Off between Stability and Makespan . International Journal of Production Economics 97(2):227--240. doi:10.1016/j.ijpe.2004.08.004

    work page doi:10.1016/j.ijpe.2004.08.004 2005

  28. [28]

    (1984) A Table for Rinott 's Selection Procedure

    Wilcox R.R. (1984) A Table for Rinott 's Selection Procedure . Journal of Quality Technology 16(2):97--100. doi:10.1080/00224065.1984.11978896

    work page doi:10.1080/00224065.1984.11978896 1984

  29. [29]

    (2014) Optimal Computing Budget Allocation for Ordinal Optimization in Solving Stochastic Job Shop Scheduling Problems

    Yang H.a., Lv Y., Xia C., Sun S., Wang H. (2014) Optimal Computing Budget Allocation for Ordinal Optimization in Solving Stochastic Job Shop Scheduling Problems . Mathematical Problems in Engineering 2014:1--10. doi:10.1155/2014/619254

    work page doi:10.1155/2014/619254 2014

  30. [30]

    (2019) Considering sample means in Rinott 's procedure with a Bayesian approach

    Yoon M., Bekker J. (2019) Considering sample means in Rinott 's procedure with a Bayesian approach. European Journal of Operational Research 273(1):249--258. doi:10.1016/j.ejor.2018.06.040

    work page doi:10.1016/j.ejor.2018.06.040 2019