Flexible job shop scheduling problem with parallel batch processing machines: MIP and CP approaches

摘要

A flexible job-shop scheduling problem (FJSP) with parallel batch processing machines (PBM) is addressed. First, we exhibit an enhanced mixed integer programming (MIP) model. Secondly, several valid inequalities are added for a reduction of solution space. Finally, we propose a constraint programming (CP) model, which is likely to be superior in many scheduling problems. Those different approaches are tested on a set of common problem instances from the literature. Computational results find three key lessons: the proposed MIP model significantly reduces computational time compared to the original model from the literature, the valid inequalities further reduce a computational time, and CP incomparably outperforms all three MIP models. Authors also discuss future adoption opportunities of CP, which has not got well deserved attention by OR/IE practitioners yet.