Abstract: The problem studied in this paper comes from the dispatchers' department of airline operation control centers. When dispatchers dispatch the flight, it is necessary to ensure punctuality for flights to take off, and regulate the rhythm of flight dispatched to ensure the quality of dispatch. The problem is described as a single machine scheduling problem with n task in this paper. Each task has release time, deadline and processing time, and the goal is to minimize the peak load of the machine, restrict to the conditions of each task ended before its deadline. Under the goal, an effective algorithm and the proof of the performance of algorithm are proposed.

Key words: airline dispatchers, single machine scheduling, peak load, task allocation