Resource Investment Project Scheduling Algorithms Based On Variable Neighborhood Search And Floor-planning

In today's rapid development of science and technology, project scheduling problems have gained increasing attentions. Resource Investment Project Scheduling Problems(RIPSPs) is an important expansion of project scheduling problems. It removes the limit of the given amount of resources exist in Resource-Constraint Project Scheduling Problems(RCPSPs). So RIPSPs can be summarized as follows. A project contains multiple activities, there may exist some preference constraint relationships between activities. At the same time, each activity's execution needs a certain time and several kinds of resources. Our task is to arrange each activity reasonably in the case of satisfying preference constraint relationships, making the project obtains the shortest makespan as well as minimizing the available resource capacity. In this thesis, we use different methods, namely variable neighborhood search(VNS) and floorplanning, to study the single mode RIPSPs. The main work is summarized as follows.(1) Apply the VNS to solve RIPSPs. In this method, shaking and neighborhood search operators are used. First a solution is made up of an activity list and a capacity list. In an activity list, all activities satisfy preference constraint relationships and a capacity list contains all amount of resources for each kind of resource. The algorithm starts at an initial solution, using the shaking and neighborhood search operators to search the optimum solutions. The algorithm stops when the optimum solution is found or reaching the stopping criterion. In the experiments, 450 problem instances are used to test the performance of our proposed algorithm. And the experimental results show that VNS are suitable for solving small-scale problems.(2) Based on our first work, MAEA is further integrated with VNS to form a new algorithm. Selection, crossover, mutation and competition operators are designed. In addition, for the best agent in current generation, we apply the self-learning and the VNS operator with the probability of 1/2 to further enlarge the search space. The experimental results show that our proposed algorithm has a good performance.(3) In the third work, we integrate the MBS in floorplanning with MAEA to solve RIPSPs. First of all, each activity in a project is regarded as a hard rectangular block of MBS, in which the width of the block stands for the duration of the activity and the height is maximum resource among all kinds of resources. Then each block has four initial positions and each position corresponds to a way of moving. All blocks must be moved in the first quadrant. Each two blocks need to satisfy preference constraint relationships and can not overlap. Two-point crossover operator, directional mutation, competition and self-learning operator are used to search the optimum solutions. The results show our algorithm has a good performance.