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:
[1]

A. AllahverdiC. NgT. Cheng and M. Y. Kovalyov, A survey of scheduling problems with setup times or costs, European Journal of Operational Research, 187 (2008), 985-1032. doi: 10.1016/j.ejor.2006.06.060. Google Scholar

[2]

B. Almada-loboD. KlabjanM. Antnia carravilla and J. F. Oliveira, Single machine multi-product capacitated lot sizing with sequence-dependent setups, International Journal of Production Research, 45 (2007), 4873-4894. doi: 10.1080/00207540601094465. Google Scholar

[3]

A. Drexl and A. Kimms, Lot sizing and scheduling survey and extensions, European Journal of Operational Research, 99 (1997), 221-235. doi: 10.1016/S0377-2217(97)00030-1. Google Scholar

[4]

M. GnoniR. IavagnilioG. MossaG. Mummolo and A. D. Leva, Production planning of a multisite, manufacturing system by hybrid modelling: A case study from the automotive industry, International Journal of Production Economics, 85 (2003), 251-262. Google Scholar

[5]

K. Haase, Capacitated lot-sizing with sequence dependent setup costs, Operations-Research-Spektrum, 18 (1996), 51-59. doi: 10.1007/BF01539882. Google Scholar

[6]

R. J. James and B. Almada-Lobo, Single and parallel machine capacitated lotsizing and scheduling: New iterative mip-based neighborhood search heuristics, Computers & Operations Research, 38 (2011), 1816-1825. doi: 10.1016/j.cor.2011.02.005. Google Scholar

[7]

R. Jans and Z. Degraeve, Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches, European Journal of Operational Research, 177 (2007), 1855-1875. doi: 10.1016/j.ejor.2005.12.008. Google Scholar

[8]

M. GnoniR. IavagnilioG. MossaG. Mummolo and A. D. Leva, Fix-and-Optimize heuristics for capacitated lot-sizing with sequence-dependent setups and substitutions, European Journal of Operational Research, 214 (2011), 595-605. Google Scholar

[9]

A. MenezesA. Clark and B. Almada-Lobo, Capacitated lot-sizing and scheduling with sequencedependent, period-overlapping and non-triangular setups, Journal of Scheduling, 14 (2011), 209-219. doi: 10.1007/s10951-010-0197-6. Google Scholar

[10]

C. E. MillerA. W. Tucker and R. A. Zemlin, Integer programming formulation of traveling salesman problems, Journal of the ACM, 7 (1960), 326-329. doi: 10.1145/321043.321046. Google Scholar

[11]

OICA Production statistics, Report of International Organization of Motor Vehicle Manufacturers, 2014. Available from: http://www.oica.net/category/production-statistics.Google Scholar

[12]

D. Quadt and H. Kuhn, Capacitated lot-sizing with extensions: A review, 4OR, 6 (2008), 61-83. doi: 10.1007/s10288-007-0057-1. Google Scholar

[13]

F. SeeannerB. Almada-Lobo and H. Meyr, Combining the principles of variable neighborhood decomposition search and the fix & optimize heuristic to solve multi-level lot-sizing and scheduling problems, Computers & Operations Research, 40 (2003), 303-317. doi: 10.1016/j.cor.2012.07.002. Google Scholar

[14]

F. Seeanner and H. Meyr, Multi-stage simultaneous lot-sizing and scheduling for flow line production, OR Spectrum, 35 (2013), 33-73. doi: 10.1007/s00291-012-0296-1. Google Scholar

[15]

F. Seeanner, Multi-Stage Simultaneous Lot-Sizing and Scheduling: Planning of Flow Lines with Shifting Bottlenecks, Damstadt: Springer Fachmedien Wiesbaden, 2013. doi: 10.1007/978-3-658-02089-7. Google Scholar

[16]

H. Stadtler and F. Sahling, A lot-sizing and scheduling model for multi-stage flow lines with zero lead times, European Journal of Operational Research, 225 (2013), 404-419. doi: 10.1016/j.ejor.2012.10.011. Google Scholar

[17]

J. XiaoC. ZhangL. Zheng and J. N. D. Gupta, Mip-based Fix-and-Optimize algorithms for the parallel machine capacitated lot-sizing and scheduling problem, International Journal of Production Research, 51 (2013), 5011-5028. Google Scholar

[18]

X. Zhu and W. E. Wilhelm, Scheduling and lot sizing with sequence-dependent setup: A literature review, IIE Transactions, 38 (2006), 987-1007. doi: 10.1080/07408170600559706. Google Scholar

show all references

References:
[1]

A. AllahverdiC. NgT. Cheng and M. Y. Kovalyov, A survey of scheduling problems with setup times or costs, European Journal of Operational Research, 187 (2008), 985-1032. doi: 10.1016/j.ejor.2006.06.060. Google Scholar

[2]

B. Almada-loboD. KlabjanM. Antnia carravilla and J. F. Oliveira, Single machine multi-product capacitated lot sizing with sequence-dependent setups, International Journal of Production Research, 45 (2007), 4873-4894. doi: 10.1080/00207540601094465. Google Scholar

[3]

A. Drexl and A. Kimms, Lot sizing and scheduling survey and extensions, European Journal of Operational Research, 99 (1997), 221-235. doi: 10.1016/S0377-2217(97)00030-1. Google Scholar

[4]

M. GnoniR. IavagnilioG. MossaG. Mummolo and A. D. Leva, Production planning of a multisite, manufacturing system by hybrid modelling: A case study from the automotive industry, International Journal of Production Economics, 85 (2003), 251-262. Google Scholar

[5]

K. Haase, Capacitated lot-sizing with sequence dependent setup costs, Operations-Research-Spektrum, 18 (1996), 51-59. doi: 10.1007/BF01539882. Google Scholar

[6]

R. J. James and B. Almada-Lobo, Single and parallel machine capacitated lotsizing and scheduling: New iterative mip-based neighborhood search heuristics, Computers & Operations Research, 38 (2011), 1816-1825. doi: 10.1016/j.cor.2011.02.005. Google Scholar

[7]

R. Jans and Z. Degraeve, Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches, European Journal of Operational Research, 177 (2007), 1855-1875. doi: 10.1016/j.ejor.2005.12.008. Google Scholar

[8]

M. GnoniR. IavagnilioG. MossaG. Mummolo and A. D. Leva, Fix-and-Optimize heuristics for capacitated lot-sizing with sequence-dependent setups and substitutions, European Journal of Operational Research, 214 (2011), 595-605. Google Scholar

[9]

A. MenezesA. Clark and B. Almada-Lobo, Capacitated lot-sizing and scheduling with sequencedependent, period-overlapping and non-triangular setups, Journal of Scheduling, 14 (2011), 209-219. doi: 10.1007/s10951-010-0197-6. Google Scholar

[10]

C. E. MillerA. W. Tucker and R. A. Zemlin, Integer programming formulation of traveling salesman problems, Journal of the ACM, 7 (1960), 326-329. doi: 10.1145/321043.321046. Google Scholar

[11]

OICA Production statistics, Report of International Organization of Motor Vehicle Manufacturers, 2014. Available from: http://www.oica.net/category/production-statistics.Google Scholar

[12]

D. Quadt and H. Kuhn, Capacitated lot-sizing with extensions: A review, 4OR, 6 (2008), 61-83. doi: 10.1007/s10288-007-0057-1. Google Scholar

[13]

F. SeeannerB. Almada-Lobo and H. Meyr, Combining the principles of variable neighborhood decomposition search and the fix & optimize heuristic to solve multi-level lot-sizing and scheduling problems, Computers & Operations Research, 40 (2003), 303-317. doi: 10.1016/j.cor.2012.07.002. Google Scholar

[14]

F. Seeanner and H. Meyr, Multi-stage simultaneous lot-sizing and scheduling for flow line production, OR Spectrum, 35 (2013), 33-73. doi: 10.1007/s00291-012-0296-1. Google Scholar

[15]

F. Seeanner, Multi-Stage Simultaneous Lot-Sizing and Scheduling: Planning of Flow Lines with Shifting Bottlenecks, Damstadt: Springer Fachmedien Wiesbaden, 2013. doi: 10.1007/978-3-658-02089-7. Google Scholar

[16]

H. Stadtler and F. Sahling, A lot-sizing and scheduling model for multi-stage flow lines with zero lead times, European Journal of Operational Research, 225 (2013), 404-419. doi: 10.1016/j.ejor.2012.10.011. Google Scholar

[17]

J. XiaoC. ZhangL. Zheng and J. N. D. Gupta, Mip-based Fix-and-Optimize algorithms for the parallel machine capacitated lot-sizing and scheduling problem, International Journal of Production Research, 51 (2013), 5011-5028. Google Scholar

[18]

X. Zhu and W. E. Wilhelm, Scheduling and lot sizing with sequence-dependent setup: A literature review, IIE Transactions, 38 (2006), 987-1007. doi: 10.1080/07408170600559706. Google Scholar

Figure 1.  Production process flow
Figure 2.  Example of bill of materials from one type of first-stage product
Figure 3.  A disconnected subtour and a main sequence
Figure 4.  A subtour connected to a main sequence at the beginning of period
Figure 5.  Relax and fix heuristic on multi-stage and over the periods
Figure 6.  Comparison of total setup time between the company planning and our model
Figure 7.  Comparison of total inventory level between the company planning and our model
Figure 8.  Comparison of total overtime between the company planning and our model
Table 1.  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
20573,750511,500407,8503,84311,43713,9062,247,8578,0297,712
100529,500521,100404,40010,35611,55714,13317,1007,7137,712
200539,100521,250395,28011,53511,40913,6807,8687,7137,712
300545,250506,850398,45011,44311,25713,3808,2457,7127,712
400559,350519,300404,85011,75711,57913,7377,7257,7127,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
20573,750511,500407,8503,84311,43713,9062,247,8578,0297,712
100529,500521,100404,40010,35611,55714,13317,1007,7137,712
200539,100521,250395,28011,53511,40913,6807,8687,7137,712
300545,250506,850398,45011,44311,25713,3808,2457,7127,712
400559,350519,300404,85011,75711,57913,7377,7257,7127,712
Table 2.  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)8716958352261090816461774
Avg. Gap (%)3.945.675.448.636.719.22
StDev. Gap1.814.061.886.192.733.36
Problem size($N \times M \times T$) $<$1000 1000—4000 4000—6000
MIP Heu. MIP Heu. MIP Heu.
Avg. Time (sec)8716958352261090816461774
Avg. Gap (%)3.945.675.448.636.719.22
StDev. Gap1.814.061.886.192.733.36
Table 3.  Numerical results of real problems by our heuristics
Avg. Time(sec)Avg. LBDev(%)
High variant of products family833018.54
Low variant of products family27561.47
Avg. Time(sec)Avg. LBDev(%)
High variant of products family833018.54
Low variant of products family27561.47
Table 4.  Total objective value between the company solutions and our model solutions
Week1234
Company1,473,4001,973,4052,008,30015,855,500
Model1,209,1001,294,4001,885,50011,345,500
Week1234
Company1,473,4001,973,4052,008,30015,855,500
Model1,209,1001,294,4001,885,50011,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]

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

[4]

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, 2017, 13 (5) : 1-18. doi: 10.3934/jimo.2019059

[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]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

[17]

María Teresa Cao-Rial, Peregrina Quintela, Carlos Moreno. Numerical solution of a time-dependent Signorini contact problem. Conference Publications, 2007, 2007 (Special) : 201-211. doi: 10.3934/proc.2007.2007.201

[18]

Tingting Liu, Qiaozhen Ma. Time-dependent asymptotic behavior of the solution for plate equations with linear memory. Discrete & Continuous Dynamical Systems - B, 2018, 23 (10) : 4595-4616. doi: 10.3934/dcdsb.2018178

[19]

Chongyang Liu, Meijia Han. Time-delay optimal control of a fed-batch production involving multiple feeds. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020099

[20]

Wen-Hung Wu, Yunqiang Yin, Wen-Hsiang Wu, Chin-Chia Wu, Peng-Hsiang Hsu. A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents. Journal of Industrial & Management Optimization, 2014, 10 (2) : 591-611. doi: 10.3934/jimo.2014.10.591

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (44)
  • HTML views (373)
  • Cited by (0)

Other articles
by authors

[Back to Top]