This paper considers the problem of scheduling a multi-spindle CNC gantry mill. Multiple spindle gantry mills are characterized by their ability to process multiple numbers of parts simultaneously and that they allow a setup on one part to take place while the spindle is processing other parts (sequence dependent setup times for jobs). These characteristics, though effective in reducing the overall production lead-time, complicate the scheduling of gantry mills. In this paper we classify the 'gantry scheduling problem' as a batch sequencing problem (BSP) with sequence dependent setup times and multiple part machining locations (PML) [1]. We consider the dual objectives of minimizing maximum lateness and minimizing total setup time and present a two-level heuristic to solve the problem. Finally we evaluate the performance of the heuristic and propose a framework for implementing the solution.