New definitions and algorithms in scheduling resource-constrained projects

Abstract

The use of float and critical path are central in analyzing activity networks in project management. However, the variability in the schedules for resource-constrained projects make it difficult to calculate float and identify critical activities accurately. In the first part of the thesis, a new definition for float is proposed for projects with resource limits. With the new definition, it is possible for us to calculate float and identify critical activity without referring to a specified schedule. Several algorithms are developed to calculate the maximum float. Extensive experiments are conducted to show that there are abundance of activities and activity sets with positive float and group float even the deadline of the project is already optimal. In the second part of the thesis, we develop an new optimization technique to solve the resource-constrained project scheduling problem (RCPSP). We based on the fact that the highly ordered structures of crystals are achieved by simultaneous movement of molecules with decreasing temperature. Simulating the process of cooling a gas into crystal, a new optimization method, Molecule Search (MS), is proposed here to tackle the RCPSP. The experimental results on the PSPLIB (standard benchmark for RCPSP) also show that MS is one of the best heuristics for RCPSP so far. In the third part of the thesis, we further develop a population based Molecule Search algorithm (Molecule Bank Algorithm) for RCPSP. Compared with all the state-of-art heuristics, MBA emerges to be one of the best heuristics so far, achieving the best results on the J60 and J120 test sets of PSPLIB. Moreover, 3 new best results for the J60 test set and 62 new best results for the J120 test sets are updated by MBA. In the fourth part of the thesis, We study an over-constrained resource-constrained project scheduling problem where constraints cannot be relaxed. This problem originates from a local defense agency where activities to be scheduled are strongly ranked in a priority scheme determined by planners ahead of time and operational real-time demands require solutions to be available almost immediately. A two-level hybrid framework is proposed to tackle this problem. Real-data used to test the algorithm show that a larger number of high priority activities are scheduled when compared to an old CP-based system. Further tests were performed using randomly-generated data and results compared with CPLEX.