We study a manpower scheduling problem with job time-windows and job-skills compatibility constraints. This problem is motivated by airline catering operations, whereby airline meals and other supplies are delivered to aircrafts on the tarmac just before the flights take off. Jobs (flights) must be serviced within a given time-window by a team consisting of a driver and a loader. Each driver/loader has the skills to service some, but not all, of the airline/aircraft/configuration of the jobs. Given the jobs to be serviced and the roster of workers for each shift, the problem is to form teams and assign teams and start-times for the jobs, so as to service as many flights as possible. Only teams with the appropriate skills can be assigned to a flight. Workload balance among the teams is also a consideration. We present a model formulation and investigate a tabu-search heuristic approach to solve the problem. The tabu search approach employs strategic oscillation and diversification to try to explore a broad region of the solution space. Computational examples suggest that the tabu search approach can find good solutions.