An approximation algorithm for scheduling aircraft with holding time

We consider the problem of scheduling arrival air traffic in the vicinity of large airports. The problem is posed as a single queue problem, from which aircraft can be pulled out and put "on hold", in holding loops, each loop taking a fixed amount of time to traverse before they join the queue again. The difficulty of deriving efficient solutions to this problem (which is currently controlled non optimally by human air traffic controllers) is the minimization of "idle time" generated by traversing an integer number of loops. We formulate this problem as a single machine scheduling problem where we are given N jobs characterized by release times and deadlines. We are given a processing time and and a holding time. In a feasible schedule, each job is assigned a starting time within a constraint set corresponding to an integer number of processing times and holding times. Our goal is to find feasible schedules to alternatively minimize two objectives: the sum of the starting times of all jobs and the makespan (the time at which all jobs are finished). We present approximation algorithms which can alternatively approximate two objectives with factors of 5 and 3. respectively. Our main algorithm consists of solving two subproblems one of which is solved optimally using dynamic programming, while the other is solved approximately using linear programming relaxation and rounding.