Terminal penalty rolling scheduling based on an initial schedule for single-machine scheduling problem

摘要

This article addresses the problem of single-machine deterministic scheduling with release times to minimize the total completion time. A type of rolling horizon procedure (RHP) is used based on an initial schedule to improve the global performance and control the computational cost. A penalty function is added to the total completion time of a local sub-problem of the RHP and this technique guarantees the improvements of the global performance over the initial schedule at each iteration. An extensive experimentation was conducted to illustrate the significance of the procedure over existing approaches. Computational results indicate that this procedure improves the initial schedule and the solution quality is higher than that of the existing procedures in most situations while the computational efforts are moderate.