Problem definition: We study optimal scheduling of customers in service systems, such as call centers. In such systems, customers typically hang up and abandon the system if their wait for service is too long. Such abandonments are detrimental for the system, and so managers typically use scheduling as a tool to mitigate it. In this paper, we study the interplay between customer impatience and scheduling decisions when managing heterogeneous customer classes. Academic/practical relevance: Call centers constitute a large industry that has a global spending of around $300 billion and employs more than 15 million people worldwide. Our work focuses on improving call center operations, which can reduce costs and improve customer satisfaction. Mathematically, customer patience is typically modeled as exponentially distributed for tractability. Our work makes inroads into relaxing this restrictive assumption to allow modeling more realistic call center situations. Methodology: We use heavy traffic–motivated asymptotic queueing machinery that provides us the traction to successfully capture and incorporate the customer impatience distribution into the scheduling problem. In our approach, the scheduling problem reduces to a diffusion control problem, which we solve to propose near-optimal scheduling policies. Results: We propose near-optimal scheduling policies that can be implemented by call centers to improve their quality-of-service metrics. One of our main results is that, for a class of parameters, we establish sufficient conditions for both the optimality and nonoptimality of threshold policies. Managerial implications: Threshold policies are widely used for scheduling. Our work provides additional insight into whether these may be suboptimal. Our work provides an easy-to-implement alternative that can reduce customer abandonments considerably; for instance, our numerical results indicate that for a system with two customer types, the abandonment rate of one class can be lowered by 30% by using our policy relative to the best threshold policy. The online appendix is available at https://doi.org/10.1287/msom.2017.0642 .