Research Of Some Scheduling Problems Based On Hybrid Evolutionary Algorithm

Scheduling plays a key role for production efficiency. Scheduling problems have a lot ofpratical prototypes and of high value. Most scheduling problems are classical NP-hardproblems. The main structural model of manufacturing industries of our country is themake-to-order manual operation system, which is difficult to study because of its strongrandomization, high flexibility and resource-constrained property. Scheduling problems arestudied by many researchers, and meta-heuristic methods are the most widely used methods,among which hybrid optimization method is a hot research trend.This research is supported by National Nature Science Foundation of China andGuangdong Nature Science Foundation. By analyzing the state-of-the-art scheduling methods,this thesis makes theoretical analysis and algorithm research on some scheduling problems.The research contents and contributions are listed as follows:1. The risk assessment of priority rule failure with random processing time is analyzed.Priority rule is often combined with other methods in production practices. But seldom workanalyzed the failure possibility of priority rule with randomness. Empirical analysis showsthat the working time obeys exponential distribution. Base on this assumption, this thesisanalyzes the failure rate of priority rule based on working time, and gives the analyticalsolution and the sensitivity of the failure rate for two and three jobs using probabilitystatistics methods. Numerical solutions for more than three jobs are given by mathematicalstatistics methods. This thesis complements this part of theoretical research and has certainpractical value.2. A hybrid genetic algorithm combined with particle swarm optimization for produtionscheduling problem is proposed. Genetic algorithm is the most widely used meta-heuristicsfor job-shop scheduling problems. But the effectiveness of regular genetic algorithm isrestricted by the randomness of initial population. In this thesis, particle swarm optimization(PSO) algorithm is incorporated for its low time and space demand, convenient operation andefficient information sharing mechanism. PSO is adapted to provide the major evolutiondirections for genetic algorithm, and it reduces the relative deviation during iterations. Andtime and space complexity of the algorithm is analyzed. Corresponding encoding schemes forthe permutation flow-shop scheduling problem and job-shop scheduling problem areproposed, and the efficiency of the proposed method is validated on the benchmark datasets.3. A hybrid chaotic paticle swarm optimization combined with genetic algorithm for flexible job-shop scheduling problem is presented. At first, this paper analyzes theshortcoming of a Kacem dispating rule, which is a general priority rule. After that, animproved Kacem rule, which takes the load of machine and the order constraint of processinto consideration, is proposed. A hybrid genetic algorithm, which takes advantage of theframe of genetic algorithm with two layers of encoding mechanism and chaotic particleswarm optimization, is proposed. The efficiency of the algorithm is validated by thecomparison with other methods on Brandimarte datasets.4. The model and algorithm for manual system scheduling problem is presented.Because of high flexiblility, uncertainty and obvious learning effect, manual systemscheduling problem is difficult to study and seldom work has been done. This thesis buildsthe model of manual job-shop scheduling problem through analyzing the difference betweenflexible job-shop scheduling and manual system scheduling problems. In order to reduce thescale of the problem, the model groups the workers, classifies the processes and expands thelearning effect. By updating the working time matrix and providing effective heuristicinformation, the algorithm for manual system flexible scheduling problem with learningeffect is achieved. The efficiency of the algorithm is validated by experiments onBrandimarte datasets, with different number of categories and learning rates.5. An evolutionary scatter search algorithm combined with improvedelectromagnetism-like meta-heuristics for the resource-constrained project schedulingproblem is proposed. Analyzing the problems met in the process of scatter search maintainingtwo-tier structure, this paper proposes an improvement of the update policy of the referenceset of scatter search. This improvement expands the scatter search and enhances therobustness of the algorithm. Because some excellent solutions can not to be used evenly dueto distance constraint, this thesis proposes the concept of effective reference count. With thisstrategy, the excellent solutions can be utilized evenly, while the excellence and diversity ofthe solution are preserved. After that, electromagnetism-like meta-heuristics is embedded inthe crossover operator of scatter search. By improving the calculation of the electromagneticforce, the optimization range of the crossover operator is expanded and the search of thesolution space is extended. The efficiency of the algorithm for the resource-constrainedproject scheduling problem is validated by the experiment on PSPLIB datasets. Incomparision with the latest meta-heuristic algorithms, the proposed algorithm is competitive.