Scheduling with Testing of Heterogeneous Jobs

Retsef Levi (), Thomas Magnanti () and Yaron Shaposhnik ()
Additional contact information
Retsef Levi: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Thomas Magnanti: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139; Singapore University of Technology and Design, Singapore 138682
Yaron Shaposhnik: Simon Business School, University of Rochester, Rochester, New York 14627

Management Science, 2024, vol. 70, issue 5, 2934-2953

Abstract: 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).

Keywords: scheduling; testing; dynamic programming; convex order; index policy (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.2023.4833 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:70:y:2024:i:5:p:2934-2953

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().