| Production scheduling, the core of the many advanced manufacturing mode, is widely exists in manufacturing industries. While it must not be limited to be used in the production of industrial enterprises. For vehicle scheduling, dispatching railways, air traffic controllers, multi-project management in companies and other resource scheduling, most of them can also use the fundamental of production scheduling. We can say, the application of the basic prototype of production scheduling is very extensive. Many resource-related constraints can take advantage of the basic principles of production scheduling. On the other hand, production scheduling problem is very typical of a class of combinatorial optimization problems, and with considerable difficulty in solving aspect. When the scheduling problem size becomes larger, its computation grows exponentially. The vast majority of scheduling problems belongs to NP complete problem. Thus, both to the actual application and in the theory of academic research, the study of the production scheduling problem has a very important significance.Production scheduling algorithms can be simply divided into three kinds of algorithm. They are the exact algorithm, heuristic algorithms and artificial intelligence algorithms. Each algorithm has its advantages and disadvantages. Exact algorithm can help to get the optimal solution, but computational efficiency can be very low. When to large-scale complex problems, this algorithm is sometimes difficult to solve the problem, other than a good solution. Due to that, Heuristic algorithm has developed its way. Within the use of heuristic rules, heuristic algorithm can obtain good solutions within a relatively short time. And it has expanded quite a lot of heuristic rules up till now. Belong with advances in technology, Artificial intelligence algorithms is now being studied more often. It’s more efficient, with better robust performance characteristics and adaptability. But this algorithm cannot guarantee to obtain optimal solution as well. Since we choose the flow shop environment, this paper is focused on heuristic algorithms.In heuristic algorithms, a rolling scheduling strategy is adopted to solve two-machine flow shop scheduling problem. In this strategy, big problem is decomposed into many small problems, which can greatly reduce the scale of the problem and help to shorten computation time. Rolling scheduling algorithms are more often used for one machine job shop scenario, this time we apply it to the case of two-machine flow shop. Meanwhile, this paper jumps out of the traditional rolling scheduling, which is Time-based and Job-based. Here the rolling scheduling is based on collision window.It describes the formation of a collision window in this article, sets out the basic ideas and the steps of the algorithm. To testing the performance, We compare our algorithm with other three algorithms, which is Time-based rolling scheduling algorithm, Job-based rolling scheduling algorithm and Greedy Johnson algorithm. The final results showed that, only when the number of the jobs equals 10, the Time-based rolling scheduling algorithm is better than the collision window-based rolling scheduling. And for the remaining cases, collision window-based rolling scheduling performs better. and it has a absolute advantage over the other two traditional rolling scheduling in computation time. Even if to a large-scale problem of solving 500 jobs, the efficiency of the Collision Window-based rolling scheduling is still very high. Although the Greedy Johnson algorithm also has advantages in terms of time, but its solution is very bad. In summarize, the collision window-based algorithm has a considerable advantage in the computation, and also to obtain very stable and high-quality solution.In the end, the Collision Window-based rolling scheduling is applied to industry with seasonal characteristics in order to explore its practical value, and later, we gives its application suggestions in this paper. |
PDF Full Text Request