It is common for Air Traffic Controllers to control air traffic during the night and to experience fatigue. Although fatigue is not the direct cause of aviation accidents, 21 percent of accidents are fatigue-related. Therefore countries and companies have tried to regulate work hours to avoid extreme fatigue, thus decreasing human error resulting from fatigue. However, these regulations may not reflect that actual fatigue variation and fatigue levels can be decreased still more by scheduling appropriately. This paper focuses on optimal work shift scheduling to reduce air traffic controller fatigue. First, a mathematical model is established to describe fatigue levels. The objective function is to reduce the fatigue peak produced by work shifts as much as possible. Various constraints, such as holidays and manpower requirements are considered. The optimization problem is then solved using integer programming. We take a sample schedule and draw conclusions by comparing our results with the original fatigue levels.