Solving Two Types Of Complex Job Shop Scheduling Problems Based On Genetic Algorithm

With the coming forth of the global economy integration and knowledge economy, the competition among enterprises will be more fierce. In order to increase their core capacity of competition, enterprises must improve their inner management of production and operation While the job shop scheduling is the core of production management . Therefore, the research on the job shop scheduling has not only tremendous academic value, but also has great practical meaning.The dramatic characteristic of the job shop scheduling problem is its complexity. Flexible Job Shop Scheduling Problem (FJSSP) and Uncertain Job Shop Scheduling Problem (UJSSP) are more complicated than general job shop scheduling problems: the routes and machines are optional for the jobs in the FJSSP; UJSSP have uncertain processing times and due date windows. Because there is much difficulty in processing in these two types of job shop scheduling, few optional algorithms are available. The genetic algorithm (GA), as a global random searching method which is characterized by generality, implicit parallelism and global searching, has been successfully applied in the field of machine-learning, pattern recognition, image processing and combinatorial optimization. the two complicated job shop scheduling problems above are solved by GA in this paper. The main work is as follows:(1) The self-adaptive genetic algorithm is used to solve a type of the FJSSP and the effectiveness of the algorithm is demonstrated through simulating experiments. Aimed at the particularity of the model (machines are optional), meanwhile considering the processing time, the time that first allows the job to be processed and the leisure time of the machines the paper chooses corresponding machines in decoding chromosomes. The simulating experiments demonstrate that the proposed scheduling algorithm can get better solutions in solving FJSSP, based on the application of self-adaptive genetic algorithm to the solving of the model.(2) Research is done on UJSSP which has uncertain processing times and due date windows. For enterprises, research on UJSSP has more practical meaning and also good for applying the outcome of the research to the actual job shop scheduling problems. The Job Shop scheduling problems with uncertain processing times and due date windows are addressed in this paper. In this paper, interval numbers symbolize uncertain process times and the optimum objective is to minimize the weighted sum of penalty possibility for jobs due to earliness or tardiness. A genetic algorithm based on king-crossover strategy is developed to find the optimal scheduling sequence. The effectiveness of the algorithm is demonstrated through simulating experiments.