PLANNING TIMELY ARRIVALS TO A STOCHASTIC PRODUCTION OR SERVICE SYSTEM

A stochastic planning problem of determining the optimal arrival times for N customers, each to be assigned to one of K equal time slots, is considered. The objective is to minimize the total system cost, which is composed of the customer waiting cost and the server availability cost. This optimal arrival schedule is examined for a single server system with either exponential or Erlang-k service time distribution. Two versions of this planning arrival problem are considered, a dynamic version and a static version. The dynamic problem requires planning decisions to be made at the beginning of each time slot, while in the static problem all decisions must be made at the beginning of the first time slot. The dynamic problem is solved by dynamic programming. The structure of the optimal dynamic policy is identified and used to solve the dynamic problem efficiently. A branch-and-bound algorithm, which uses the solution to the dynamic problem, is developed to solve the static problem. The results can be used to schedule material deliveries, work-in-process flows, appointments, or other similar systems.