Combining sectional processing algorithm and compound incremental cost based list scheduling algorithm for long-horizon job-shop scheduling problems

摘要

In this paper, we combine the sectional processing algorithm with the compound incremental cost based list scheduling algorithm to solve long-horizon job-shop scheduling problems. Our algorithm has achieved the reduction of both CPU times and objective values in comparing with the original method. In our simulation results, we observe that when the section length of our algorithm approximately equals the average system time, the reduction of both CPU times and objective values are approximately optimal. This observation leads us to proposing a receding horizon scheduling algorithm for infinite-horizon job-shop scheduling problems. This algorithm allows us to solve the scheduling problem one section at a time. Thus, it will not only save the computation time tremendously but also easily take care of the variation of the system configuration.