An Innovative Formulation Tightening Approach for Job-Shop Scheduling

Job shops are an important production environment for low-volume high-variety manufacturing. Its scheduling has recently been formulated as an integer linear programming (ILP) problem to take advantages of popular mixed-integer linear programming (MILP) methods, e.g., branch-and-cut. When considering a large number of parts, MILP methods may experience difficulties. To address this, a critical but much overlooked issue is formulation tightening. The idea is that if problem constraints can be transformed to directly delineate the problem convex hull in the data preprocessing stage, then a solution can be obtained by using linear programming (LP) methods without combinatorial difficulties. The tightening process, however, is fundamentally challenging because of the existence of integer variables. In this article, an innovative and systematic approach is established for the first time to tighten the formulations of individual parts, each with multiple operations, in the data preprocessing stage. It is a major advancement of our previous work on problems with binary and continuous variables to integer variables. The idea is to first link integer variables to binary variables by innovatively combining constraints so that the integer variables are uniquely determined by the binary variables. With binary and continuous variables only, it is proved that the vertices of the convex hull can be obtained based on vertices of the LP problem after relaxing binary requirements. These vertices are then converted to tightened constraints for general use. This approach significantly improves our previous results on tightening individual operations. Numerical results demonstrate significant benefits on solution quality and computational efficiency. This approach also applies to other complex ILP and MILP problems with similar characteristics and fundamentally changes the way how such problems are formulated and solved.

Automated summary

This article introduces an innovative and systematic approach to tighten the formulations of individual parts in the data preprocessing stage, linking integer variables to binary variables and obtaining vertices of the convex hull based on LP problem vertices. This significantly improves solution quality and computational efficiency, and can be applied to other complex ILP and MILP problems with similar characteristics.