Abstract
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 methods without much difficulty.
The tightening process, however, is fundamentally challenging because of
the existence of integer variables. In this paper, 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 linear problem after relaxing binary
requirements. These vertices are then converted to tight 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 ILP problems with similar
characteristics and fundamentally changes the way how such problems are
formulated and solved.