The Research And Application On Job Shop Scheduling Problem Based On GA

Computer Integrated Manufacturing System (CIMS) can greatly promote the synthesized economic profit of the enterprise when it is implemented widely in manufacturing fields, thus it has become the hotspot of research and implement in all kinds of enterprises. Management Automation System, one sub-system of CIMS, is an important part of modern manufacturing factory whose kernel technologies are CAPP, Job Shop Scheduling Problem (JSSP), etc, which are vital and indispensable. As a one part of enterprise produce system, JSPP affects it so much. So JSSP stirs many scholars' research. JSSP characters as its complicated model construct and calculation, dynamic multi-restriction, and multi-objective. It is assemble optimization problem and has been proved as NP-hard problem. Many intelligent computation methods such as simulated Anneal Algorithm, Genetic Algorithm, heuristic algorithm, are introduced into scheduling problem in recent years.As a method in evolutive computer field, GA is applied widely in parameter optimization such as global search. When it's applied in JSSP, there are several distinct merits compared with othter methods. As an uncertain stochastic optimal algorithm, GA is applied in all kinds of fields in the past 20 years. And because of its independence, global optimization, and implicit parallelism in complex problem solving, GA is developed and applied in many fields by more and more people.In this paper, GA is applied to solve complicated shop floor scheduling problem. The paper is divided into seven chapters. In the introduction, it states the significance, recent actuality and research methods of job shop scheduling problem. Then the succedent five chapters include the presentation of GA, the typical descriptions of job shop, flow shop, machine scheduling earliness-tardiness and virtual scheduling and its research strategy. The performance is compared when using different GA coding mode. The simulation scheduling results of several samples show GA's feasibility, reliability and validity in solving JSSP problems. The last chapter is conclusion and expectation and prospect of the research subject.In this paper, I have made some research and innovative achievement in the following aspects:(1) In order to overcome the weakness of premature convergence and the disadvantage of local seardhing ability appearing in GA, an improved genetic algorithm which combining with Heuristic algorithm is proposed and applied in the flow shop scheduling problem.(2) For the hybrid flow shop scheduling problem, a solution method based on GA is proposed. The encoding method of chromosome and the corresponding operators are given. The encoding method greatly simplifies the operations in GA.(3)Since there are many uncertain factors consisting in the real product schedulingproblem, the fuzzy flow shop is discussed. The hybrid GA combining neighbor search is simulated, and the results is compared with the results got by other algorithms.(4)The machine scheduling problem with earliness-tardiness penalties is described. Identical parallel machine scheduling problem is solved by separating it into two sub-problems for the complexity, then a solution based on GA is proposed.(5)The paper researches briefly into the virtual job shop scheduling system, and designs a scheduling model based on principle of loop- adjustable system. This system can make the whole production system working as a dynamic enterprise producing system with good performance. And then design a scheduling algorithm with GA. The computer simulative datum show the validity of GA applied in the system.