A branch-and-bound heuristic for outpatients appointment scheduling systems

摘要

Appointment-based service systems admit limited number of customers during a specific time interval to make them more accessible by reducing customers' waiting time and make the costly resources more productive. A traditional approach suggests the Bailey rule, which assigns one or more customers at the initial block and only one customer at remaining blocks. We prescribe a heuristic approach and variations of the traditional Bailey rule to appointment scheduling systems with the objective of minimizing total expected costs of delay- and idle-times between blocks. The heuristic adopts a branch-and-bound approach using forward dynamic programming and tries to fully enumerate with some restrictions. We conduct numerical tests, which show that the heuristic gets near-optimal solutions in a quicker time than a commercial solver, CPLEX. In addition, we suggest the use of a periodic Bailey rule, which provides a close solution to the best result of the heuristics, depending upon cost parameters and service time variances.