On Problems of Safe Transportation by a Single Helicopter

DOI: 10.5176/2251-1938_ORS18.12

Authors: Hans Kellerer, Vitaly A. Strusevich

Abstract:

In a low-risk helicopter scheduling the goal is to determine a pickup and delivery schedule for a flight that starts at a heliport (depot), visits several destinations and returns to the heliport so that the overall risk associated with take-offs and landings is minimized. We consider a situation that each destination is given individual risk estimates for take-offs and landings. We show that if the helicopter capacity is sufficient to perform all pickups and deliveries, then the problem reduces to a single machine scheduling and is solvable in polynomial time. If the capacity is not sufficient, then in the case of pickup only the problem of determining a subset of destinations to be visited in order to minimize the overall risk plus the total penalty for not visiting other destinations reduces to minimizing a pseudo-Boolean quadratic function under a linear knapsack constraint and admits a fully polynomial-time approximation scheme.

Keywords: low-risk transportation; single machine scheduling, weighted total completion time, half-product, FPTAS