Problem definition: In many resource scheduling problem for services with scheduled starting and com- pletion times (e.g., airport gate assignment), a common approach is to maintain appropriate buffer between successive services assigned to a common resource. With a large buffer, the chances of a “crossing” (i.e., a flight arriving later than the succeeding one at the gate) will be significantly reduced. This approach is often preferred over more sophisticated stochastic mixed-integer programming (MIP) methods that track the arrival of all the flights to infer the number of “conflicts” (i.e., a flight arriving at a time when the assigned gate becomes unavailable). We provide a theoretical explanation, from the perspective of robust optimization, for the good performance of the buffering approach in minimizing not only the number of crossings, but also the number of conflicts in the operations.
Methodology/results: We show that the buffering method inherently minimizes the worst-case number of “conflicts” , under both robust and distributionally robust optimization models using down-monotone uncer- tainty sets. Interestingly, under down-monotone properties, the worst-case number of crossings is identical to the worst-case number of conflicts. Using this equivalence, we demonstrate how feature information from flight and historical delay information can be used to enhance the effectiveness of the buffering method.
Managerial implications: The paper provides the first theoretical justification on the use of buffering method to control for the number of conflicts in resource assignment problem.
