Appointment schedules aim at achieving a proper balance between the conflicting interests of the service provider and her clients: a primary objective of the service provider is to fully utilize her available time, whereas clients want to avoid excessive waiting times. Setting up schedules that strike a good balance is severely complicated by the fact that the clients' service times are random. Because of the lack of explicit expressions, one has often set up schedules relying on simulation techniques. In this paper, we take a radically different approach: we use newly developed analytical techniques to numerically determine optimal schedules (i.e., schedules that optimize a given objective function that incorporates the interests of the service provider as well as the clients) and compare them with a number of easily evaluated heuristics; in our setup, it is throughout assumed that a given fraction of the clients does not show up. Our results are particularly useful in situations in which there is a significant variation in the service times, which is typically the case in various healthcare‐related settings. Copyright © 2015 John Wiley & Sons, Ltd.