A method for improving an agent schedule comprises unscheduling an agent from a shift in the schedule; evaluating a score function for each of a plurality of possible schedules which have the agent scheduled for different possible shifts; and selecting an improved schedule from among the plurality of possible schedules. The improved schedule is characterized by an improved value of the score function. The above steps are repeated until a locally optimal schedule is obtained. The break times in the possible shifts are not necessarily scheduled in the above procedure. In another aspect of the invention, a method is provided for optimal break scheduling. The method includes the steps of unscheduling a break; evaluating a score function for a plurality of possible break times for the break; and selecting an improved break time from the possible break times. The improved break time is characterized by an improved score. In the above procedures, the evaluation of the score function for a possible schedule includes selecting, for each interval in the possible schedule, one of a plurality of predetermined values corresponding to distinct staffing levels.