Multi-mode resource-constrained project scheduling problem with alternative project structures

This paper proposes to consider alternative project structures when dealing with the multi-mode resource-constrained project scheduling problem. An AND-OR network is used to present this alternative project structures innovatively. The problem is formulated as a bi-objective linear integer program, which minimizes the makespan and total cost. A hybrid metaheuristic is developed based on AND-OR network to solve this NP-hard problem efficiently, which nests adapted Tabu Search (outer layer) and NSGA-II algorithm (inner layer). A large amount of computational experiments of different sizes are conducted, and compared with solutions generated by CPLEX, traditional Tabu Search, enumeration-based method and single-layer NSGA-II. The experimental results show the advantages of the proposed model and method, especially with large-size problems.