Appointment Scheduling with Discrete Random Durations

作者：Begen Mehmet A^*; Queyranne Maurice

来源：Mathematics of Operations Research, 2011, 36(2): 240-257.

DOI：10.1287/moor.1110.0489

• appointment scheduling
• discrete convexity
• optimization

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.

• 出版日期2011-5