Technical Note-A Sampling-Based Approach to Appointment Scheduling

• 成果类型: Article
• 署名作者: Begen, Mehmet A.; Levi, Retsef; Queyranne, Maurice
• 署名单位: Western University (University of Western Ontario); Massachusetts Institute of Technology (MIT); University of British Columbia
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1120.1053
• 发表日期: 2012
• 页码: 675-681
• 关键词: systems; times

摘要

We consider the problem of appointment scheduling with discrete random durations but under the more realistic assumption that the duration probability distributions are not known and only a set of independent samples is available, e.g., historical data. For a given sequence of appointments (jobs, tasks), the goal is to determine the planned starting time of each appointment such that the expected total underage and overage costs due to the mismatch between allocated and realized durations is minimized. We use the convexity and subdifferential of the objective function of the appointment scheduling problem to determine bounds on the number of independent samples required to obtain a provably near-optimal solution with high probability.