A Rolling Horizon Procedure with Terminal Penalty for Large-Scale Single Machine Scheduling Problems

A more general rolling horizon procedure with terminal penalty (TP-RHP) is proposed for the single machine scheduling problems with release dates where the objective is to minimize a regular sum criterion. In TP-RHP, a sub-problem with global performance is formulated by adding the terminal penalty cost to the local performance of a local sub-problem of the RHP during the rolling procedure. The terminal penal function is estimated with an approximate cost-to-go function with a heuristic method. Theorems show that the TP-RHP method improves the procedure solution as the iteration goes forward and the global performance of the ultimate solution is always better than the heuristics.