Algorithms for optimal project scheduling

Abstract

Project scheduling plays a vital role in project management, and constitutesone of the most important directions in both research and practice in theOperational Research (OR) field. During the last decades, the Resource-Constrained Project Scheduling Problem (RCPSP) has become the mostchallenging standard problem of project scheduling in the OR literature. TheRCPSP involves the construction of a precedence and resource feasible timeschedule which identifies the starting and completion times of activities, undera specific objective. Several variations of the RCPSP exist that representdifferent practical problems with different objectives, resource types, morethan one way (mode) to execute an activity, generalised precedence relationsfor activities, etc. The RCPSP and its variants belong to the class of stronglyNP-hard problems and a number of solution methods, both exact andapproximate have been proposed in the literature.Scheduling is also a critical issue in process operations. The processscheduling problem consists of determining the most efficient way to producea set of products in a time horizon given a set of processing recipes andlimited resources. The activities to be scheduled usually take place inmultiproduct and multipurpose plants, in which a wide variety of differentproducts can be manufactured via the same recipe or different recipes bysharing limited resources, such as equipment, material, time, and utilities.The common problem features, such as required resource types, precedencerelations and initial/target inventories, suggest that exchanging solutiontechniques between the two research fields is both possible and useful.The process scheduling industry is driven by the substantial advances ofrelated modelling and solution techniques, as well as the rapidly growingcomputational power. On the other hand, project scheduling research efforthas mostly focused on developing approximate solution techniques. However, recent project scheduling research papers show a renewed interest formathematical programming-based solution strategies. Moreover, the bestlower bounds ever found on broadly-studied RCPSP test instances, wereobtained by a hybrid method involving constraint propagation and a MILPformulation. Additionally, mathematical programming solvers are often theonly software available to industrial practitioners. Therefore, the study ofexact methods, and especially mathematical programming techniques forsolving the RCPSP is of particular theoretical and practical interest. The mainobjective of this work is to develop new optimal project scheduling techniquesinspired by the process scheduling literature.This thesis consists of a literature review and state-of-the-art, three chapterswith novel mathematical programming solution methods for the RCPSP and itsvariants under the objective of minimising the makespan and finally someconcluding remarks. The first part presents new mixed-integer linearprogramming models for the deterministic single- and multi-mode RCPSP withrenewable and non-renewable resources. The modelling approach relies onthe Resource-Task Network (RTN) representation, a network representationtechnique used in process scheduling problems, based on continuous timemodels. Next, two new binary integer programming discrete-time models andtwo novel precedence-based mixed integer continuous-time formulations aredeveloped. These four novel mathematical formulations are compared withfour state-of-the-art models from the open literature using a total number of2760 well-known open-accessed benchmark problem instances. Thecomputational comparison demonstrates that the proposed mathematicalformulations feature the best overall performance. Finally, a new precedencebasedcontinuous-time formulation is proposed for a challenging extension ofthe standard single-mode resource-constrained project scheduling problemthat also considers minimum and maximum time lags (RCPSP/max). The newformulation is then used to conduct an extensive computational study on atotal of 2,250 benchmark problems, which illustrates its efficient performance.