We study an appointment-based queue with two classes of customers whose excessive service times are stochastically ordered. The objective is to find the optimal sequence of arrivals to minimize the total waiting time of customers. We first show that the optimal sequence does not follow the Shortest Expected Processing Time first (SEPT) and the Smallest Variance first (SV) rules in general. Then we identify and prove an important property, the First Half Rule (FHR), of the optimal sequence. We also extend our analysis to a system where the server is unpunctual and the two customer classes are different in their no-show probabilities instead of the excessive service times. Besides many applications in healthcare, such as scheduling surgeries in operating rooms and out-patients scheduling in clinics, FHR can be applied to improve airport gate or runway schedules as well.