Estimation Of Distribution Algorithms For Resource Constrained Project Scheduling Problems

Resource-constrained scheduling problems(RCPSPs) are an important branch of scheduling problems, whose objective is to minimize the makespan of projects over reasonable usage of resources and scheduling of activities. RCPSPs have a wide engineering background and many algorithms have been proposed. Due to the complexity and diversity of this problem, most existing algorithms are heuristic ones. Estimation of distribution algorithm(EDA) is an important branch of evolutionary computation. This class of algorithms combines traditional genetic algorithms with statistical learning and builds probabilistic model to describe the distribution of solution space, which is an efficient scheme for multi-variable related complex optimization problems. This thesis focuses on applying EDAs to RCPSPs, and the main work can be summarized as follows:(1) The characteristics of RCPSPs are first studied. A new methodology is proposed to analyze the structure of configuration spaces of RCPSPs. Up to now, although many algorithms have been proposed for RCPSPs, little has been done on theoretically analyzing the properties of the problem itself. Generally, there are three decoding methods for RCPSPs, namely forward decoding, backward decoding and hybrid decoding. These three decodings are used to construct local optima networks of RCPSPs and different network properties are analyzed. In RCPSP LONs, nodes represent local optima and edges represent transition probability between local optima. Our analysis shows that LONs fall into three types, and the hybrid decoding can construct LONs with the best performance.(2) Next, based on the above analysis, an estimation of distribution algorithm with loosing constraint local search for RCPSPs(EDALCS-RCPSP) is proposed. In this algorithm, an individual is a sequence of activities subject to precedence constraints and elite individuals are selected to renew the probabilistic model. The algorithm uses the traditional forward-backward iteration(FBI) as local search scheme and besides, a new local search operator, namely loosing constraint search(LCS) is designed to improve the searching ability of the algorithm. Computational experiments are conducted on the standard data sets of project instances. The performance of EDALCS-RCPSP ise compared with an existing EDA for RCPSPs. The results reveal the feasibility and effectiveness of our algorithm.(3) Last, a new model of RCPSPs is proposed, namely RCPSPs with time windows(RCPSPs-TW). First, a sparse base schedule is generated. By adding a time window to each activity in the base schedule, the time window constraint is presented. When solving this problem, an activity must be executed within the given time window, which is closer to the practical situations. A new decoding method called sparse decoding(SD) is proposed for this problem. An EDA is proposed for solving RCPSPs-TW. Computational experiments are conducted on the standard dataset, namely Patterson, J30, J60, J90, and J120. The results show that from a certain perspective, the difficulty for solving this problem is related to the width of time windows.