: Mechanical Engineering Department, Echelon Institute of Technology Faridabad,
YMCA University of Science & Technologies Faridabad, Haryana, India
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.
:Job Shop Scheduling; Transfer Lots; Optimization; Lagrangian Relaxation;
(size: 615.88 kB, pp. 30-45
, Download times:
 Trietsch D, Baker K. Basic Techniques for Lot
Streaming, Operation Research (2015) 41(6):1065-
 Kropp D, Smunt T. Optimal and Heuristic
Models for Lots Splitting in a Flow Shop, Decision
Sciences (2014) 21(1):691-709.
 Wagner B, Ragatz G. The Impact of Lot Splitting
on Due Date Performance. Journal of Operations
Management (2014) 12(1):13-25.
 Benjaafar S. On Production Batches, Transfer
Batches, and Lead Times, Institute of Industrial
Engineering Transactions, (2015) 28(1):357-362.
 Vickson R, Alfredsson B. Two and Threemachine
Flow Shop Scheduling Problems with
Equal Sized Transfer Batches, International Journal
of Production Research, (2010) 30(7):1551-1574.
 Cetinkaya F. Lot Streaming in a Two-stage Flow
Shop with Set-up, Processing and Removal Times
Separated, Journal of Operation Research Society,
 Jacobs F, Bragg D. The Repetitive Lots: Flowtime
Reduction through Sequencing and Dynamic
Batch Sizing, Decision Sciences, (2008) 19(1):281-
 Glass C, Gupta J, Potts C. Lot Streaming in
Three-stage Production Processes, European
Journal of Operational Research, (2011) 75(1):378-
 Luh P, Hoitomt D. Scheduling of Manufacturing
Systems using the Lagrangian Relaxation
Technique. IEEE Transactions on Automatic
Control, (2012) 38(7):1066-1080.
 Luh P, Gou L, Zhang Y, Nagahora T, Tsuji
M, Yoneda K, Hasegawa T, Kyoya Y, Kano T. Job
Shop Scheduling with Group-dependent Setups,
Finite Buffers, and Long Time Horizon. Annals of
Operations Research, (2011) 76(1):233-259.
 Zhao X, Luh P, Wang J. The Surrogate Gradient
Algorithm for Lagrangian Relaxation Method.
Journal of Optimization Theory and Applications,