Scheduling with Testing of Heterogeneous Jobs
研究了一个通用调度模型，权衡处理作业与测试诊断，提出两种简单启发式策略，在数值实验中平均接近最优（误差低于0.1%），对运营管理学者和调度实践者有用。
This paper studies a canonical general scheduling model that captures the fundamental trade-off between processing jobs and performing diagnostics (testing). In particular, testing reveals the required processing time and urgency of need-to-schedule jobs to inform future scheduling decisions. The model captures a range of important applications. Prior work focused on special cases (e.g., jobs with independent and identically distributed processing time) to devise optimal policies. In contrast, the current paper studies the most general form of the model and describes two simple heuristics to solve it; adaptive weighted shortest processing time is an adaptive generalization of Smith’s rule that optimally solves several important extensions of previously studied models, whereas index policy optimally solves a closely related stochastic optimization bandit problem. The latter achieves an approximation guarantee that quickly approaches a constant factor that is bounded by two as the number of jobs grows and approaches optimally when the testing time decreases. Extensive numerical experiments suggest that our policies effectively solve the general setting (under 0.1% from optimal on average and under 10% from optimal in rare, worst-case instances). This paper was accepted by Jeannette Song, operations management. Supplemental Material: The data files and online appendix are available at https://doi.org/10.1287/mnsc.2023.4833 .