Rolling horizon heuristic for single-machine scheduling problem

A kind of rolling horizon heuristic for the scheduling problems with globally known information was presented. Under the heuristic, the scheduling problems were addressed by using a series of locally scheduling instead of a single globally off-line scheduling. At each decision time, a sub-problem based on a job subset was particularly defined and the sizes of sub-problems were limited. The sub-problem for locally scheduling was solved and then a portion of the solution was implemented. While the decision time was being put forward, global schedule was being realized step by step. Usually it is hard to analyze the global performance of rolling horizon procedures due to heuristic. However, a terminal penalty function was appended to the objective function of sub-problems to make the local objective consistent with the global one. Global performances of rolling horizon procedures can be analyzed to an extent. Several conclusions were drawn out about the global performance of the new rolling horizon procedures. The procedural global performance is getting better and better from one decision time to another and the performance of the initial schedule is an upper bound for that of the ultimately realized schedule.