The resource-constrained project scheduling problem (RCPSP) as its significations in the reality and theory fields is always an important issue in the scheduling field. There have been many algorithms provided, most of them pay more attention in designing different structure and applying different mathematic skills, there was rarely research which designed algorithm directly by the essentials of the scheduling process. As for this situation, this paper studies the searching process and search space in detail and gets the following results: (1) The main fields of algorithm designing and the main task of these fields are clarified. Constructing schedules phase and strolling in search space phase are regard as the main two phase for algorithm designing. In the constructing schedules phase, the main task of an algorithm will be finding the best procedure by ordering the constructing components, and in the search space strolling phase, the main task of an algorithm will be finding the most potential direction in which a better schedule can be found. (2) A new representation of solution for RCPSP and the distance between two solutions in the new search space are given. This new representation describes the linking relation between arbitrary activities pair, and it can be use in any generation scheme. It can be said that the new representation keeps the schedule property in high level. (3) A reverse problem which extends the ideal of forward-backward schedule is given. It keeps all the resource constraints of the original problem and includes the reverse linking relations as the original problem. All the operations applied in original problem are taken in the same style in reverse problem. When needed, a reverse scheduling for the population in one direction is used to update the population in the other direction. (4) Scatter search algorithm is designed. After analyzing the affections of the factors in the scatter search, improving methods are given. A hybrid genetic algorithm and an evolutional algorithm are given. The simulation results for the instances in the standard library show that these two algorithms all can resolve the large-sized problems and have reached high level in finding optimal solutions in generating less number of solutions. (5) Based on the new representation, decomposition algorithm for search space is given. The algorithms with one time and multi-times decomposition for the search space are given, and the simulation results are given. (6) Quantum-inspired evolutionary algorithm which uses the two values property of the new representation is given. The general structure of quantum-inspired evolutionary algorithm and the improving methods are given also. The algorithms which use one quantum solution and two quantum solutions respectively are given. The simulation results show that the ideals of this paper are correct and the algorithms given by this paper are effective.
修改评论