Research On Job Shop Scheduling Problem Based On Critical Path Method

As the global economic integration and knowledge economy coming, the competition between enterprises is becoming increasingly fierce. If an enterprise does not have strong competitiveness, it would be very difficult to have the living space in the society market. For processing and manufacturing industries concerned, in the shortest possible time produce customer satisfaction products at the lowest cost, is undoubtedly powerful means to enterprise increase competitiveness. Therefore, how to use limited resources, reduce production cost, shorten the production period, guarantee on-time delivery, enhances the enterprise prestige, win more customers, is one of the important conditions for manufacturing survive in the competition. Effectivly use of the present resources, work out a reasonable production plans between enterprise and workshop, in order to achieve workshop production efficiency and reliability will be the key in the enterprise production.Through the analysis of the job scheduling problems, and combined the technology of the graph theory, presented based on graph shop scheduling model (G-JSHOP). For the complexity of the job shop scheduling, converting the job shop scheduling(JSS) problem into solving the critical path, that is, using the critical path method(CPM) to solve job shop scheduling problem.Combining the critical path technology with genetic algorithm to solve job shop scheduling problem.When establishing the plan of workshop scheduling, each workpiece of processing of the process line, the processing time and processing costs are known, but, every machine processing of workpiece order can be adjusted, and this processing order plays the role of decision-making. This paper is from the decision-making route began, combining with genetic algorithm, convert each route into decision matrix, and each decision matrix is a an individual of the population. Because every machine internal processing the number of the workpieces and procedures is fixed, only allowed machines internal process adjustment, that is, only make the most workpieces(k) of all the machines as a Genome. Using the selected operator, k-bits Genome crossover and mutation operator technologies to produce the next generation, finally after the evolution of several generations, obtained an optimal solution.This paper applies critical path technology to the production management of the mould. Firstly, it introduces the JSS of the mould production management. Secondly, it analysis the functional fabric of the JSS and its characteristics. Finally, it analysis the workshop-level production planning and plant-level production planning, in the while, these two plans was combined to constitute JSS with two-level scheduling, and combines this plan with critical path method to solve the scheduling problem of the production of the mould. By analyzing the test, this algorithm reduces the overall processing time of mould.