Sequencing and scheduling appointments on multiple servers with stochastic service durations and customer arrivals

In this paper, we consider the problem of sequencing and scheduling appointments on multiple servers with stochastic service durations and customer arrivals. The objective is to minimize the weighted sum of server staffing cost and total expected cost of customer waiting, server idleness and overtime. To solve the problem, we first formulate it as a two-stage integer program, where the second stage involves multiple stochastic linear programs. Based on this, we then derive a deterministic mixed-integer linear program for the problem via sample average approximation and further strengthen the formulation by exploiting problem properties. Due to the high complexity of the problem, we also propose an efficient integer Lshaped based heuristic, which is further enhanced by variable neighborhood descent. Our computational experiments show that the proposed integer L-shaped heuristic dominates the strengthened deterministic program and integer L-shaped method especially for large-scale problems, while the incorporation of variable neighborhood descent can significantly improve the performance of the heuristic. Our computational results also reveal that variations in service durations and fluctuations as well as customer unpunctual times have significant impacts on the system performance, while optimizing appointment sequencing decision can help reduce operational cost. (c) 2021 Elsevier Ltd. All rights reserved.

Automated summary

This paper addresses the problem of sequencing and scheduling appointments on multiple servers with stochastic service durations and customer arrivals. By formulating it as a two-stage integer program and deriving a deterministic mixed-integer linear program, the paper provides solutions to minimize the operational cost and improve system performance. The proposed integer L-shaped heuristic, enhanced by variable neighborhood descent, outperforms the deterministic program and integer L-shaped method, especially for large-scale problems, demonstrating significant impacts of appointment sequencing decisions on reducing operational cost.