Decomposition techniques for the solution of large‐scale scheduling problems

TLDR

In chemical processing, product specialization makes generating production schedules for complex facilities increasingly valuable. The article aims to present rapid solution methods for large‑scale industrial scheduling problems. The authors describe several time‑based decomposition techniques—including reverse rolling windows with disaggregation heuristics and resource‑ and task‑unit‑based splits—that reduce combinatorial complexity by solving small horizon subsections. The study finds that a reverse rolling window combined with a disaggregation heuristic is the most promising approach.

Abstract

Abstract 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.