Decomposition techniques for the solution of large-scale scheduling problems

With increased product specialization within the chemical-processing industries, the ability to obtain production schedules for complex facilities is at a premium. This article discusses ways of quickly obtaining solutions for industrially relevant, large-scale scheduling problems. A number of time-based decomposition approaches are presented along with their associated strengths and weaknesses. It is shown that the most promising of the approaches utilizes a reverse rolling window in conjunction with a disaggregation heuristic. In this method only a small subsection of the horizon is dealt with at a time, thus reducing the combinatorial complexity of the problem. Resource- and task-unit-based decompositions are also discussed as possible approaches to reduce the problem to manageable proportions. A number of examples are presented throughout to clarify the discussion.