An effective optimization-based algorithm for job shop scheduling with fixed-size transfer lots

Effective scheduling of production lots is of great importance for manufact uring medium to high-volume products that require significant setup times. Compared to traditional entire-lot production, lot splitting techniques div ide a production lot into multiple smaller sublets so that each sublet can be "transferred" from one stage of operation to the next as soon as it has been completed. "Transfer lots," therefore, significantly reduce lead times and lower work-in-process (WIP) inventory. The mathematical modeling, anal ysis, and control of transfer lots, however, is extremely difficult. This p aper presents a novel integer programming formulation with separable struct ure for scheduling job shops with fixed-size transfer lots. A solution meth odology based on a synergistic combination of Lagrangian relaxation, backwa rd dynamic programming (BDP), and heuristics is developed. Through explicit modeling of lot dynamics, transfer lots are handled on standard machines, machines with setups, and machines requiring all transfer lots within a pro duction lot to be processed simultaneously. With "substates" and the deriva tion of DP functional equations considering transfer lot dynamics, the stan dard BDP is extended to solve the lot-level subproblems. The recently devel oped "time step reduction technique" is also used for increased efficiency. It implicitly establishes two time scales to reduce computational requirem ents without much loss of modeling accuracy and scheduling performance, thu s enabling resolution of long-horizon problems within controllable computat ional requirements. The method has been implemented using object-oriented p rogramming language C++, and numerical tests show that high-quality schedul es involving transfer lots are efficiently generated to achieve on-time del ivery of products with low WIP inventory.