Scheduling outpatients and medical operation rooms has the following structure:Nusers are given appointment times to use a facility, the duration required by the facility to service each user is stochastic. The system incurs a “user idle cost” if a user arriving at the appointed time finds the facility still engaged by preceding users, while a “facility idle cost” is incurred if the facility becomes free before the next user arrives. We develop an accurate procedure to compute the expected total system costs for any given appointment schedule. Compared to earlier related procedures, ours is much faster and can handle larger problems as well as very general service-time distributions. We then show that this fast computation procedure enables one to determine easily the “lowest-cost appointment schedule” for any given “job” (i.e., “user”) sequence. This in turn will enable one to search for the optimal job sequence that has the best “lowest-cost appointment schedule”.