An efficient heuristic algorithm for two-dimensional rectangular packing problem with central rectangle

Mao Chen; Xiangyang Tang; Zhizhong Zeng; Sanya Liu

doi:10.3934/jimo.2018164

Previous Article
JIMO Home
This Issue
Next Article
Some characterizations of robust solution sets for uncertain convex optimization problems with locally Lipschitz inequality constraints

January 2020, 16(1): 495-510. doi: 10.3934/jimo.2018164

An efficient heuristic algorithm for two-dimensional rectangular packing problem with central rectangle

Mao Chen ^, , Xiangyang Tang , Zhizhong Zeng and Sanya Liu

National Engineering Research Center for E-learning, Central China Normal University, Wuhan 430079, China

* Corresponding author: Mao Chen

Received November 2017 Revised May 2018 Published January 2020 Early access October 2018

This paper presents a heuristic algorithm for solving a specific NP-hard 2D rectangular packing problem in which a rectangle called central rectangle is required to be placed in the center of the final layout, and the aspect ratio of the container is also required to be in a given range. The key component of the proposed algorithm is a greedy constructive procedure, according to which, the rectangles are packed into the container one by one and each rectangle is packed into the container by an angle-occupying placement with maximum fit degree. The proposed algorithm is evaluated on two groups of 35 well-known benchmark instances. Computational results disclose that the proposed algorithm outperforms the previous algorithm for the packing problem. For the first group of test instances, solutions with average filling rate 99.31% can be obtained; for the real-world layout problem in the second group, the filling rate of the solution is 94.75%.

Keywords: Optimization, heuristic algorithm, 2D rectangular packing problem, central rectangle, angle-occupying placement.

Mathematics Subject Classification: Primary: 68T20, 68R05.

Citation: Mao Chen, Xiangyang Tang, Zhizhong Zeng, Sanya Liu. An efficient heuristic algorithm for two-dimensional rectangular packing problem with central rectangle. Journal of Industrial and Management Optimization, 2020, 16 (1) : 495-510. doi: 10.3934/jimo.2018164

References:

[1]	A. Lodi, S. Martello and M. Monaci, Two-dimensional packing problems: A survey, European Journal of Operational Research, 141 (2002), 241-252. doi: 10.1016/S0377-2217(02)00123-6.
[2]	K. A. Dowsland and W. B. Dowsland, Packing problems, European Journal of Operational Research, 56 (1992), 2-14.
[3]	H. F. Lee and E. C. Sewell, The strip-packing problem for a boat manufacturing firm, IIE Transactions, 31 (1999), 639-651. doi: 10.1080/07408179908969865.
[4]	D. S. Hochbaum and W. Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the Association for Computing Machinery, 32 (1985), 130-136. doi: 10.1145/2455.214106.
[5]	B. S. Baker, Jr. E. G. Coffman and R. L. Rivest, Orthogonal packing in two dimensions, SIAM Journal on Computing, 9 (1980), 846-855. doi: 10.1137/0209064.
[6]	B. Chazelle, The bottom-left bin packing heuristic: An efficient implementation, IEEE Transactions on Computers, 32 (1983), 697-707. doi: 10.1109/tc.1983.1676307.
[7]	S. Jakobs, On genetic algorithms for the packing of polygons, European Journal of Operational Research, 88 (1996), 165-181. doi: 10.1016/0377-2217(94)00166-9.
[8]	D. Q. Liu and H. F. Teng, An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles, European Journal of Operational Research, 112 (1999), 413-420. doi: 10.1016/S0377-2217(97)00437-2.
[9]	E. Hopper and B. Turton, An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem, European Journal of Operational Research, 128 (2001), 34-57. doi: 10.1016/S0377-2217(99)00357-4.
[10]	Y. L. Wu, W. Q. Huang, S. C. Lau, C. K. Wong and G. H. Young, An effective quasi-human based heuristic for solving the rectangle packing problem, European Journal of Operational Research, 141 (2002), 341-358. doi: 10.1016/S0377-2217(02)00129-7.
[11]	W. Q. Huang and D. B. Chen, An efficient heuristic algorithm for rectangle-packing problem, Simulation Modelling Practice and Theory, 15 (2007), 1356-1365.
[12]	D. F. Zhang, Y. Kang and A. S. Deng, A new heuristic recursive algorithm for the strip rectangular packing problem, Computers & Operations Research, 33 (2006), 2209-2217.
[13]	L. J. Wei, D. F. Zhang and Q. S. Chen, A least wasted first heuristic algorithm for the rectangular packing problem, Computers & Operations Research, 36 (2009), 1608-1614. doi: 10.1016/j.cor.2008.03.004.
[14]	R. Alvarez-Valdes, F. Parreño and J. M. Tamarit, Reactive GRASP for the strip-packing problem, Computers & Operations Research, 35 (2008), 1065-1083. doi: 10.1016/j.cor.2006.07.004.
[15]	K. He, W. Q. Huang and Y. Jin, An efficient deterministic heuristic for two-dimensional rectangular packing, Computers & Operations Research, 39 (2012), 1355-1363. doi: 10.1016/j.cor.2011.08.005.
[16]	W. S. Xiao, L. Wu, X. Tian and J. L. Wang, Applying a new adaptive genetic algorithm to study the layout of drilling equipment in semisubmersible drilling platforms, Mathematical Problems in Engineering, 2015 (2015), Article ID 146902, 9 pages. doi: 10.1155/2015/146902.
[17]	L. Wu, L. Zhang, W.S. Xiao, Q. Liu, C. Mu and Y.W. Yang, A novel heuristic algorithm for two-dimensional rectangle packing area minimization problem with central rectangle, Computers & Industrial Engineering, 102 (2016), 208-218. doi: 10.1016/j.cie.2016.10.011.
[18]	E. K. Burke, G. Kendall and G. Whitwell, A new placement heuristic for the orthogonal stock-cutting problem, Operations Research, 52 (2004), 655-671. doi: 10.1287/opre.1040.0109.

show all references

References:

[1]	A. Lodi, S. Martello and M. Monaci, Two-dimensional packing problems: A survey, European Journal of Operational Research, 141 (2002), 241-252. doi: 10.1016/S0377-2217(02)00123-6.
[2]	K. A. Dowsland and W. B. Dowsland, Packing problems, European Journal of Operational Research, 56 (1992), 2-14.
[3]	H. F. Lee and E. C. Sewell, The strip-packing problem for a boat manufacturing firm, IIE Transactions, 31 (1999), 639-651. doi: 10.1080/07408179908969865.
[4]	D. S. Hochbaum and W. Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the Association for Computing Machinery, 32 (1985), 130-136. doi: 10.1145/2455.214106.
[5]	B. S. Baker, Jr. E. G. Coffman and R. L. Rivest, Orthogonal packing in two dimensions, SIAM Journal on Computing, 9 (1980), 846-855. doi: 10.1137/0209064.
[6]	B. Chazelle, The bottom-left bin packing heuristic: An efficient implementation, IEEE Transactions on Computers, 32 (1983), 697-707. doi: 10.1109/tc.1983.1676307.
[7]	S. Jakobs, On genetic algorithms for the packing of polygons, European Journal of Operational Research, 88 (1996), 165-181. doi: 10.1016/0377-2217(94)00166-9.
[8]	D. Q. Liu and H. F. Teng, An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles, European Journal of Operational Research, 112 (1999), 413-420. doi: 10.1016/S0377-2217(97)00437-2.
[9]	E. Hopper and B. Turton, An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem, European Journal of Operational Research, 128 (2001), 34-57. doi: 10.1016/S0377-2217(99)00357-4.
[10]	Y. L. Wu, W. Q. Huang, S. C. Lau, C. K. Wong and G. H. Young, An effective quasi-human based heuristic for solving the rectangle packing problem, European Journal of Operational Research, 141 (2002), 341-358. doi: 10.1016/S0377-2217(02)00129-7.
[11]	W. Q. Huang and D. B. Chen, An efficient heuristic algorithm for rectangle-packing problem, Simulation Modelling Practice and Theory, 15 (2007), 1356-1365.
[12]	D. F. Zhang, Y. Kang and A. S. Deng, A new heuristic recursive algorithm for the strip rectangular packing problem, Computers & Operations Research, 33 (2006), 2209-2217.
[13]	L. J. Wei, D. F. Zhang and Q. S. Chen, A least wasted first heuristic algorithm for the rectangular packing problem, Computers & Operations Research, 36 (2009), 1608-1614. doi: 10.1016/j.cor.2008.03.004.
[14]	R. Alvarez-Valdes, F. Parreño and J. M. Tamarit, Reactive GRASP for the strip-packing problem, Computers & Operations Research, 35 (2008), 1065-1083. doi: 10.1016/j.cor.2006.07.004.
[15]	K. He, W. Q. Huang and Y. Jin, An efficient deterministic heuristic for two-dimensional rectangular packing, Computers & Operations Research, 39 (2012), 1355-1363. doi: 10.1016/j.cor.2011.08.005.
[16]	W. S. Xiao, L. Wu, X. Tian and J. L. Wang, Applying a new adaptive genetic algorithm to study the layout of drilling equipment in semisubmersible drilling platforms, Mathematical Problems in Engineering, 2015 (2015), Article ID 146902, 9 pages. doi: 10.1155/2015/146902.
[17]	L. Wu, L. Zhang, W.S. Xiao, Q. Liu, C. Mu and Y.W. Yang, A novel heuristic algorithm for two-dimensional rectangle packing area minimization problem with central rectangle, Computers & Industrial Engineering, 102 (2016), 208-218. doi: 10.1016/j.cie.2016.10.011.
[18]	E. K. Burke, G. Kendall and G. Whitwell, A new placement heuristic for the orthogonal stock-cutting problem, Operations Research, 52 (2004), 655-671. doi: 10.1287/opre.1040.0109.

Figure 1. Cartesian coordinate system and central rectangle

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2. An illustrative example of angle

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3. An illustrative example of initial layout

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4. An illustrative example of angle

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5. Visual representation of the changing trend with the increase of $\varepsilon$

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6. The final layout of two hard test instances

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7. Final layout of the drilling platform

Figure Options

Download full-size image

Download as PowerPoint slide

Table 1. Settings of important parameters

Parameter	Description	Value
Nar$_{\min}$	Lower bound of the aspect ratio of the container	0.5
Nar$_{\max}$	Upper bound of the aspect ratio of the container	2
$Z_{Hmin}$	Lower bound of the between centrality of CR in vertical direction	1
$Z_{Hmax}$	Upper bound of the between centrality of CR in vertical direction	2
$Z_{Wmin}$	Lower bound of the between centrality of CR in horizontal direction	1
$Z_{Wmax}$	Upper bound of the between centrality of CR in horizontal direction	2

Table Options

Download as excel

Parameter	Description	Value
Nar$_{\min}$	Lower bound of the aspect ratio of the container	0.5
Nar$_{\max}$	Upper bound of the aspect ratio of the container	2
$Z_{Hmin}$	Lower bound of the between centrality of CR in vertical direction	1
$Z_{Hmax}$	Upper bound of the between centrality of CR in vertical direction	2
$Z_{Wmin}$	Lower bound of the between centrality of CR in horizontal direction	1
$Z_{Wmax}$	Upper bound of the between centrality of CR in horizontal direction	2

Table 2. Filling rate (%) of test instances N1--N10 under different values of parameter $\varepsilon $

Instance	Filling rate (%) under different values of parameter $\varepsilon $
Instance	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1.0	1.1	1.2	1.3	1.4	1.5	1.6
N1	81.63	81.63	83.33	77.37	83.33	78.43	77.75	77.37	74.59	74.59	73.46	73.46	74.59	74.59	73.46	52.59
N2	100	100	98.81	98.04	100	98.81	98.81	98.04	98.04	98.04	98.04	98.04	98.81	98.81	98.04	98.04
N3	99.67	99.67	99.47	99.67	99.21	99.21	99.21	98.75	98.81	98.81	98.88	98.04	99.21	98.04	98.04	90.74
N4	98.98	98.77	99.01	98.46	98.49	98.77	98.98	97.86	98.51	98.28	98.05	98.77	96.75	97.09	98.31	89.19
N5	99.21	99.21	99.21	99.21	98.18	98.24	98.12	98.39	98.19	97.98	97.65	97.98	98.27	97.23	97.92	97.22
N6	100	100	99.70	99.56	99.50	99.56	99.70	99.21	99.30	99.21	99.36	99.36	99.36	99.70	99.50	99.21
N7	100	99.95	100	99.95	99.55	99.95	99.50	99.50	99.55	99.30	99.90	99.95	99.55	99.30	99.38	99.30
N8	99.90	99.90	99.91	99.90	99.76	99.70	99.76	99.90	99.37	99.71	99.55	99.69	99.57	99.76	99.71	99.36
N9	99.75	99.75	99.73	99.73	99.73	99.68	99.73	99.68	99.68	99.68	99.68	99.68	99.68	99.68	99.68	99.68
N10	100	100	99.96	100	99.93	99.96	99.93	99.89	99.74	99.91	99.89	99.74	99.93	99.91	99.88	99.71
Average	97.91	97.89	97.91	97.19	97.77	97.23	97.15	96.86	96.58	96.55	96.06	96.47	96.57	96.41	96.39	92.50

Table Options

Download as excel

Instance	Filling rate (%) under different values of parameter $\varepsilon $
Instance	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1.0	1.1	1.2	1.3	1.4	1.5	1.6
N1	81.63	81.63	83.33	77.37	83.33	78.43	77.75	77.37	74.59	74.59	73.46	73.46	74.59	74.59	73.46	52.59
N2	100	100	98.81	98.04	100	98.81	98.81	98.04	98.04	98.04	98.04	98.04	98.81	98.81	98.04	98.04
N3	99.67	99.67	99.47	99.67	99.21	99.21	99.21	98.75	98.81	98.81	98.88	98.04	99.21	98.04	98.04	90.74
N4	98.98	98.77	99.01	98.46	98.49	98.77	98.98	97.86	98.51	98.28	98.05	98.77	96.75	97.09	98.31	89.19
N5	99.21	99.21	99.21	99.21	98.18	98.24	98.12	98.39	98.19	97.98	97.65	97.98	98.27	97.23	97.92	97.22
N6	100	100	99.70	99.56	99.50	99.56	99.70	99.21	99.30	99.21	99.36	99.36	99.36	99.70	99.50	99.21
N7	100	99.95	100	99.95	99.55	99.95	99.50	99.50	99.55	99.30	99.90	99.95	99.55	99.30	99.38	99.30
N8	99.90	99.90	99.91	99.90	99.76	99.70	99.76	99.90	99.37	99.71	99.55	99.69	99.57	99.76	99.71	99.36
N9	99.75	99.75	99.73	99.73	99.73	99.68	99.73	99.68	99.68	99.68	99.68	99.68	99.68	99.68	99.68	99.68
N10	100	100	99.96	100	99.93	99.96	99.93	99.89	99.74	99.91	99.89	99.74	99.93	99.91	99.88	99.71
Average	97.91	97.89	97.91	97.19	97.77	97.23	97.15	96.86	96.58	96.55	96.06	96.47	96.57	96.41	96.39	92.50

Table 3. Comparison with previous state-of-the-art algorithms on N13 and C21 instances

Instance	$n$	HACR							HA_AOP
Instance	$n$	$H$	$W$	Fillrate (%)	Nar	$Z_{H}$	$Z_{W}$	Time (s)	$H$	$W$	Fillrate (%)	Nar	$Z_{H}$	$Z_{W}$	Time (s)
N1	10	48	37	90.09	1.297	1.400	1.056	15.37	48	40	83.33	1.200	2.000	1.000	0.45
N2	20	36	45	92.59	0.800	1.250	1.500	77.48	30	50	100	0.6	2.000	1.500	0.13
N3	30	32	50	93.75	0.640	1.133	1.174	162.07	28	54	99.21	0.519	1.000	1.000	0.70
N4	40	89	76	94.62	1.171	1.119	1.533	294.51	70	93	98.49	0.753	1.500	2.000	17.10
N5	50	92	114	95.35	0.807	1.244	1.073	452.74	98	104	98.18	0.942	1.500	1.000	66.40
N6	60	74	71	95.17	1.042	1.467	1.536	747.08	75	67	99.50	1.119	2.000	2.000	20.76
N7	70	85	98	96.04	0.867	1.237	1.333	1061.3	90	89	99.55	1.011	1.500	1.500	62.07
N8	80	96	86	96.90	1.116	1.400	1.263	1406.7	99	81	99.76	1.222	2.000	1.000	54.29
N9	100	81	85	97.47	0.853	1.025	1.159	1913.8	94	80	99.73	1.175	1.000	2.000	59.98
N10	200	78	138	97.55	0.565	1.026	1.379	6075.4	121	87	99.93	1.391	2.000	1.500	334.58
N11	300	89	120	98.31	0.742	1.094	1.124	12489	105	100	100	1.050	2.000	2.000	572.07
N12	500	155	195	99.26	0.795	1.067	1.000	20435	154	196	99.39	0.786	1.000	2.000	93376.28
N13	3152	822	750	99.66	1.096	1.055	1.344	1.16$\times $10$^{5}$	1024	600	100	1.707	2.000	2.000	187.80
C11	16	18	24	92.59	0.750	1.250	1.400	54.45	20	20	100	1.000	1.000	1.500	0.07
C12	17	16	27	92.59	0.593	1.286	1.077	60.88	20	20	100	1.000	1.000	1.500	0.05
C13	16	21	21	90.70	1.000	1.625	1.625	52.16	25	16	100	1.563	1.000	1.000	0.01
C21	25	28	23	93.17	1.217	1.000	1.300	98.76	30	20	100	1.500	2.000	1.000	0.02
C22	25	24	27	92.30	0.889	1.400	1.455	94.05	20	30	100	0.667	2.000	1.000	0.04
C23	25	28	23	93.17	1.217	1.333	1.556	103.44	30	20	100	1.500	2.000	1.500	0.02
C31	28	38	50	94.74	0.760	1.111	1.083	154.62	30	60	100	0.500	2.000	1.500	0.86
C32	29	52	37	93.56	1.405	1.364	1.176	149.78	44	41	99.78	1.073	1.500	2.000	2.11
C33	28	40	48	93.75	0.833	1.500	1.400	160.22	40	45	100	0.889	1.000	2.000	0.74
C41	49	54	70	95.24	0.771	1.700	1.333	427.69	82	44	99.78	1.864	2.000	2.000	11.28
C42	49	73	52	94.84	1.404	1.433	1.364	432.15	72	50	100	1.440	2.000	1.500	2.65
C43	49	60	63	95.24	0.952	1.308	1.100	430.27	50	72	100	0.694	2.000	1.000	4.05
C51	72	80	70	96.43	1.143	1.353	1.188	1216.3	100	54	100	1.852	1.500	1.000	1.80
C52	73	73	77	96.07	0.948	1.433	1.265	1300.4	100	54	100	1.852	2.000	2.000	0.21
C53	72	78	72	96.15	1.083	1.137	1.215	1278.2	90	60	100	1.500	1.000	2.000	5.06
C61	97	101	99	96.01	1.020	1.172	1.020	1714.5	120	80	100	1.500	1.000	2.000	13.99
C62	97	108	92	96.62	1.174	1.571	1.300	1807.6	128	75	100	1.707	2.000	2.000	2.65
C63	97	100	100	96.00	1.000	1.273	1.174	1786.3	85	113	99.95	0.752	1.000	1.500	83.70
C71	196	197	200	97.46	0.985	1.402	1.128	6246.2	183	210	99.92	0.871	1.500	2.000	3668.73
C72	197	180	219	97.41	0.822	1.308	1.190	6012.7	256	150	100	1.707	2.000	1.000	1.23
C73	196	238	166	97.20	1.434	1.380	1.243	6175.6	194	198	99.97	0.980	2.000	1.000	4621.96
Average				95.24				5614.32			99.31				3045.99

Table Options

Download as excel

Instance	$n$	HACR							HA_AOP
Instance	$n$	$H$	$W$	Fillrate (%)	Nar	$Z_{H}$	$Z_{W}$	Time (s)	$H$	$W$	Fillrate (%)	Nar	$Z_{H}$	$Z_{W}$	Time (s)
N1	10	48	37	90.09	1.297	1.400	1.056	15.37	48	40	83.33	1.200	2.000	1.000	0.45
N2	20	36	45	92.59	0.800	1.250	1.500	77.48	30	50	100	0.6	2.000	1.500	0.13
N3	30	32	50	93.75	0.640	1.133	1.174	162.07	28	54	99.21	0.519	1.000	1.000	0.70
N4	40	89	76	94.62	1.171	1.119	1.533	294.51	70	93	98.49	0.753	1.500	2.000	17.10
N5	50	92	114	95.35	0.807	1.244	1.073	452.74	98	104	98.18	0.942	1.500	1.000	66.40
N6	60	74	71	95.17	1.042	1.467	1.536	747.08	75	67	99.50	1.119	2.000	2.000	20.76
N7	70	85	98	96.04	0.867	1.237	1.333	1061.3	90	89	99.55	1.011	1.500	1.500	62.07
N8	80	96	86	96.90	1.116	1.400	1.263	1406.7	99	81	99.76	1.222	2.000	1.000	54.29
N9	100	81	85	97.47	0.853	1.025	1.159	1913.8	94	80	99.73	1.175	1.000	2.000	59.98
N10	200	78	138	97.55	0.565	1.026	1.379	6075.4	121	87	99.93	1.391	2.000	1.500	334.58
N11	300	89	120	98.31	0.742	1.094	1.124	12489	105	100	100	1.050	2.000	2.000	572.07
N12	500	155	195	99.26	0.795	1.067	1.000	20435	154	196	99.39	0.786	1.000	2.000	93376.28
N13	3152	822	750	99.66	1.096	1.055	1.344	1.16$\times $10$^{5}$	1024	600	100	1.707	2.000	2.000	187.80
C11	16	18	24	92.59	0.750	1.250	1.400	54.45	20	20	100	1.000	1.000	1.500	0.07
C12	17	16	27	92.59	0.593	1.286	1.077	60.88	20	20	100	1.000	1.000	1.500	0.05
C13	16	21	21	90.70	1.000	1.625	1.625	52.16	25	16	100	1.563	1.000	1.000	0.01
C21	25	28	23	93.17	1.217	1.000	1.300	98.76	30	20	100	1.500	2.000	1.000	0.02
C22	25	24	27	92.30	0.889	1.400	1.455	94.05	20	30	100	0.667	2.000	1.000	0.04
C23	25	28	23	93.17	1.217	1.333	1.556	103.44	30	20	100	1.500	2.000	1.500	0.02
C31	28	38	50	94.74	0.760	1.111	1.083	154.62	30	60	100	0.500	2.000	1.500	0.86
C32	29	52	37	93.56	1.405	1.364	1.176	149.78	44	41	99.78	1.073	1.500	2.000	2.11
C33	28	40	48	93.75	0.833	1.500	1.400	160.22	40	45	100	0.889	1.000	2.000	0.74
C41	49	54	70	95.24	0.771	1.700	1.333	427.69	82	44	99.78	1.864	2.000	2.000	11.28
C42	49	73	52	94.84	1.404	1.433	1.364	432.15	72	50	100	1.440	2.000	1.500	2.65
C43	49	60	63	95.24	0.952	1.308	1.100	430.27	50	72	100	0.694	2.000	1.000	4.05
C51	72	80	70	96.43	1.143	1.353	1.188	1216.3	100	54	100	1.852	1.500	1.000	1.80
C52	73	73	77	96.07	0.948	1.433	1.265	1300.4	100	54	100	1.852	2.000	2.000	0.21
C53	72	78	72	96.15	1.083	1.137	1.215	1278.2	90	60	100	1.500	1.000	2.000	5.06
C61	97	101	99	96.01	1.020	1.172	1.020	1714.5	120	80	100	1.500	1.000	2.000	13.99
C62	97	108	92	96.62	1.174	1.571	1.300	1807.6	128	75	100	1.707	2.000	2.000	2.65
C63	97	100	100	96.00	1.000	1.273	1.174	1786.3	85	113	99.95	0.752	1.000	1.500	83.70
C71	196	197	200	97.46	0.985	1.402	1.128	6246.2	183	210	99.92	0.871	1.500	2.000	3668.73
C72	197	180	219	97.41	0.822	1.308	1.190	6012.7	256	150	100	1.707	2.000	1.000	1.23
C73	196	238	166	97.20	1.434	1.380	1.243	6175.6	194	198	99.97	0.980	2.000	1.000	4621.96
Average				95.24				5614.32			99.31				3045.99

Table 4. Details of the modules in a practical layout problem

No.	Layout module	Length (m)	Width (m)	Height (m)
1	Drilling floor	33.00	24	10.00
2	Drilling collar storage area	9.60	2.00	1.10
3	Drilling pipe area No.1	9.60	8.50	1.70
4	Drilling pipe area No.2	9.60	8.50	1.70
5	30in drive pipe area	12.50	2.70	2.70
6	20in drive pipe area	12.50	3.50	3.50
7	13-3/8in drive pipe area	12.50	4.00	4.00
8	9-5/8in drive pipe area	12.00	7.00	6.00
9	7in drive pipe area	10.50	5.00	4.20
10	Flatwise marine riser area	23.00	13.00	7.00
11	Vertical marine riser area	32.00	10.00	23.00
12	Pipe conveyor area	24.00	4.00	10.00
13	Bop area	28.50	10.00	3.80
14	Christmas tree area	20.00	9.50	3.80
15	Mud purification area	18.00	16.50	2.00
16	Living quarters	38.00	11.00	11.00

Table Options

Download as excel

No.	Layout module	Length (m)	Width (m)	Height (m)
1	Drilling floor	33.00	24	10.00
2	Drilling collar storage area	9.60	2.00	1.10
3	Drilling pipe area No.1	9.60	8.50	1.70
4	Drilling pipe area No.2	9.60	8.50	1.70
5	30in drive pipe area	12.50	2.70	2.70
6	20in drive pipe area	12.50	3.50	3.50
7	13-3/8in drive pipe area	12.50	4.00	4.00
8	9-5/8in drive pipe area	12.00	7.00	6.00
9	7in drive pipe area	10.50	5.00	4.20
10	Flatwise marine riser area	23.00	13.00	7.00
11	Vertical marine riser area	32.00	10.00	23.00
12	Pipe conveyor area	24.00	4.00	10.00
13	Bop area	28.50	10.00	3.80
14	Christmas tree area	20.00	9.50	3.80
15	Mud purification area	18.00	16.50	2.00
16	Living quarters	38.00	11.00	11.00

[1]	Georgios Fotopoulos, Markus Harju, Valery Serov. Inverse fixed angle scattering and backscattering for a nonlinear Schrödinger equation in 2D. Inverse Problems and Imaging, 2013, 7 (1) : 183-197. doi: 10.3934/ipi.2013.7.183
[2]	Julia Lieb, Raquel Pinto. A decoding algorithm for 2D convolutional codes over the erasure channel. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021031
[3]	Xiangyu Gao, Yong Sun. A new heuristic algorithm for laser antimissile strategy optimization. Journal of Industrial and Management Optimization, 2012, 8 (2) : 457-468. doi: 10.3934/jimo.2012.8.457
[4]	Chuanxin Zhao, Lin Jiang, Kok Lay Teo. A hybrid chaos firefly algorithm for three-dimensional irregular packing problem. Journal of Industrial and Management Optimization, 2020, 16 (1) : 409-429. doi: 10.3934/jimo.2018160
[5]	Claude-Michel Brauner, Josephus Hulshof, Luca Lorenzi. Stability of the travelling wave in a 2D weakly nonlinear Stefan problem. Kinetic and Related Models, 2009, 2 (1) : 109-134. doi: 10.3934/krm.2009.2.109
[6]	Chia-Huang Wu, Kuo-Hsiung Wang, Jau-Chuan Ke, Jyh-Bin Ke. A heuristic algorithm for the optimization of M/M/$s$ queue with multiple working vacations. Journal of Industrial and Management Optimization, 2012, 8 (1) : 1-17. doi: 10.3934/jimo.2012.8.1
[7]	Shinya Kinoshita. Well-posedness for the Cauchy problem of the Klein-Gordon-Zakharov system in 2D. Discrete and Continuous Dynamical Systems, 2018, 38 (3) : 1479-1504. doi: 10.3934/dcds.2018061
[8]	Hawraa Alsayed, Hussein Fakih, Alain Miranville, Ali Wehbe. Finite difference scheme for 2D parabolic problem modelling electrostatic Micro-Electromechanical Systems. Electronic Research Announcements, 2019, 26: 54-71. doi: 10.3934/era.2019.26.005
[9]	Ruihong Ji, Yongfu Wang. Mass concentration phenomenon to the 2D Cauchy problem of the compressible Navier-Stokes equations. Discrete and Continuous Dynamical Systems, 2019, 39 (2) : 1117-1133. doi: 10.3934/dcds.2019047
[10]	Yang Liu, Sining Zheng, Huapeng Li, Shengquan Liu. Strong solutions to Cauchy problem of 2D compressible nematic liquid crystal flows. Discrete and Continuous Dynamical Systems, 2017, 37 (7) : 3921-3938. doi: 10.3934/dcds.2017165
[11]	Jitao Liu. On the initial boundary value problem for certain 2D MHD-$\alpha$ equations without velocity viscosity. Communications on Pure and Applied Analysis, 2016, 15 (4) : 1179-1191. doi: 10.3934/cpaa.2016.15.1179
[12]	Gianluca Crippa, Elizaveta Semenova, Stefano Spirito. Strong continuity for the 2D Euler equations. Kinetic and Related Models, 2015, 8 (4) : 685-689. doi: 10.3934/krm.2015.8.685
[13]	Bernd Kawohl, Guido Sweers. On a formula for sets of constant width in 2d. Communications on Pure and Applied Analysis, 2019, 18 (4) : 2117-2131. doi: 10.3934/cpaa.2019095
[14]	Ka Kit Tung, Wendell Welch Orlando. On the differences between 2D and QG turbulence. Discrete and Continuous Dynamical Systems - B, 2003, 3 (2) : 145-162. doi: 10.3934/dcdsb.2003.3.145
[15]	Julien Cividini. Pattern formation in 2D traffic flows. Discrete and Continuous Dynamical Systems - S, 2014, 7 (3) : 395-409. doi: 10.3934/dcdss.2014.7.395
[16]	Géry de Saxcé, Claude Vallée. Structure of the space of 2D elasticity tensors. Discrete and Continuous Dynamical Systems - S, 2013, 6 (6) : 1525-1537. doi: 10.3934/dcdss.2013.6.1525
[17]	Igor Kukavica, Amjad Tuffaha. On the 2D free boundary Euler equation. Evolution Equations and Control Theory, 2012, 1 (2) : 297-314. doi: 10.3934/eect.2012.1.297
[18]	Liangliang Sun, Fangjun Luan, Yu Ying, Kun Mao. Rescheduling optimization of steelmaking-continuous casting process based on the Lagrangian heuristic algorithm. Journal of Industrial and Management Optimization, 2017, 13 (3) : 1431-1448. doi: 10.3934/jimo.2016081
[19]	Hong Chen, Xin Zhong. Local well-posedness to the 2D Cauchy problem of non-isothermal nonhomogeneous nematic liquid crystal flows with vacuum at infinity. Communications on Pure and Applied Analysis, , () : -. doi: 10.3934/cpaa.2022093
[20]	Mostafa Abouei Ardakan, A. Kourank Beheshti, S. Hamid Mirmohammadi, Hamed Davari Ardakani. A hybrid meta-heuristic algorithm to minimize the number of tardy jobs in a dynamic two-machine flow shop problem. Numerical Algebra, Control and Optimization, 2017, 7 (4) : 465-480. doi: 10.3934/naco.2017029

2020 Impact Factor: 1.801

Tools

Metrics

Tools

Article outline

Figures and Tables

2020 Impact Factor: 1.801

Tools

Figures and Tables

2020 Impact Factor: 1.801

American Institute of Mathematical Sciences

An efficient heuristic algorithm for two-dimensional rectangular packing problem with central rectangle

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

An efficient heuristic algorithm for two-dimensional rectangular packing problem with central rectangle

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors