Abstract: The deterministic single-machine scheduling problem with release times is addressed. Dispatching rules and rolling horizon procedures are combined to form a two-stage sch- eduling procedure based on an initial schedule. A terminal penalty function is added into the local objective of subproblems to make it be consistent with the global one. The analytical and computational results demonstrate that this procedure can make a great improvement on the initial schedule and the global solu-tion is better than that of the existing two-pass procedure in most situations.

Key words: Initial schedule, Rolling horizon procedures, Dispatching rules, Rolling window, Two-stage procedure