Stochastic scheduling problems for minimizing tardy jobs with application to emergency vehicle dispatching on unreliable road networks.

摘要

In the wake of a natural disaster such as a major earthquake, there will be many casualties. These casualties will be spatially scattered across a potentially damaged transportation infrastructure. Emergency operators will try to save as many lives as possible by dispatching limited resources such as ambulances and other emergency vehicles to transport the injured to available hospital beds. These dispatching decisions will be complicated by the uncertainty in the transportation network.; The primary goal of this research is to investigate good ways to dispatch emergency vehicles in order to maximize the number of survivals in an emergency situation. Scheduling approaches are proposed to sequence injured parties based on their location and severity of injury. The casualties (jobs) are treated before an unknown expiration (due) date. Processing times are also unknown and involve the travel time to and from the casualty location. The stochastic nature of these processing times and due dates necessitates a stochastic scheduling approach.; This research investigates three different types of stochastic scheduling problems for maximizing the number of early jobs. In the first case, processing times are independent and identically distributed and independent due dates follow distinct exponential distributions. A dynamic program which runs much faster than traditional assignment problems is developed using a necessary condition for optimal solutions called a Pivot Rule. For parallel machines, a binary integer program is also developed that can be solved by its linear programming relaxation.; In the second case, due dates are considered either common or exchangeable. A pairwise rank based policy is introduced and compared to the known probabilistic slack policy. These two policies are complementary in that they generate optimal sequences under separate conditions. Therefore, a combination of these two policies is proposed.; Finally, for arbitrary independent processing times and independent distinct exponential due dates, methods for maximizing the number of early enough jobs are discussed. A revised Moore's algorithm is developed along with a sufficient order-invariance condition for optimality. For the case where the sufficient condition is not met, a binary integer program that is relatively easy to solve is proposed.; We conclude this research with a real application to emergency vehicle dispatching in the site of the Northridge earthquake of 1994 in California.