Scheduling with Testing

• 成果类型: Article
• 署名作者: Levi, Retsef; Magnanti, Thomas; Shaposhnik, Yaron
• 署名单位: Massachusetts Institute of Technology (MIT); Singapore University of Technology & Design; University of Rochester
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2017.2973
• 发表日期: 2019
• 页码: 776-793
• 关键词: scheduling; dynamic programing; service oprations; Approximation algorithms

摘要

We study a new class of scheduling problems that capture common settings in service environments, in which one has to serve a collection of jobs that have a priori uncertain attributes (e.g., processing times and priorities) and the service provider has to decide how to dynamically allocate resources (e.g., people, equipment, and time) between testing (diagnosing) jobs to learn more about their respective uncertain attributes and processing jobs. The former could inform future decisions, but could delay the service time for other jobs, while the latter directly advances the processing of the jobs but requires making decisions under uncertainty. Through novel analysis we obtain surprising structural results of optimal policies that provide operational managerial insights, efficient optimal and near-optimal algorithms, and quantification of the value of testing. We believe that our approach will lead to further research to explore this important practical trade-off.