A branch-and-bound algorithm for the solution of chemical production scheduling MIP models using parallel computing

• We develop a branch-and-bound algorithm for chemical production scheduling MIP models.
• The algorithm is based on domain knowledge and is designed to harness parallel computing resources.
• We develop special branching strategies and bounding procedures.
• The proposed methods lead to significant computational enhancements, allowing us to address instances of industrial relevance.
• The proposed methods are applicable to a wide range of scheduling MIP models.

Exploiting multiple cores in a computer or grid of computers can reduce the time required to solve a mixed-integer programming (MIP) model. Here, we develop a parallel branch-and-bound algorithm for a chemical production scheduling problem using a discrete-time model. The algorithm consists of initialization, submission, branching, collection, bounding, and pruning steps. We branch by adding a constraint to bound the total number of times each task runs. Each subproblem is solved as an MIP on a single core of a computer, so that many sub problems can be solved simultaneously. Also, we propose an algorithm, executed at each node of our branch-and-bound tree, to improve the bounds on the number of times a task is run based on the current objective value. We present computational results for several instances to show the parallel algorithm with the proposed branching strategy can solve more challenging problems than simply using the default parallel option.