Two-level rolling strategy for single-machine scheduling problem with release times

A kind of rolling horizon procedures for single-machine scheduling problem is presented to deal with the incomplete global information at decision time. At each decision time the known information should be sufficiently considered while the size of the rolling window on the sub-problem is should be limited in order to limit computational cost. The two-level rolling horizon scheduling strategy is presented to deal with the conflict. The first-level is preliminary scheduling based on the predictive windows and the second-level is locally scheduling with terminal penalty based on the rolling windows. The estimated global performance is getting close to the ultimately realized actual cost and its getting better and better while the new information is obtained and the decision time is being put forward.