Research On Job-shop Scheduling Algorithm Based On Methods

The Production Scheduling Problem is very important in the domain of manufacturing execution system. This paper studies the job-shop scheduling problem by using computer-aided management. Job-Shop Scheduling Algorithm is one of the important issues of scheduling theory, which can not only promote the study of scheduling theory, but also realize the dynamic adjustment in the production plans of enterprise. Job-shop Scheduling Problem (JSSP) is one kind of combinatorial optimum problems with time, sequence and resource constraints. It has been proved theoretically that JSSP is a NP-hard, and it is impossible to find the global optimum result for it in polynomial complexity. Nonstandard Job-shop Scheduling Problem (NJSSP), which slacks the resource constraint, and gets larger search space and solves broader practical scheduling problems. The fact that it is impossible to find the global optimum in polynomial complexity has been proved.In this paper, through the analysis and study of Job-Shop Scheduling Problem and Nonstandard Job-Shop Scheduling Problem, Job-Shop Scheduling Algorithm Based on Efficiency Function and Nonstandard Job-Shop Scheduling Efficiency Algorithm is designed for Job-Shop scheduling problem to minimize total flowtime. This algorithm adapts the engineering practice. The experimental results show that they can find the better solution in polynomial complexity, but they are the better in average relative percentage deviation (ARPD), standard deviation(STD), number of optimum solutions obtained for a given size of problems(OPT). The main idea of this paper is described as follows.First, the author introduces the studying level of Scheduling Problem and the advantage of Job-Shop Scheduling Algorithm Based on Efficiency Function (JSSABF) and Nonstandard Job-Shop Scheduling Efficiency Algorithm (NJSSEA) in both efficiency and effectiveness. Then, the detailed description of JSSABF and NJSSEA are presented, including the description of JSSP and NJSSP, cost function, detailed steps of the algorithm and the instance of scheduling. In order to improve the adjusting efficiency, this paper puts forward a new way of shifting after swapping job.Finally, the Job-shop scheduling results are very satisfactory in the project, through analyzing and practical verifying.