Emergency planning: Small airport scheduling in disaster relief

We study a novel small airport scheduling problem encountered in Wenchuan Earthquake and in Yushu Earthquake (China) disaster relief. The small airport has one runway for taking off and landing airplanes and several identical aircraft stands for discharging. To make the relief supplies arrive at the disaster area more quickly, the problem is to find a schedule with minimum schedule length which consist of deciding: when to land an airplane, which aircraft stand it is assigned to discharge relief supplies and its departure time for leaving airport, so that all airplanes are served without preemption. Note that the runway and each aircraft stand can serve only one airplane at a time. No airplane is allowed to land when all aircraft stands are occupied at that moment for the sake of the unique runway. We first describe the scheduling problem as a two-stage flexible reentrant flow shop (TSFRFS) with no intermediate buffer and investigate its dominance properties. The TSFRFS is thus reduced to a constrained permutation problem based on these theoretical properties. For practice interest, a GRASP algorithm is finally proposed to find near optimal solution to the TSFRFS. Numerical results on randomly generated instances are also presented.