Algorithm Design For Multi-objective Flexible Job Shop Scheduling Problems

Scheduling problem has a long research history and can be classified into many varieties such as flow-shop scheduling problem and job shop scheduling problem and so on. Meanwhile, job shop scheduling problem (JSP) is a kind of resource allocating problem satisfying task configuration and sequence restriction. And JSP is one of the most complex combinational optimization problems. Flexible job shop scheduling problem (FJSP) is the extension of the classical job shop scheduling problem and it is more realistic and complicated than JSP. Such a scheduling problem can be described as follows, there are a set of jobs to be processed on a set of machines. Each job consists of a number of operations and each operation can be operated on one of available machines for a fixed time continuously. Each operation can only be processed on one machine at one time, and each machine can process at most one operation at one time. The objective is to find a solution with minimal makespan, minimal cost, minimal storage, maximum utilization of machines, etc.Makespan, total earliness and total tardiness are three objectives to be optimized in this paper. The focus of our work is to model, analyze and resolve the FJSP with single resource. Meanwhile, there are many properties and characteristics of the system, which can be studied and analyzed by merging the shared resources system.Scheduling problem is a NP problem, and finding the optimal solution to this problem is the difficulty of the reaearch work. Therefore, a better solution is required instead of optimal solution. Timed Petri net is used to model the scheduling problem in this paper. At the same time, the obtained model is researched to analysize deadlock and resource competition in this paper. And then improved genetic algorithm is used to resolve the problem based on the Petri net model.In this research work, the firing sequence of transitions stands for a chromosome, and genetic operation such as crossover and mutation are all based on the elements of the timed Petri net model, which are independent of space elements and hence avoid explosion of state space. Our method is applied to every FJSP that can be modeled by timed Petri net, which improved the universal usage of algorithm. Meanwhile, an approach based cost is proposed to resolve multi-objective scheduling problems. The objectives to be optimized are transformed to total cost, which can evaluate the solution more visually and reflect the desire of enterprise. Further, we used both general genetic algorithm and self adaptable genetic algorithm to simulate realistic problem.Simulation experiments of scheduling problem theory result are taken to prove that this thesis can solve FJSP effectively by making use of its advantages and avoiding its disadvantages.