Project planning algorithms: Lowering cost and improving delivery time in capital projects

With the goal of developing models and approaches leading to better operation of large-scale project delivery supply chains, we interviewed a variety of consultants and project and supply chain managers (with a particular emphasis on oil and gas major capital project delivery) and asked them a set of questions so that we could better understand current capital project delivery views of supply chain management, inventory, risk management tools, and related topics (Appendix A). Our interviewees expressed surprisingly diverse opinions, particularly regarding the future of mega-project delivery and the need for more closely coordinating supplier deliveries with onsite needs. The work in the dissertation is particularly motivated by mega-projects in the oil and gas industry, and our goal is to build models that lead to better operation of capital project delivery supply chains. The characteristics of this industry, and of these projects, place specific requirements on project scheduling models, and many of the existing models in the literature do not meet these requirements. Our focus in this dissertation is to formulate models and develop approaches that are particularly useful for mega-projects in the oil and gas industry, and that enable the concurrent determination of the project schedule and inventory delivery times in order to efficiently manage the project supply chain, and to effectively control project delivery time and cost. We consider the Stochastic Resource-Constrained Project Scheduling Problem with inventory, where the objective is to minimize a weighted combination of the expected project makespan and the expected inventory holding costs. Motivated by the requirements of major oil and gas industry projects, we introduce a class of proactive policies for the problem. We develop several effective heuristics for this problem, as well as deterministic and probabilistic lower bounds on the optimal solution. In computational testing, we demonstrate the effectiveness of these heuristics and develop insights into the value of explicitly considering inventory in this setting. A related problem that arises is the scheduling of oil field drilling operations, where the goal is to maximize the expected revenue generated by oil extraction. For this problem, we build a model and propose a heuristic approach. We confirm the effectiveness of our heuristic approach by analyzing its performance compared to the current practice in a real-world case study. Our results demonstrate the potential to increase the efficiency and productivity of drilling operations significantly and to boost profitability by decreasing the time until wells start the extraction. Through our interviews, and through analysis in subsequent models, it is clear that suppliers, and the timely delivery of supplies, plays a critical role in the successful implementation of large-scale projects. In the context of oil and gas projects, our focus is on the suppliers that provide customized materials. While the bulk of this dissertation focuses on projects from the project planner's point of view, we were also motivated to consider these problems from the perspective of the supplier, and hence, to consider scheduling models with due dates. We present a stylized model, where we consider sequencing decisions on a single processor, here representing a supplier, in an online setting where no data about the future incoming opportunities is available. With the goal of minimizing total weighted (modified) earliness and tardiness cost, we introduce a new scheduling policy, which we refer to as the list-based delayed shortest processing time policy, and develop lower and upper bounds on the performance of this policy. Finally, we consider an alternative view of managing construction in projects, a location-based method known as the Work Density Method for takt planning. Given a work space and the number of zones in which to divide that space, the so-called WoLZo problem is to identify the shape and dimensions of each zone while minimizing the peak in the trades' workloads per zone. We model this problem and develop an optimization algorithm to divide a work space into zones while leveling work densities across trades in a process. The tools presented in this dissertation are useful for managing different elements of mega-projects and significantly advance the state-of-the-art in those areas. We confirm the effectiveness of these tools by analyzing their performance compared to current practice in real-world case studies as well as their performance over the benchmark test problems that are available in the literature.