Scheduling disaster relief operations

Effective scheduling of disaster-relief operations has proved significant to the lives of those affected by disasters. The time at which specific relief operations arrive to and commence in a devastated area can have an effect on the number of deaths that occur. Motivated by the recent Tsunami and Katrina disasters, this dissertation gives some insight on the nature of disaster-relief operations and models these operations as a class of parallel machine scheduling problems. An efficient procedure to maximize on-time delivery of relief operations is presented. A mixed integer programming formulation to the problem is given with the objective of minimizing total weighted tardiness (TWT). After establishing the complexity of the problem, we analyze the problem using both an evolutionary algorithm and a precedence-constrained apparent tardiness cost rule with ready times. Both methodologies show good solution promise when compared against known optimal solutions in a few fractions of a second of computation time for representative problem instances.;Finally, we attempt to assess the risks involved in scheduling disaster-relief operations. This research is motivated by the reality that job-specific parameters relating to ready times, processing times, weights, or due dates can and often do change rapidly during the first few hours once a natural disaster is declared. Stochastic scheduling policies are commonly used when job data follows some know distribution; however, we implement a multi-stage genetic algorithm that approximately solves this NP-hard problem deterministically every time new information regarding any of these parameters becomes available. A case study is conducted to produce approximate Pareto front showing total costs involved versus gains in total weighted tardiness objective. The GA is extended to solve the problem under two scenarios: a fixed cost scenario and a variable cost scenario. We demonstrate the efficacy of the proposed solution approaches in terms of their ability to assess and mitigate risk.;Next, we examine a tri-criteria version of the disaster-relief operations scheduling problem. The performance measures in interest are total weighted completion time, maximum earliness, and number of tardy jobs. We implement Non-Dominated Sorting Genetic Algorithm II (NSGA-II) that finds the set of approximate efficient schedules to a tri-criteria scheduling problem. We propose three different algorithms that differ according to the reproduction mechanism within NSGA-II. Namely, we assess the performance of (1) NSGA-II as presented by Deb et al. (2002); (2) a modified version of NSGA-II called NSGA-IIα wherein new chromosomes are introduced at each generation up to a fixed level α of the population size; and (3) a strict, elitist NSGA-II we term SENSGA-II. As the proposed problem for any one of the objectives individually is known to be NP hard in the strong sense for the parallel machine environment, we propose lower bounds based on job preemption in order to produce an ideal (unattainable) solution for the tri-criteria problem. This ideal solution approach will be used as a benchmark in assessing the efficiency and diversity of the obtained Pareto front for this multi-objective problem.