Despite the significant progress made in the fields of operations research and process systems engineering ( Puigjaner, 1999 ; Shah, 1998 ) the complexity of many industrialsize scheduling problems means that a global optimal solution cannot be reached within a reasonable computational time. In these cases, the production schedule must be generated using e.g. some kind of sophisticated heuristics, which can often lead to suboptimal solutions. In this paper, we introduce a Mixed Integer Linear Programming (MILP) based algorithm, which can be efficiently used to improve an existing feasible, but nonoptimal, production schedule or to reschedule jobs in the case of changed operational parameters. The algorithm has been successfully applied to certain scheduling problems in both the paper-converting and pharmaceutical industry.