Research On Model And Algorithm For Job Shop Scheduling Problem With Deteriorating Time

With the continuous progress of science and technology and rapid development of the productivity, consumer demand become more and more diversified and personalized. In order to meet the market demand, manufacturing enterprises gradually change their mode of production from the original unified, single species, high-volume, high-volume manufacturing of the pipelined effective production scheduling and planning programs has an important significance to improve the production efficiency and resource utilization and reduce production costs in manufacturing enterprises.As a typical NP-hard problem, the job shop scheduling problem (JSSP) is a common production scheduling problem for manufacturing enterprises. The majority of researchers have done much work for finding an efficient solution to tackle it. In the classic job shop scheduling problem, the processing time of operations of a machine is considered constant. However, in the actual situation the processing time affected by the characteristics of the resource is usually changing. If the processing time of the job increases, we call this kind of job shop scheduling problem is job shop scheduling problem with deteriorating time. In recent years, the job shop scheduling problem with deteriorating time catches more and more researchers’ attention.The main research in this thesis is job shop scheduling problem with deteriorating time, the main research work are as follows:Firstly, we summarized the main task and purpose of the scheduling and also introduced the shop scheduling problem and its characteristics and research methods.Secondly, we summarized the job shop scheduling problem and the deteriorating time problem and then established a model of the job shop scheduling problem with deteriorating time, in which we considered the processing time as a linear function of its starting time and made the processing time, the inherent process of the job, resource capacity and other factors as constraints. Finally, according to the problem characteristics, we designed a genetic algorithm, a nested partitions algorithm and an improved nested partition algorithm respectively, then we used the enumeration algorithm and three algorithm above to solve the problem. The algorithms simulation results show that:when the problem size is small, the enumeration algorithm, the genetic algorithm, the nested partition algorithm and the improved nested partition algorithm can obtain better result, moreover, the GA algorithm has advantage in computing time. When the solution space increases larger, the enumeration algorithm can not find the optimal solution of the problem, both of the genetic algorithm and nested partition algorithm are easy to fall into local optimal solution, the improved nested partitions algorithm shows excellent performance on stability and efficiency.The research of this thesis provided an effective tool for solving the job shop scheduling problem with some practical factors.