This paper presents a manpower tour-scheduling approach that involves determining the manning requirements and optimum employee work schedules for several security gates. The two-stage approach is used to minimize the total labor cost of security personnel. In stage 1, manning requirements are determined based on the results of a manpower workload study at the company. In stage 2, an integer programming model is formulated to satisfy each gate’s staffing requirements during weekdays and weekends. The objective is to minimize the total labor cost of both Non-supervising and Supervising employees. The model proposed an alternative work schedule combination that resulted in annual savings of 24% in comparison to the schedule currently in use by the company.