Article-detailsAdvances in Industrial Engineering and Management
 Article-details | AIEM

2019(Volume 8)
Vol. 8, No. 1 (2019)
2018(Volume 7)
Vol. 7, No. 1 (2018)
Vol. 7, No. 2 (2018)
2017(Volume 6)
Vol. 6, No. 2 (2017)
Vol. 6, No. 1 (2017)
2016(Volume 5)
Vol. 5, No. 2 (2016)
Vol. 5, No. 1 (2016)
2015(Volume 4)
Vol. 4, No. 2 (2015)
Vol. 4, No. 1 (2015)
2014(Volume 3)
Vol.3, No.4 ( 2014 )
Vol.3, No.3 ( 2014 )
Vol.3, No.2 ( 2014 )
Vol.3, No.1 ( 2014 )
2013 ( Volume 2 )
Vol.2, No.2 ( 2013 )
Vol.2, No.1 ( 2013 )
2012 ( Volume 1 )
Vol. 1, No.1 ( 2012 )



ISSN:2222-7059 (Print);EISSN: 2222-7067 (Online)
Copyright © 2000- American Scientific Publishers. All Rights Reserved.

Title : A Novel Integer Programming Approach with Separable Structure for Scheduling Job Shops
Author(s) : Manoj Kumar*
Author affiliation : Mechanical Engineering Department, Echelon Institute of Technology Faridabad, YMCA University of Science & Technologies Faridabad, Haryana, India
Corresponding author img Corresponding author at : Corresponding author img  

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.

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

Cite it:

Full Text : PDF(size: 615.88 kB, pp. 30-45, Download times:37)

DOI : 10.7508/aiem.2018.02.002

[1] Trietsch D, Baker K. Basic Techniques for Lot Streaming, Operation Research (2015) 41(6):1065- 1076.
[2] Kropp D, Smunt T. Optimal and Heuristic Models for Lots Splitting in a Flow Shop, Decision Sciences (2014) 21(1):691-709.
[3] Wagner B, Ragatz G. The Impact of Lot Splitting on Due Date Performance. Journal of Operations Management (2014) 12(1):13-25.
[4] Benjaafar S. On Production Batches, Transfer Batches, and Lead Times, Institute of Industrial Engineering Transactions, (2015) 28(1):357-362.
[5] 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.
[6] Cetinkaya F. Lot Streaming in a Two-stage Flow Shop with Set-up, Processing and Removal Times Separated, Journal of Operation Research Society, (2013) 45(12):1445-1455.
[7] Jacobs F, Bragg D. The Repetitive Lots: Flowtime Reduction through Sequencing and Dynamic Batch Sizing, Decision Sciences, (2008) 19(1):281- 294.
[8] Glass C, Gupta J, Potts C. Lot Streaming in Three-stage Production Processes, European Journal of Operational Research, (2011) 75(1):378- 394.
[9] Luh P, Hoitomt D. Scheduling of Manufacturing Systems using the Lagrangian Relaxation Technique. IEEE Transactions on Automatic Control, (2012) 38(7):1066-1080.
[10] 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.
[11] Zhao X, Luh P, Wang J. The Surrogate Gradient Algorithm for Lagrangian Relaxation Method. Journal of Optimization Theory and Applications, (2008) 100(3):699-712.

Terms and Conditions   Privacy Policy  Copyright©2000- 2014 American Scientific Publishers. All Rights Reserved.