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

Lalida Deeratanasrikul; Shinji Mizuno

doi:10.3934/jimo.2016024

Article Contents

2017, Volume 13, Issue 1: 413-428. Doi: 10.3934/jimo.2016024

This issue Previous Article Optimal stopping problems with restricted stopping times Next Article Dynamic pricing of network goods in duopoly markets with boundedly rational consumers

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: August 2017

Abstract / Introduction Full Text(HTML) Figure(8) / Table(4) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Full Text(HTML)

Figure 1. Production process flow

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

Figure 3. A disconnected subtour and a main sequence

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

Table 1. Average objective values in detailed

q	Setup time (sec)			Inventory level (pieces)			Overtime (sec)
q	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

| Show Table

DownLoad: CSV

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)	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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.