Research On Inverse Scheduling Methods Based On Hybrid Genetic Algorithm

In order to adapt to the production mode with low volume-high variety, a method "Inverse Scheduling Problem"(ISP) based on the inverse optimization theory has been proposed by past researchers. The goal is that the exact values of parameters (e.g. processing times, due dates) are controllable and a feasible job sequence is given but not optimal and pre-specified job sequence (s) become optimal through adjusting processing parameters for a target. At present, the research about ISP has just begun, most of the works that they studied were short of mathematical models, solving tactics and methods. In this research, aiming at single-machine and flow-shop scheduling, four types of inverse scheduling problem are systematically studied, such as single-machine ISP, single-machine ISP with due date, flow-shop inverse scheduling and multi-objective flow-shop inverse scheduling. The mathematical models of ISPs have been proposed. Furthermore, according to these models, we have been developed the effective solving methods.Based on the single-machine scheduling problem, the mathematical model of single-machine ISP with the weighted completion time has been proposed. A hybrid genetic algorithm based on PSO (Particle Swarm Optimization, PSO) has been developed to solve this problem. In this algorithm, to improve the diversity and quality of the individuals, a double scheduling method which combines heuristic non-optimal scheduling method with random initial population and local initial population has been designed to construct initial population. According to the problem characteristics, three kinds of crossover operators and two kinds of mutation operators has been designed. The hybrid algorithm uses the improved PSO to improve the local search ability of the algorithm. Experimental studies and comparisons have been conducted. The experimental results show that the proposed method has a higher solution efficiency and better stability.Aiming at the single-machine scheduling problem with due dates, a hybrid algorithm based on variable neighborhood search have been proposed by using the embedded structure. It can balance the algorithm of global search and local search. Based on the features of problem and encoding, we have been put forward four neighborhood structures to improve the local search ability by changing the neighborhood structure. Finally, a lot of instances have been conducted and results have been compared with existing methods. The experimental results show that the proposed method can solve the single-machine inverse scheduling problem with due dates effectively.Based on the flow-shop inverse scheduling problem, a mathematical model which considers minimizing the adjustment of processing time has been proposed. Then, an adaptive hybrid algorithm (GAVA) which combines improved GA with an adaptive VNS is proposed. In this approach, a new decimal system encoding method is proposed to present the solution, which realizes coordinative optimization of operator and parameter. Furthermore, four neighborhood structures have been designed based on the feature of problem. To improve the local search ability of the approach, an adaptive selection mechanism is developed to select the best neighborhood. Finally, a lot of instances have been conducted and results have been compared with existing methods. The results show that GAVA algorithm outperforms other algorithms.In this part, we have been built the model of multi-objective ISP which considers scheduling efficiency and system stability. The adjustment of processing parameters, the changing of system and the weighted completion time are considered in this model. A LMONG (Multi-Objective NSGAII and GA with Local search:LMONG) algorithm has been proposed to solve this problem. In order to improve the performance of algorithm, the multiple strategies have been mixed, including rapid non-dominated sorting method, two kinds of diversity strategy, hybrid elitism strategy and efficient local search strategy. Finally, public problem instances and ANOVA analysis are provided for the proposed algorithm. The results demonstrate the effectiveness of the algorithm.Based on the aforementioned research results, the method proposed by this dissertation has been conducted in the multi-objective ISP problem from a real Chinese shipyard. We analysis the existing problems according to the actual conditions of the work-shop. The example analysis shows that the proposed algorithm can solve production scheduling effectively. The workshop system can run effectively and smoothly.Finally, this dissertation summarizes the research results and proposes its future research interest.