manufacturing process managers

Abstract: We study preemptive single-machine scheduling with predictions, where a prediction of the order of the jobs (or of their sizes) is available, and the objective is to minimize the total completion time. An algorithm is $c$-consistent if it is $c$-competitive when the prediction is correct, and $R$-robust if it is $R$-competitive whatever the prediction. Since the introduction of this problem as one of the first examples of learning-augmented algorithms, the best possible trade-off between consistency and robustness has remained open. We determine it exactly for deterministic algorithms. For every $R>2$, we give an $R$-robust algorithm whose consistency is \[ c(R)=R\Big(1-\Big(1-\frac{R+2}{R^2}\Big)^{\frac R{R+2}}\Big), \] and we prove that no deterministic $R$-robust algorithm, with either predicted order or predicted job sizes, has better consistency. In particular, consistency $1+\eps$ is achievable with robustness $\eps^{-1/2}+\frac16+O(\sqrt\eps)$, whereas all previous algorithms required robustness $Θ(1/\eps)$. Our algorithm is greedy: it follows the predicted order as fast as possible, subject to the invariant that the cost paid so far is at most $R$ times the optimum of the instance in which every unfinished job would end immediately. The matching lower bound rests on the observation that every robust deterministic algorithm must satisfy the same invariant along its run on correct predictions.

Abstract: Expected improvement (EI) based on stochastic kriging (SK) surrogate is widely used in continuous simulation optimization, but unknown heteroscedastic noise on simulation output makes three basic design choices consequential: the incumbent used to define improvement, the replication level at each sampled point, and the terminal recommendation. Existing methods typically either assume the noise levels are known or choose these components separately through heuristic rules or empirical calibration. We instead derive a high-probability upper bound on the simple regret and systematically choose the three components within general rule classes to tighten this bound. We first establish a finite-sample confidence bound for the SK predictor with unknown and estimated noise levels as a foundation for the three design choices. We then analyze general posterior-quantile families for both the incumbent and the terminal recommendation. For the incumbent, minimizing the regret bound selects a lower quantile coefficient that matches the coefficient in the SK predictor confidence bound. For the terminal recommendation, minimizing the same bound instead selects the sampled point with the best upper posterior quantile under the same coefficient. These opposite quantile choices reflect the different roles of search and implementation in simulation optimization. Intermediate simulations are exploratory with an optimistic incumbent, while the terminal recommendation is implemented in the real system and is therefore relatively conservative about the remaining posterior uncertainty. Under mild conditions satisfied by common kernels, minimizing a tractable kernel-specific bound yields $Θ(\log T)$ replications. To our knowledge, this is the first simple-regret guarantee for a continuous-domain EI-type simulation optimization method that learns unknown heteroscedastic variances through replications.