Journal
IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING
Volume 19, Issue 3, Pages 2526-2539Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TASE.2021.3088047
Keywords
Job shop scheduling; Processor scheduling; Manufacturing; Data preprocessing; Systematics; Production; Mixed integer linear programming; Formulation tightening; job-shop scheduling; manufacturing; mixed-integer linear programming (MILP)
Categories
Funding
- National Science Foundation (NSF) [ECCS-1810108]
- U.S. Department of Energy (DoE)'s Office of Energy Efficiency and Renewable Energy through the Advanced Manufacturing Office [DE-EE0007613]
Ask authors/readers for more resources
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.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available