Research On Intelligent Algorithm For Fuzzy Shop Scheduling Problems

It’s very important for shortening the production cycle, controlling inventory of the products which are being producing in the plant, enhancing the satisfaction of product due date and raising the productivity of enterprise by contriving a production scheduling scheme scientifically. It has important theoretical and practical significance for achieving the modernization of advanced manufacturing enterprises by researching on effective scheduling methods and optimization techniques. The traditional optimization methods are difficult to solve the scheduling problems for the complexity, so soft computing method becomes an effective way to.solve such problems, it is currently a hot topic in international research and many valuable new scheduling algorithm was put forward.Most researches about production scheduling are based on deterministic scheduling models, but there are many uncertain factors in actual production process. If the scheduling model ignores these uncertainties, the practical application value of scheduling scheme will be greatly reduced. The fuzzy theory can more accurately describe the uncertain events of production process, optimizing fuzzy scheduling scheme can improve the efficiency of actual production, and can greatly reduce the maladjustment probability between production plan and scheduling. This thesis studies the job shop scheduling problem, which is the most basic and important production scheduling problem, and uses fuzzy theory to deal with uncertainty. Some important factors such as machine availability constraint, flexible and multi-objective are introduced into fuzzy job shop to form more complex and integrative scheduling problems, this study deals with these problems and proposes some solving methods based on evolutionary computation.This thesis presents a random key genetic algorithm (RKGA) for the fuzzy job shop scheduling problem with resumable jobs and preventive maintenance. RKGA uses a random key representation, a new decoding strategy incorporating maintenance operation, binary tournament selection, discrete crossover and swap mutation are applied to evolve population. In RKGA, a chromosome is expressed as a real string and can be directly converted into an orderly operation-based representation, and it’s very easy to implement algorithm. Computational results show the optimization ability of RKGA.This study investigates the job shop scheduling problems with both flexible process plan and fuzzy processing conditions, and proposes an efficient co-evolutionary genetic algorithm (CGA) to simultaneously evolve the two sub-problems:machine assignment problem and operation sequence problem, so as to minimize the maximum fuzzy completion time. CGA uses a two-string representation with a real string and an integer string, a new decoding strategy and a co-evolutionary technique applied to chromosome. In each generation, both the evolution of only one string for some individuals and the evolution of two strings for other individuals occur, as a result, CGA maintains good balance between exploration and exploitation.This thesis researchs fuzzy job shop scheduling problems and proposes an efficient swarm-based neighbourhood search (SNS) to minimize the fuzzy makespan, proposes an orderly operation-based representation and a neighbourhood search operator based on swap. SNS evolves swarm using binary tournament selection and swap operation in which probability is1. SNS has simple structure and is very easy to implement. SNS has strong global and local optimization capabilities, as well as faster convergence speed.This study considers fuzzy flexible job scheduling problems with makespan and maximum machine workload and proposes a multi-objective swarm-based neighborhood search (MOSNS). In MOSNS, ordered operation-based doublet string and three-dimension array are used to indicate the solution of operation sequence sub-problem and machine assignment sub-problem, three neighbourhood search operators (two swaps and an insertion) are applied to produce new solutions, simple weighted-objective based methods are used to update swarm and external archive to obtain a set of non-dominated solutions. MOSNS possesses strong global and local optimization abilities.This study designs an effective artificial bee colony (ABC) algorithm to solve fuzzy job shop scheduling problem, and proposes a neighbourhood structure based on insertion operator. In ABC, binary tournament selection is applied to selection solution for each onlooker bee, and neighborhood search is used to produce new solutions for employed bees and onlooker bees respectively. The employed bee phase and the onlooker bee phase execute sequentially in each cycle, and the worst food source is replaced with the elite solution every certain cycles. And then this study addresses fuzzy job shop scheduling problem with flexible preventive maintenance, and proposes a multi-objective artificial bee colony (MOABC) to minimize fuzzy makespan and another new objective called fuzzy total tardiness index. Weighted objective-based method is used to choose a solution for each onlooker bee, and neighborhood search based on swap operator is used to produce new solutions for employed bees and onlooker bees respectively. The food source with the biggest weighted objective value is replaced with the solution with the smallest weighted objective value every certain cycles. Compared with general multi-objective optimization algorithms, MOABC has lower computational complexity. MOABC is tested and compared with the methods from literature and computational results show that MOABC can provide promising solutions and scheduling strategies.