A queue-dependent 2-cutoff heuristic for scheduling of routine and urgent tasks

Abstract The presence of urgent customers, whose service cannot be delayed, is common in clinics, maintenance systems, government departments, etc. As a result, service slots are often reserved for such customers, and if the number of arrivals exceeds the reserved capacity, costly overtime work may be incurred. In contrast, routine customers can be appointed to a later day. The system manager must decide how many routine customers to serve today and how many to postpone, given the current number of unserved routine customers. We characterize the optimal strategy that minimizes the expected waiting and overtime costs, and introduce a 2-cutoff heuristic that closely approximates the optimal policy. In addition, we examine a special case with no urgent customers and propose alternative solution methods for this simpler setting.