American Institute of Mathematical Sciences

Advanced
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

Lalida Deeratanasrikul and  Shinji Mizuno

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.

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 & 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.  Google Scholar

[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.  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. 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.   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. 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.   Google Scholar

[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.  Google Scholar

[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.  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. 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.  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. 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.   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. 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.  Google Scholar

[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.  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. 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.   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. 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.   Google Scholar

[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.  Google Scholar

[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.  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. 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.  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. 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.   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 Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Example of bill of materials from one type of first-stage product
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  A disconnected subtour and a main sequence
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  A subtour connected to a main sequence at the beginning of period
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  Relax and fix heuristic on multi-stage and over the periods
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  Comparison of total setup time between the company planning and our model
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  Comparison of total inventory level between the company planning and our model
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 8.  Comparison of total overtime between the company planning and our model
Figure Options

Download full-size image

Download as PowerPoint slide

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
Table Options

Download as excel

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
Table Options

Download as excel

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
Table Options

Download as excel

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
Table Options

Download as excel

Week1234
Company1,473,4001,973,4052,008,30015,855,500
Model1,209,1001,294,4001,885,50011,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 & Management Optimization, 2021  doi: 10.3934/jimo.2021048
[2]

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 & Management Optimization, 2021  doi: 10.3934/jimo.2021044
[3]

Yueqiang Shang, Qihui Zhang. A subgrid stabilizing postprocessed mixed finite element method for the time-dependent Navier-Stokes equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3119-3142. doi: 10.3934/dcdsb.2020222
[4]

Quan Hai, Shutang Liu. Mean-square delay-distribution-dependent exponential synchronization of chaotic neural networks with mixed random time-varying delays and restricted disturbances. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3097-3118. doi: 10.3934/dcdsb.2020221
[5]

Yunfei Lv, Rong Yuan, Yuan He. Wavefronts of a stage structured model with state--dependent delay. Discrete & Continuous Dynamical Systems, 2015, 35 (10) : 4931-4954. doi: 10.3934/dcds.2015.35.4931
[6]

Xiaochen Mao, Weijie Ding, Xiangyu Zhou, Song Wang, Xingyong Li. Complexity in time-delay networks of multiple interacting neural groups. Electronic Research Archive, , () : -. doi: 10.3934/era.2021022
[7]

Prabir Panja, Soovoojeet Jana, Shyamal kumar Mondal. Dynamics of a stage structure prey-predator model with ratio-dependent functional response and anti-predator behavior of adult prey. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 391-405. doi: 10.3934/naco.2020033
[8]

Shanjian Tang, Fu Zhang. Path-dependent optimal stochastic control and viscosity solution of associated Bellman equations. Discrete & Continuous Dynamical Systems, 2015, 35 (11) : 5521-5553. doi: 10.3934/dcds.2015.35.5521
[9]

Paul Deuring. Spatial asymptotics of mild solutions to the time-dependent Oseen system. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021044
[10]

Ying Sui, Huimin Yu. Singularity formation for compressible Euler equations with time-dependent damping. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021062
[11]

Qiwei Wu, Liping Luan. Large-time behavior of solutions to unipolar Euler-Poisson equations with time-dependent damping. Communications on Pure & Applied Analysis, 2021, 20 (3) : 995-1023. doi: 10.3934/cpaa.2021003
[12]

Masahiro Ikeda, Ziheng Tu, Kyouhei Wakasa. Small data blow-up of semi-linear wave equation with scattering dissipation and time-dependent mass. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021011
[13]

Michiyuki Watanabe. Inverse $N$-body scattering with the time-dependent hartree-fock approximation. Inverse Problems & Imaging, 2021, 15 (3) : 499-517. doi: 10.3934/ipi.2021002
[14]

Xiongxiong Bao, Wan-Tong Li. Existence and stability of generalized transition waves for time-dependent reaction-diffusion systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3621-3641. doi: 10.3934/dcdsb.2020249
[15]

Jinye Shen, Xian-Ming Gu. Two finite difference methods based on an H2N2 interpolation for two-dimensional time fractional mixed diffusion and diffusion-wave equations. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021086
[16]

Shan-Shan Lin. Due-window assignment scheduling with learning and deterioration effects. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021081
[17]

Hsin-Lun Li. Mixed Hegselmann-Krause dynamics. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021084
[18]

Namsu Ahn, Soochan Kim. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021037
[19]

Todd Hurst, Volker Rehbock. Optimizing micro-algae production in a raceway pond with variable depth. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021027
[20]

Julian Tugaut. Captivity of the solution to the granular media equation. Kinetic & Related Models, 2021, 14 (2) : 199-209. doi: 10.3934/krm.2021002

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (150)
  • HTML views (526)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences