arxiv: 2604.15161 · v1 · submitted 2026-04-16 · 🧮 math.OC

A Robust Optimization Approach for Scheduling with Uncertain Start-Time Dependent Costs

Sof\'ia Rodr\'iguez-Ballesteros , Javier Alcaraz , Laura Anton-Sanchez , Marc Goerigk , Dorothee Henke This is my paper

Pith reviewed 2026-05-10 10:39 UTC · model grok-4.3

classification 🧮 math.OC

keywords single-machine schedulingrobust optimizationbudgeted uncertaintystart-time dependent costsNP-hardnesstwo-stage optimizationdiscrete uncertaintycontinuous uncertainty

0 comments p. Extension

The pith

Scheduling jobs with uncertain time-dependent costs is modeled as a two-stage robust optimization problem that is NP-hard and not approximable.

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

The paper examines a single-machine scheduling task that minimizes total cost when each job's cost depends on its start time and these costs vary within a budgeted uncertainty set. It proposes a two-stage robust approach in which the sequence of jobs is chosen first without knowing the exact costs, then start times are adjusted once a cost scenario is observed. This structure reflects situations such as daily changes in energy or labor prices. The authors prove that the overall problem is NP-hard and not approximable, and that simply checking the cost of any fixed sequence is already NP-hard when the uncertainty set is discrete. They supply solution models for both continuous and discrete uncertainty and run experiments showing that accounting for uncertainty in the first stage produces better schedules than ignoring it.

Core claim

We study a single-machine scheduling problem that minimizes total cost subject to start-time dependent costs lying in a budgeted uncertainty set. We propose a two-stage robust optimization approach in which the order of activities is decided in the first stage and starting times are set in the second stage after a cost scenario is revealed. We demonstrate that the proposed problem is NP-hard and not approximable, implying the complexity of its robust counterpart. Furthermore, we show that already evaluating a first-stage solution is NP-hard when the uncertainty set is discrete. We develop models and solution methods for both continuous and discrete budgeted uncertainty and demonstrate the a

What carries the argument

The two-stage robust optimization framework that fixes the job order in the first stage and adjusts start times in the second stage after uncertainty revelation, subject to a budgeted uncertainty set on the cost functions.

If this is right

The robust counterpart of the scheduling problem is NP-hard and admits no polynomial-time approximation algorithm.
Evaluating the robust cost of any fixed ordering is NP-hard whenever the uncertainty set is discrete.
Models and algorithms can be constructed separately for continuous and discrete budgeted uncertainty sets.
Computational comparisons show that schedules obtained by including uncertainty in the first stage outperform those that ignore it.

Where Pith is reading between the lines

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

The hardness results indicate that practical instances will likely require tailored heuristics or decomposition methods even for moderate sizes.
The two-stage ordering-plus-timing structure may transfer directly to other time-dependent problems such as vehicle routing with variable fuel costs.
If the budgeted-set assumption matches observed cost variation, similar robust two-stage models could improve decisions in related areas like energy-aware production planning.
The experimental advantage suggests that the modeling effort is worthwhile whenever cost uncertainty is both significant and partially observable after ordering.

Load-bearing premise

The cost fluctuations can be represented by a budgeted uncertainty set and the real decision process can be captured by first committing to an order then choosing times after costs are known.

What would settle it

A polynomial-time algorithm that computes the worst-case cost of any given first-stage job order under a discrete budgeted uncertainty set would disprove the claimed NP-hardness of evaluation.

Figures

Figures reproduced from arXiv: 2604.15161 by Dorothee Henke, Javier Alcaraz, Laura Anton-Sanchez, Marc Goerigk, Sof\'ia Rodr\'iguez-Ballesteros.

**Figure 2.** Figure 2: Illustration of the proof of Theorem 4 for the case of n = 4 and K = 3. Theorem 4. For given y ∈ Y, the adversarial problem with execution-time dependent costs and timeslot attacks, i.e., the problem max c∈U˜D(Γ) min x∈X (y) X j∈J X t∈T wjtxjt with U˜D(Γ) = w ∈ R J×T : wjt = wjt + ˜wjt˜δt, ˜δt ∈ {0, 1}, X t∈T ˜δt ≤ Γ , is NP-hard. In order to prove Theorem 4, we first begin with a lemma. It is well-kn… view at source ↗

**Figure 3.** Figure 3: Average adversarial evaluation cost of the schedules obtained with [PITH_FULL_IMAGE:figures/full_fig_p017_3.png] view at source ↗

read the original abstract

In this work, we study a single-machine scheduling problem that aims at minimizing the total cost of a schedule subject to start-time dependent costs. This framework naturally captures scenarios where costs fluctuate throughout the day, such as time-varying energy or labor prices. To model more realistic scenarios, we assume that these costs lie within a budgeted uncertainty set and propose a two-stage robust optimization approach. In a first stage, the order in which activities should be executed is decided. After a cost scenario has been revealed, the starting times for each activity are established, subject to the ordering from the first stage. We demonstrate that the proposed problem is NP-hard and not approximable, implying the complexity of its robust counterpart. Furthermore, we show that already evaluating a first-stage solution is NP-hard when the uncertainty set is discrete. We develop models and solution methods for both continuous and discrete budgeted uncertainty. In computational experiments, we compare these approaches and demonstrate the advantages of including uncertainty beforehand.

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.

Desk Editor's Note private letter to a colleague

This paper sets up a two-stage robust model for single-machine scheduling with budgeted uncertainty on start-time costs, fixing the order first then adjusting times, with matching hardness results and MIPs.

read the letter

The main thing here is a two-stage robust optimization setup for single-machine scheduling where costs depend on start times and fall inside a budgeted uncertainty set. The first stage locks in the job order, and the second stage sets the actual times once a cost scenario is known. This fits applications like energy pricing that changes over the day. They prove the problem is NP-hard and not approximable, show that evaluating a fixed order is already NP-hard for discrete uncertainty, give MIP models for both continuous and discrete cases, and compare the approaches in experiments. The modeling choice to commit to an order upfront is justified by the structure and avoids obvious inconsistencies with the uncertainty handling. The hardness claims follow from standard scheduling reductions extended to the robust setting, which is fine but expected rather than surprising. The experiments are only described at a high level, with no numbers on instance sizes, runtimes, or gaps versus non-robust baselines, so it is hard to judge how practical the methods are for larger problems. The budgeted uncertainty assumption is standard and the paper does not appear to overclaim its generality. This is aimed at operations research readers working on robust scheduling variants with time-varying costs. Someone adapting MIPs for similar energy or labor problems would get usable formulations and complexity context from it. The combination of a new application, formal results, and concrete methods is enough to send it for peer review, though more experimental detail would help.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes a two-stage robust optimization approach for a single-machine scheduling problem with start-time dependent costs under a budgeted uncertainty set. In the first stage, the job order is fixed; in the second stage, start times are optimized after the uncertainty is revealed. The paper establishes that the problem is NP-hard and inapproximable, that evaluating first-stage solutions is NP-hard for discrete uncertainty, develops MIP models for continuous and discrete cases, and reports computational comparisons showing advantages of accounting for uncertainty.

Significance. Assuming the complexity proofs hold via appropriate reductions and the experiments validate the models' performance, this work contributes to the literature on robust scheduling by addressing time-dependent costs with practical uncertainty modeling. It provides both theoretical hardness results and practical solution methods, which could be significant for applications with fluctuating costs like energy pricing.

major comments (2)

[Complexity analysis section] The demonstration that the proposed problem is NP-hard and not approximable, as well as the NP-hardness of evaluating a first-stage solution for discrete uncertainty, requires explicit details on the reductions used (e.g., from which known NP-hard problem) to allow verification of these central claims.
[Computational experiments section] The comparisons between continuous and discrete uncertainty models should include specific metrics such as solution times, optimality gaps, and cost savings (e.g., in a table) to substantiate the claim that including uncertainty beforehand is advantageous.

minor comments (2)

[Abstract] The abstract would be strengthened by briefly indicating the scale of the computational experiments (e.g., number of jobs or instances tested) and key quantitative findings.
The definition of the budgeted uncertainty set and the two-stage decision process should be formalized with equations early in the introduction or problem statement for clarity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We address each major comment below and will revise the paper to incorporate the suggested improvements for greater clarity and substantiation.

read point-by-point responses

Referee: [Complexity analysis section] The demonstration that the proposed problem is NP-hard and not approximable, as well as the NP-hardness of evaluating a first-stage solution for discrete uncertainty, requires explicit details on the reductions used (e.g., from which known NP-hard problem) to allow verification of these central claims.

Authors: We agree that additional explicit details on the reductions would improve verifiability. The proofs in Section 3 establish NP-hardness via reduction from the Partition problem, inapproximability via reduction from the Knapsack problem, and NP-hardness of first-stage evaluation via reduction from the Set Cover problem. In the revised manuscript, we will expand these sections with step-by-step instance constructions, formal mappings, and equivalence arguments directly in the main text (rather than relying on high-level sketches) to allow full verification. revision: yes
Referee: [Computational experiments section] The comparisons between continuous and discrete uncertainty models should include specific metrics such as solution times, optimality gaps, and cost savings (e.g., in a table) to substantiate the claim that including uncertainty beforehand is advantageous.

Authors: We concur that quantitative metrics would better support the claims. The current experiments in Section 5 compare the models qualitatively and via aggregate performance, but lack a consolidated table. In the revision, we will add a new table reporting average solution times, MIP optimality gaps, and percentage cost savings (robust vs. deterministic) for both continuous and discrete cases across all instance classes, directly substantiating the advantages of the two-stage robust approach. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected in the derivation chain

full rationale

The paper formulates a two-stage robust optimization model for single-machine scheduling with budgeted uncertainty on start-time-dependent costs, proves NP-hardness and non-approximability via standard scheduling reductions extended to the robust case, and develops MIP models for continuous and discrete uncertainty sets. These steps rely on explicit problem structure (order fixed in stage one, times adjusted in stage two) and conventional complexity arguments rather than any self-definitional loop, fitted parameter renamed as prediction, or load-bearing self-citation. The distinction between continuous and discrete cases is handled by tailored formulations without internal reduction to the inputs.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The approach rests on the domain assumption that costs can be captured by a budgeted uncertainty set and on standard mathematical results about robust optimization and scheduling complexity.

free parameters (1)

uncertainty budget parameter
The parameter that controls the total allowable deviation in the uncertainty set is a modeling choice that affects the robust solution.

axioms (1)

domain assumption Costs lie within a budgeted uncertainty set
This is invoked to model realistic fluctuations such as time-varying energy or labor prices.

pith-pipeline@v0.9.0 · 5485 in / 1236 out tokens · 45825 ms · 2026-05-10T10:39:53.992078+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

44 extracted references · 31 canonical work pages

[1]

Arnold, K., Gosling, J., and Holmes, D. (2005). The J ava programming language . Addison Wesley Professional, 4 edition. ISBN 978-0321349804

2005
[2]

Artigues, C., Leus, R., and Talla Nobibon, F. (2013). Robust optimization for resource-constrained project scheduling with uncertain activity durations. Flexible Services and Manufacturing Journal , 25:175--205. https://doi.org/10.1007/s10696-012-9147-2

work page doi:10.1007/s10696-012-9147-2 2013
[3]

Baker, K. R. (1974). Introduction to Sequencing and Scheduling . John Wiley & Sons, Inc., New York, USA

1974
[4]

Ben-Tal, A., El Ghaoui, L., and Nemirovski, A. (2009). Robust optimization , volume 28. Princeton University Press. ISBN 9780691143682

2009
[5]

Bendotti, P., Chr \'e tienne, P., Fouilhoux, P., and Pass-Lanneau, A. (2023). The anchor-robust project scheduling problem. Operations Research , 71(6):2267--2290. https://doi.org/10.1287/opre.2022.2315

work page doi:10.1287/opre.2022.2315 2023
[6]

and den Hertog , D

Bertsimas, D. and den Hertog , D. (2022). Robust and Adaptive Optimization . Dynamic Ideas LLC. ISBN 978-1-7337-8852-6

2022
[7]

16 Dimitris Bertsimas, David B

Bertsimas, D. and Sim, M. (2004). The price of robustness. Operations Research , 52(1):35--53. https://doi.org/10.1287/opre.1030.0065

work page doi:10.1287/opre.1030.0065 2004
[8]

and Goerigk, M

Bold, M. and Goerigk, M. (2021). A compact reformulation of the two-stage robust resource-constrained project scheduling problem. Computers & Operations Research , 130:105232. https://doi.org/10.1016/j.cor.2021.105232

work page doi:10.1016/j.cor.2021.105232 2021
[9]

and Goerigk, M

Bold, M. and Goerigk, M. (2022). Investigating the recoverable robust single machine scheduling problem under interval uncertainty. Discrete Applied Mathematics , 313:99--114. https://doi.org/10.1016/j.dam.2022.02.005

work page doi:10.1016/j.dam.2022.02.005 2022
[10]

and Goerigk, M

Bold, M. and Goerigk, M. (2024). Recoverable robust single machine scheduling with polyhedral uncertainty. Journal of Scheduling . https://doi.org/10.1007/s10951-024-00828-7

work page doi:10.1007/s10951-024-00828-7 2024
[11]

A., and Poss, M

Bougeret, M., Pessoa, A. A., and Poss, M. (2019). Robust scheduling with budgeted uncertainty. Discrete Applied Mathematics , 261:93--107. https://doi.org/10.1016/j.dam.2018.07.001

work page doi:10.1016/j.dam.2018.07.001 2019
[12]

Bruni, M., Di Puglia Pugliese , L., Beraldi, P., and Guerriero, F. (2017). An adjustable robust optimization model for the resource-constrained project scheduling problem with uncertain activity durations. Omega , 71:66--84. https://doi.org/10.1016/j.omega.2016.09.009

work page doi:10.1016/j.omega.2016.09.009 2017
[13]

Chaari, T., Chaabane, S., Aissani, N., and Trentesaux, D. (2014). Scheduling under uncertainty: Survey and research directions. In 2014 International Conference on Advanced Logistics and Transport (ICALT) , pages 229--234, Hammamet, Tunisia. IEEE. https://doi.org/10.1109/ICAdLT.2014.6866316

work page doi:10.1109/icadlt.2014.6866316 2014
[14]

Chang, G. J. and Edmonds, J. (1985). The poset scheduling problem. Order , 2(2):113--118. https://doi.org/10.1007/BF00334849

work page doi:10.1007/bf00334849 1985
[15]

A., and Mitchell, J

Chaudhuri, S., Walker, R. A., and Mitchell, J. E. (1994). Analyzing and exploiting the structure of the constraints in the ILP approach to the scheduling problem. IEEE Transactions on Very Large Scale Integration (VLSI) Systems , 2(4):456--471. https://doi.org/10.1109/92.335014

work page doi:10.1109/92.335014 1994
[16]

Garey, M. R. and Johnson, D. S. (1979). Computers and I ntractability. A G uide to the T heory of NP - C ompleteness . W. H. Freeman and Company

1979
[17]

and Hartisch, M

Goerigk, M. and Hartisch, M. (2024). An Introduction to Robust Combinatorial Optimization , volume 361 of International Series in Operations Research & Management Science . Springer. https://doi.org/10.1007/978-3-031-61261-9

work page doi:10.1007/978-3-031-61261-9 2024
[18]

Goerigk, M., Lendl, S., and Wulf, L. (2024). On the complexity of robust multi-stage problems with discrete recourse. Discrete Applied Mathematics , 343:355--370

2024
[19]

Goldratt, E. (1997). Critical Chain . The North River Press

1997
[20]

o flin, H., Liebling, T., and Prodon, A. (1982). Optimal subtrees and extensions. In Bachem, A., Gr \

Gr \"o flin, H., Liebling, T., and Prodon, A. (1982). Optimal subtrees and extensions. In Bachem, A., Gr \"o tschel, M., and Korte, B., editors, Bonn Workshop on Combinatorial Optimization , volume 66 of North-Holland Mathematics Studies , pages 121--127. North-Holland. https://doi.org/10.1016/S0304-0208(08)72447-2

work page doi:10.1016/s0304-0208(08)72447-2 1982
[21]

and Wulf, L

Gr \"u ne, C. and Wulf, L. (2025). Completeness in the polynomial hierarchy for many natural problems in bilevel and robust optimization. In International Conference on Integer Programming and Combinatorial Optimization , pages 256--269. Springer

2025
[22]

and Ulusoy, G

Hazır, O. and Ulusoy, G. (2020). A classification and review of approaches and methods for modeling uncertainty in projects. International Journal of Production Economics , 223:107522. https://doi.org/10.1016/j.ijpe.2019.107522

work page doi:10.1016/j.ijpe.2019.107522 2020
[23]

and Leus, R

Herroelen, W. and Leus, R. (2004). Robust and reactive project scheduling: a review and classification of procedures. International Journal of Production Research , 42:1599--1620. https://doi.org/10.1080/00207540310001638055

work page doi:10.1080/00207540310001638055 2004
[24]

and Leus, R

Herroelen, W. and Leus, R. (2005). Project scheduling under uncertainty: Survey and research potentials. European Journal of Operational Research , 165(2):289--306. https://doi.org/10.1016/j.ejor.2004.04.002

work page doi:10.1016/j.ejor.2004.04.002 2005
[25]

Ikli, S., Mancel, C., Mongeau, M., Olive, X., and Rachelson, E. (2021). The aircraft runway scheduling problem: A survey. Computers & Operations Research , 132:105336. https://doi.org/10.1016/j.cor.2021.105336

work page doi:10.1016/j.cor.2021.105336 2021
[26]

and Zieli \'n ski, P

Kasperski, A. and Zieli \'n ski, P. (2009). A randomized algorithm for the min-max selecting items problem with uncertain weights. Annals of Operations Research , 172:221--230. https://doi.org/10.1007/s10479-009-0564-x

work page doi:10.1007/s10479-009-0564-x 2009
[27]

and Zieli \'n ski, P

Kasperski, A. and Zieli \'n ski, P. (2019). Risk-averse single machine scheduling: complexity and approximation. Journal of Scheduling , 22:567--580. https://doi.org/10.1007/s10951-019-00599-6

work page doi:10.1007/s10951-019-00599-6 2019
[28]

and Sprecher, A

Kolisch, R. and Sprecher, A. (1997). PSPLIB - A project scheduling problem library: OR software - ORSEP operations research software exchange program. European Journal of Operational Research , 96(1):205--216. https://doi.org/10.1016/S0377-2217(96)00170-1

work page doi:10.1016/s0377-2217(96)00170-1 1997
[29]

Liu, Y., Jin, S., Zhou, J., and Hu, Q. (2023). A branch-and-bound algorithm for the unit-capacity resource constrained project scheduling problem with transfer times. Computers & Operations Research , 151:106097. https://doi.org/10.1016/j.cor.2022.106097

work page doi:10.1016/j.cor.2022.106097 2023
[30]

Mastrolilli, M., Mutsanas, N., and Svensson, O. (2013). Single machine scheduling with scenarios. Theoretical Computer Science , 477:57--66

2013
[31]

H., Schulz, A

M \"o hring, R. H., Schulz, A. S., Stork, F., and Uetz, M. (2001). On project scheduling with irregular starting time costs. Operations Research Letters , 28(4):149--154. https://doi.org/10.1016/S0167-6377(01)00064-5

work page doi:10.1016/s0167-6377(01)00064-5 2001
[32]

H., Schulz, A

M\" o hring, R. H., Schulz, A. S., Stork, F., and Uetz, M. (2003). Solving project scheduling problems by minimum cut computations. Management Science , 49(3):330--350. https://doi.org/10.1287/mnsc.49.3.330.12737

work page doi:10.1287/mnsc.49.3.330.12737 2003
[33]

Pinedo, M. L. (2016). Scheduling: Theory, Algorithms, And Systems . Springer Cham, 6 edition. https://doi.org/10.1007/978-3-031-05921-6

work page doi:10.1007/978-3-031-05921-6 2016
[34]

Riedler, M., Jatschka, T., Maschler, J., and Raidl, G. R. (2020). An iterative time-bucket refinement algorithm for a high-resolution resource-constrained project scheduling problem. International Transactions in Operational Research , 27(1):573--613. https://doi.org/10.1111/itor.12445

work page doi:10.1111/itor.12445 2020
[35]

O., Maxwell, W

Roundy, R. O., Maxwell, W. L., Herer, Y. T., Tayur, S. R., and Getzler, A. W. (1991). A price-directed approach to real-time scheduling of production operations. IIE Transactions , 23(2):149--160. https://doi.org/10.1080/07408179108963850

work page doi:10.1080/07408179108963850 1991
[36]

and Karabuk, S

Sabuncuoglu, I. and Karabuk, S. (1999). Rescheduling frequency in an FMS with uncertain processing times and unreliable machines. Journal of Manufacturing Systems , 18(4):268--283. Special issue on scheduling: F rom Research Into Practice. https://doi.org/10.1016/S0278-6125(00)86630-3

work page doi:10.1016/s0278-6125(00)86630-3 1999
[37]

K., Bricker, D., and Juang, S.-H

Sankaran, J. K., Bricker, D., and Juang, S.-H. (1999). Strong Fractional Cutting-Plane Algorithm for Resource-Constrained Project Scheduling https://www.scopus.com/inward/record.uri?eid=2-s2.0-0032653343&partnerID=40&md5=de895e6b5b4c3fb9ae38473480d00847. International Journal of Industrial Engineering: T heory, Applications and Practice , 6:99--111

1999
[38]

Shabtay, D. (2023). A new perspective on single-machine scheduling problems with late work related criteria. Annals of Operations Research , 322(2):947--966. https://doi.org/10.1007/s10479-022-04806-0

work page doi:10.1007/s10479-022-04806-0 2023
[39]

Sourd, F. (2009). New exact algorithms for one-machine earliness-tardiness scheduling. INFORMS Journal on Computing , 21:167--175. https://doi.org/10.1287/ijoc.1080.0287

work page doi:10.1287/ijoc.1080.0287 2009
[40]

and Chaudhuri, D

Suresh, V. and Chaudhuri, D. (1993). Dynamic scheduling -- a survey of research. International Journal of Production Economics , 32(1):53--63. https://ideas.repec.org/a/eee/proeco/v32y1993i1p53-63.html

1993
[41]

and Smith, J

Tadayon, B. and Smith, J. C. (2015). Algorithms and complexity analysis for robust single-machine scheduling problems. Journal of Scheduling , 18(6):575--592

2015
[42]

Van Cauwelaert, S., Dejemeppe, C., and Schaus, P. (2020). An efficient filtering algorithm for the unary resource constraint with transition times and optional activities. Journal of Scheduling , 23:431--449. https://doi.org/10.1007/s10951-019-00632-8

work page doi:10.1007/s10951-019-00632-8 2020
[43]

and Yu, G

Yang, J. and Yu, G. (2002). On the robust single machine scheduling problem. Journal of Combinatorial Optimization , 6(1):17--33

2002
[44]

and Zhao, L

Zeng, B. and Zhao, L. (2013). Solving two-stage robust optimization problems using a column-and-constraint generation method. Operations Research Letters , 41(5):457--461. https://doi.org/10.1016/j.orl.2013.05.003

work page doi:10.1016/j.orl.2013.05.003 2013