Figure 1.
Production process flow
-
Previous Article
Dynamic pricing of network goods in duopoly markets with boundedly rational consumers
- JIMO Home
- This Issue
-
Next Article
Optimal stopping problems with restricted stopping times
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 |
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.
Keywords:
Lot-sizing,
scheduling,
multiple-stage production,
sequence-dependent setup time,
mixed integer programming,
relax-and-fix heuristic solution.
Mathematics Subject Classification:
Primary: 58F15, 58F17; Secondary: 53C35.
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 and Management Optimization,
2017, 13
(1)
: 413-428.
doi: 10.3934/jimo.2016024
![]()
References:
| [1] |
A. Allahverdi, C. Ng, T. 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. |
| [2] |
B. Almada-lobo, D. Klabjan, M. 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. |
| [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. |
| [4] |
M. Gnoni, R. Iavagnilio, G. Mossa, G. 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.
|
| [5] |
K. Haase,
Capacitated lot-sizing with sequence dependent setup costs, Operations-Research-Spektrum, 18 (1996), 51-59.
doi: 10.1007/BF01539882. |
| [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. |
| [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. |
| [8] |
M. Gnoni, R. Iavagnilio, G. Mossa, G. 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.
|
| [9] |
A. Menezes, A. 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. |
| [10] |
C. E. Miller, A. 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. |
| [11] |
OICA Production statistics, Report of International Organization of Motor Vehicle Manufacturers, 2014. Available from: http://www.oica.net/category/production-statistics. |
| [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. |
| [13] |
F. Seeanner, B. 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. |
| [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. |
| [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. |
| [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. |
| [17] |
J. Xiao, C. Zhang, L. 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.
|
| [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. |
show all references
References:
| [1] |
A. Allahverdi, C. Ng, T. 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. |
| [2] |
B. Almada-lobo, D. Klabjan, M. 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. |
| [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. |
| [4] |
M. Gnoni, R. Iavagnilio, G. Mossa, G. 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.
|
| [5] |
K. Haase,
Capacitated lot-sizing with sequence dependent setup costs, Operations-Research-Spektrum, 18 (1996), 51-59.
doi: 10.1007/BF01539882. |
| [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. |
| [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. |
| [8] |
M. Gnoni, R. Iavagnilio, G. Mossa, G. 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.
|
| [9] |
A. Menezes, A. 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. |
| [10] |
C. E. Miller, A. 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. |
| [11] |
OICA Production statistics, Report of International Organization of Motor Vehicle Manufacturers, 2014. Available from: http://www.oica.net/category/production-statistics. |
| [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. |
| [13] |
F. Seeanner, B. 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. |
| [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. |
| [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. |
| [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. |
| [17] |
J. Xiao, C. Zhang, L. 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.
|
| [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. |
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 | |||
| 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 | ||
Table 2.
Numerical results of small problems
| Problem size( |
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( |
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 |
Table 3.
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 |
Table 4.
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] |
Sumon Sarkar, Bibhas C. Giri. Optimal lot-sizing policy for a failure prone production system with investment in process quality improvement and lead time variance reduction. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1891-1913. doi: 10.3934/jimo.2021048 |
| [2] |
Alireza Goli, Taha Keshavarz. Just-in-time scheduling in identical parallel machine sequence-dependent group scheduling problem. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021124 |
| [3] |
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 and Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431 |
| [4] |
Pedro Piñeyro, Omar Viera. Inventory policies for the economic lot-sizing problem with remanufacturing and final disposal options. Journal of Industrial and Management Optimization, 2009, 5 (2) : 217-238. doi: 10.3934/jimo.2009.5.217 |
| [5] |
Onur Kaya, Halit Bayer. Pricing and lot-sizing decisions for perishable products when demand changes by freshness. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3113-3129. doi: 10.3934/jimo.2020110 |
| [6] |
René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363 |
| [7] |
Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control and Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115 |
| [8] |
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 and Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009 |
| [9] |
Reza Alizadeh Foroutan, Javad Rezaeian, Milad Shafipour. Bi-objective unrelated parallel machines scheduling problem with worker allocation and sequence dependent setup times considering machine eligibility and precedence constraints. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021190 |
| [10] |
Min Tang, Fuying Jing, Xiangrui Chao. A dynamic lot sizing model with production-or-outsourcing decision under minimum production quantities. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2389-2406. doi: 10.3934/jimo.2019059 |
| [11] |
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 and Management Optimization, 2021, 17 (1) : 467-484. doi: 10.3934/jimo.2020043 |
| [12] |
Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027 |
| [13] |
Tugba Sarac, Aydin Sipahioglu, Emine Akyol Ozer. A two-stage solution approach for plastic injection machines scheduling problem. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1289-1314. doi: 10.3934/jimo.2020022 |
| [14] |
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 and Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783 |
| [15] |
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 and Management Optimization, 2021, 17 (6) : 3475-3491. doi: 10.3934/jimo.2020128 |
| [16] |
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 and Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435 |
| [17] |
Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557 |
| [18] |
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 and Management Optimization, 2021, 17 (5) : 2783-2804. doi: 10.3934/jimo.2020094 |
| [19] |
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 and Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323 |
| [20] |
Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1795-1807. doi: 10.3934/jimo.2021044 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]