# American Institute of Mathematical Sciences

January  2017, 13(1): 413-428. doi: 10.3934/jimo.2016024

## Multiple-stage multiple-machine capacitated lot-sizing and scheduling with sequence-dependent setup: A case study in the wheel industry

 Graduate School of Decision Science and Technology, Tokyo Institute of Technology, Tokyo 152-8552, Japan

Received  May 2015 Published  March 2016

This paper studies a real-world problem of simultaneous lot-sizing and scheduling in a capacitated flow shop. The problem combines two significant characteristics in production which are multiple-stage production with heterogeneous multiple machines and sequence-dependent setup time. Setup time does not hold the triangle inequality, thus there may be a setup for a product without actual production. Consequently, a novel mixed integer programming (MIP) formulation is proposed and tested on real data sets of wheel production. Exact approaches cannot find a feasible solution for the model in a reasonable time, so MIP-based heuristics are developed to solve the model more quickly. Test results show that the formulation is able to contain the problem requirements and the heuristics are computationally effective. Moreover, the obtained solution can improve on a real practice at the plant.

Citation: Lalida Deeratanasrikul, Shinji Mizuno. Multiple-stage multiple-machine capacitated lot-sizing and scheduling with sequence-dependent setup: A case study in the wheel industry. Journal of Industrial & Management Optimization, 2017, 13 (1) : 413-428. doi: 10.3934/jimo.2016024
##### References:

show all references

##### References:
Production process flow
Example of bill of materials from one type of first-stage product
A disconnected subtour and a main sequence
A subtour connected to a main sequence at the beginning of period
Relax and fix heuristic on multi-stage and over the periods
Comparison of total setup time between the company planning and our model
Comparison of total inventory level between the company planning and our model
Comparison of total overtime between the company planning and our model
Average objective values in detailed
 q Setup time (sec) Inventory level (pieces) Overtime (sec) W=1000 W=100 W=10 W=1000 W=100 W=10 W=1000 W=100 W=10 20 573,750 511,500 407,850 3,843 11,437 13,906 2,247,857 8,029 7,712 100 529,500 521,100 404,400 10,356 11,557 14,133 17,100 7,713 7,712 200 539,100 521,250 395,280 11,535 11,409 13,680 7,868 7,713 7,712 300 545,250 506,850 398,450 11,443 11,257 13,380 8,245 7,712 7,712 400 559,350 519,300 404,850 11,757 11,579 13,737 7,725 7,712 7,712
 q Setup time (sec) Inventory level (pieces) Overtime (sec) W=1000 W=100 W=10 W=1000 W=100 W=10 W=1000 W=100 W=10 20 573,750 511,500 407,850 3,843 11,437 13,906 2,247,857 8,029 7,712 100 529,500 521,100 404,400 10,356 11,557 14,133 17,100 7,713 7,712 200 539,100 521,250 395,280 11,535 11,409 13,680 7,868 7,713 7,712 300 545,250 506,850 398,450 11,443 11,257 13,380 8,245 7,712 7,712 400 559,350 519,300 404,850 11,757 11,579 13,737 7,725 7,712 7,712
Numerical results of small problems
 Problem size($N \times M \times T$) $<$1000 1000—4000 4000—6000 MIP Heu. MIP Heu. MIP Heu. Avg. Time (sec) 8716 958 35226 1090 81646 1774 Avg. Gap (%) 3.94 5.67 5.44 8.63 6.71 9.22 StDev. Gap 1.81 4.06 1.88 6.19 2.73 3.36
 Problem size($N \times M \times T$) $<$1000 1000—4000 4000—6000 MIP Heu. MIP Heu. MIP Heu. Avg. Time (sec) 8716 958 35226 1090 81646 1774 Avg. Gap (%) 3.94 5.67 5.44 8.63 6.71 9.22 StDev. Gap 1.81 4.06 1.88 6.19 2.73 3.36
Numerical results of real problems by our heuristics
 Avg. Time(sec) Avg. LBDev(%) High variant of products family 8330 18.54 Low variant of products family 2756 1.47
 Avg. Time(sec) Avg. LBDev(%) High variant of products family 8330 18.54 Low variant of products family 2756 1.47
Total objective value between the company solutions and our model solutions
 Week 1 2 3 4 Company 1,473,400 1,973,405 2,008,300 15,855,500 Model 1,209,100 1,294,400 1,885,500 11,345,500
 Week 1 2 3 4 Company 1,473,400 1,973,405 2,008,300 15,855,500 Model 1,209,100 1,294,400 1,885,500 11,345,500
 [1] Wan Nor Ashikin Wan Ahmad Fatthi, Adibah Shuib, Rosma Mohd Dom. A mixed integer programming model for solving real-time truck-to-door assignment and scheduling problem at cross docking warehouse. Journal of Industrial & Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431 [2] Pedro Piñeyro, Omar Viera. Inventory policies for the economic lot-sizing problem with remanufacturing and final disposal options. Journal of Industrial & Management Optimization, 2009, 5 (2) : 217-238. doi: 10.3934/jimo.2009.5.217 [3] Onur Kaya, Halit Bayer. Pricing and lot-sizing decisions for perishable products when demand changes by freshness. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020110 [4] René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363 [5] Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115 [6] Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009 [7] Min Tang, Fuying Jing, Xiangrui Chao. A dynamic lot sizing model with production-or-outsourcing decision under minimum production quantities. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2389-2406. doi: 10.3934/jimo.2019059 [8] Tien-Yu Lin, Bhaba R. Sarker, Chien-Jui Lin. An optimal setup cost reduction and lot size for economic production quantity model with imperfect quality and quantity discounts. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020043 [9] Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027 [10] Tugba Sarac, Aydin Sipahioglu, Emine Akyol Ozer. A two-stage solution approach for plastic injection machines scheduling problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020022 [11] Ming-Yong Lai, Chang-Shi Liu, Xiao-Jiao Tong. A two-stage hybrid meta-heuristic for pickup and delivery vehicle routing problem with time windows. Journal of Industrial & Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435 [12] Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel. Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming. Networks & Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783 [13] Mahdi Roozbeh, Saman Babaie–Kafaki, Zohre Aminifard. Two penalized mixed–integer nonlinear programming approaches to tackle multicollinearity and outliers effects in linear regression models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020128 [14] Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557 [15] Yunqiang Yin, T. C. E. Cheng, Jianyou Xu, Shuenn-Ren Cheng, Chin-Chia Wu. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration. Journal of Industrial & Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323 [16] Zhimin Liu, Shaojian Qu, Hassan Raza, Zhong Wu, Deqiang Qu, Jianhui Du. Two-stage mean-risk stochastic mixed integer optimization model for location-allocation problems under uncertain environment. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020094 [17] Fanwen Meng, Kiok Liang Teow, Kelvin Wee Sheng Teo, Chee Kheong Ooi, Seow Yian Tay. Predicting 72-hour reattendance in emergency departments using discriminant analysis via mixed integer programming with electronic medical records. Journal of Industrial & Management Optimization, 2019, 15 (2) : 947-962. doi: 10.3934/jimo.2018079 [18] Zhanyou Ma, Pengcheng Wang, Wuyi Yue. Performance analysis and optimization of a pseudo-fault Geo/Geo/1 repairable queueing system with N-policy, setup time and multiple working vacations. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1467-1481. doi: 10.3934/jimo.2017002 [19] Ming-Jong Yao, Shih-Chieh Chen, Yu-Jen Chang. A common cycle approach for solving the economic lot and inspection scheduling problem. Journal of Industrial & Management Optimization, 2012, 8 (1) : 141-162. doi: 10.3934/jimo.2012.8.141 [20] Yu-Jen Chang, Ming-Jong Yao. New heuristics for solving the economic lot scheduling problem with reworks. Journal of Industrial & Management Optimization, 2011, 7 (1) : 229-251. doi: 10.3934/jimo.2011.7.229

2019 Impact Factor: 1.366