Author(s):
Manoj Kumar

Author Affiliation:
Mechanical Engineering Department, Echelon Institute of Technology Faridabad, YMCA University of Science & Technologies Faridabad, Haryana, India.

This is an open access article distributed under the Creative Commons Attribution License CC BY 4.0, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited

In this paper, we investigate an effective scheduling of production lots is of great importance for manufacturing medium to high volume products that require significant setup times. As compared to traditional entire lot production, lot splitting techniques divide a production lot into multiple smaller sub-lots so that each sub-lot 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-inprocess (WIP) inventory. The mathematical modeling, analysis, and control of transfer lots, however, are extremely difficult. This paper presents a novel integer programming formulation with separable structure for scheduling job shops with fixed-size transfer lots. A solution methodology based on a synergistic combination of Lagrangian relaxation (LR), backward 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 production lot to be processed simultaneously. With the introduction of “sub-states” and the derivation of DP functional equations considering transfer lot dynamics, the standard BDP is extended to solve the lot-level sub problems. The recently developed “time step reduction technique” is also incorporated for increased efficiency. It implicitly establishes two time scales to reduce computational requirements without much loss of modeling accuracy and scheduling performance, thus enabling resolution of long horizon problems within controllable computational requirements. The method has been implemented using object-oriented programming language C++, and numerical testing results show that high quality schedules involving transfer lots are efficiently generated to achieve on-time delivery of products with low WIP inventory.

KEYWORDS:
Job Shop Scheduling; Transfer Lots; Optimization; Lagrangian Relaxation; Dynamic Programming.