Disruption managment for project scheduling problem
This dissertation studies the resource-constrained project scheduling problem under disruptions. The focus is on how to formulate such problems and solve them efficiently. The work includes mainly three parts. First, we present an exact branch-and-cut algorithm for the multi-mode resource-constrained project scheduling problem based on an integer linear programming (ILP) formulation (Chapter 4). We proposed several techniques that accelerate the solution process, such as variable reduction, special branching and bound-tightening schemes, and cuts. To find good feasible solutions in the early stages of the computations, a high level neighborhood search strategy known as local branching is included. As implemented, the full algorithm is exact in nature, but can be applied as an heuristic when solution time is limited. Second, we study the problem of how to react when an ongoing project is disrupted (Chapter 5). We begin by proposing a classification scheme for the different types of disruptions and then define the constraints and objectives that comprise what we call the recovery problem. The goal is to get back on track as soon as possible at minimum cost, where cost is now a function of the deviation from the original schedule. The problem is formulated as an integer linear program and solved with a hybrid mixed-inter programming/constraint programming procedure that exploits a number of special features in the constraints. Finally, we investigate the problem of setting target finish times for project activities with random durations (Chapter 6). Using two-stage integer linear stochastic programming, target times are determined in the first stage followed by the development of a detailed project schedule in the second stage. The objective is to balance the cost of project completion as a function of activity target times with the expected penalty cost incurred by deviating from the specified values. It is shown that the results may be significantly different when deviations are considered, compared to when activities are scheduled as early as possible in the traditional way. To find solutions, an exact algorithm is developed for the case without a budget constraint and is used as a part of a heuristic when crashing cost is limited. For all the aspects, detailed examples and numerical results are provided to show the details of modeling process and the efficiency of proposed algorithms. We also find that project scheduling problem under disruptions is very different from a deterministic project scheduling problem, and leads to several useful managerial insights.