Appointment Scheduling with Discrete Random Durations

• 成果类型: Article
• 署名作者: Begen, Mehmet A.; Queyranne, Maurice
• 署名单位: Western University (University of Western Ontario); University of British Columbia
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1110.0489
• 发表日期: 2011
• 页码: 240-257
• 关键词: submodular function; ARRIVALS; systems; service; times; care

摘要

We consider the problem of determining an optimal appointment schedule for a given sequence of jobs (e. g., medical procedures) on a single processor (e. g., operating room, examination facility, physician), to minimize the expected total underage and overage costs when each job has a random processing duration given by a joint discrete probability distribution. Simple conditions on the cost rates imply that the objective function is submodular and L-convex. Then there exists an optimal appointment schedule that is integer and can be found in polynomial time. Our model can handle a given due date for the total processing (e. g., end of day for an operating room) after which overtime is incurred, as well as no-shows and some emergencies.