Flexible Resource Dynamic Combination Production Scheduling Algorithm And Implementation

Job-shop scheduling is a research hotspot in manufacturing enterprises. The majority of job-shop scheduling problems are NP complete, which are very difficult to obtain the optimal solution when the computational complexity is controlled within an acceptable range. Heuristic algorithm, which is easy to be implemented and can achieve good performances in solving complex scheduling problems in the actual production process, has been widely applied in designing production scheduling algorithms.The research object of this paper is packaging scheduling in a tobacco factory, the process of which is composed of cabinet for storing pipe tobacco, zhenpan (a machine for transmitting pipe tobacco), packaging units and a case sealer machine. All of those devices can be dynamically combined to produce different products by the flexible connection between them. In other word, these devices have the ability of organizing dynamically on the basis of different request.The number of zhenpan in packaging lines is much more less than the number of productions produced in the packaging workshop. However, the zhenpan is the necessary machine for all products'process path. In this thesis, a dual heuristic scheduling algorithm based on the first batch has been designed. Firstly, the first batch jobs are scheduled in a heuristic way. Then, other unscheduled jobs are arranged for a heuristic scheduling based on the first jobs'running conditions in order to get the static scheduling results without any worker's participation. Because there are many emergencies which are difficult to be accurately predicted in actual production process, such as add orders unexpectedly, some dynamic scheduling algorithms are designed to make the scheduling results being more in line with a factory's actual demands. Finally, with the Nanjing cigarette factory Volume packet scheduling as the application example, experimental results have proved that the proposed dual heuristic scheduling algorithm is effective.