Multi-objective Evolutionary Algorithms For Dynamic Resource Investment Project Scheduling Problems

In our daily life, scheduling problems can be seen everywhere. For example, the vehicle scheduling at the crossing, the production schedule in the factory, the thread scheduling of operating system, and so on. The project scheduling is the process that we reasonably arrange all activities of the project concerning time and resource constraints. The traditional project scheduling problems mainly study under certain environment, but during the actual project uncertain prevails, for example due to environment change, resources can not arrive on time lead to the execution of some activities lengthen.In this thesis, we expand the scope of existing project scheduling problems from a single objective optimization to the multi-objective and from deterministic environment to uncertain environment. Next we will introduce our research model, the research environment as well as the experimental results. There are three achievements about resource investment project scheduling problems in this thesis, and the three parts is studied step by step in-depth. First of all, we use the differential evolution algorithm with local search to solve resource investment project scheduling problems; and then a multi-objective evolutionary algorithm for resource investment project scheduling problems with duration perturbation is proposed; finally we propose a new surrogate model to study solution robustness of resource investment project scheduling problems. The main work can be summarized as follows:(1)We combine the differential evolution algorithm with a local search operator to resolve the resource investment project scheduling problems, which is labeled as DELS-RIPSP. Here we do not permit project tardiness in the process of optimization. DELS-RIPSP can improve the population quality changing existing chromosomes to those that have better fitness by using the local search operator for reducing resource cost. The performance of DELS-RIPSP is validated on 450 benchmark problems, including Mohring and Pro Gen instances which have 10, 14 and 20 non-dummy activities. The percentages of optimal solutions for all benchmark problems are reported. The results illustrate the effectiveness of DELS-RIPSP and the potential for solving large-scale RIPSPs.(2)We propose a new multi-objective optimization model to study resource investment project scheduling problems with perturbation on activity durations(DP-RIPSPs), where perturbation is modeled via a set of scenarios. We propose an improved non-dominated sorting genetic algorithm II to solve DP-RIPSPs, which is based on standard non-dominated sorting genetic algorithm II and a local search operator. The algorithm is labeled as NSGAM-II. NSGAM-II improves the speed to find optimal solutions by changing existing chromosomes to those with better fitness using advanced strategies. The performance of NSGAM-II is validated on 1152 benchmark problems, including Pro Gen instances with 30, 60 and 120 non-dummy activities. The experimental results illustrate the effectiveness of NSGAM-II and its potential for solving DP-RIPSPs.(3)Usually, study solution robustness of resource investment project scheduling problems in uncertain environment need to do lots of scenario modeling. However, the scenario modeling method is expensive in time and memory. In this thesis, we employ surrogate models of robustness to study solution robustness of RIPSPs and propose a new surrogate model of robustness, labeled as SMnew, which is simple and effective to study solution robustness based on free slack and resource redundant. The performance comparison between SMnew and the existing surrogate model SM are validated on 288 benchmark problems, including 30, 60 and 120 non-dummy activities. The experimental results illustrate the effectiveness of SMnew and its potential for studying solution robustness of RIPSPs.