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.