A Hybrid Algorithm for Strip Packing Problem with Rotation Constraint
Strip packing is a well-known NP-hard problem and it was widely applied in engineering fields. This paper considers a two-dimensional orthogonal strip packing problem. Until now some exact algorithm and mainly heuristics were proposed for two-dimensional orthogonal strip packing problem. While this...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
EDP Sciences
2016-01-01
|
| Series: | MATEC Web of Conferences |
| Online Access: | http://dx.doi.org/10.1051/matecconf/20166806001 |
| _version_ | 1831537414357647360 |
|---|---|
| author | Chen Huan Ye Furong Si Yain-Whar |
| author_facet | Chen Huan Ye Furong Si Yain-Whar |
| author_sort | Chen Huan |
| collection | DOAJ |
| description | Strip packing is a well-known NP-hard problem and it was widely applied in engineering fields. This paper considers a two-dimensional orthogonal strip packing problem. Until now some exact algorithm and mainly heuristics were proposed for two-dimensional orthogonal strip packing problem. While this paper proposes a two-stage hybrid algorithm for it. In the first stage, a heuristic algorithm based on layering idea is developed to construct a solution. In the second stage, a great deluge algorithm is used to further search a better solution. Computational results on several classes of benchmark problems have revealed that the hybrid algorithm improves the results of layer-heuristic, and can compete with other heuristics from the literature. |
| first_indexed | 2024-12-16T23:06:18Z |
| format | Article |
| id | doaj.art-9f2b9e725865476da10f5a842995f026 |
| institution | Directory Open Access Journal |
| issn | 2261-236X |
| language | English |
| last_indexed | 2024-12-16T23:06:18Z |
| publishDate | 2016-01-01 |
| publisher | EDP Sciences |
| record_format | Article |
| series | MATEC Web of Conferences |
| spelling | doaj.art-9f2b9e725865476da10f5a842995f0262022-12-21T22:12:33ZengEDP SciencesMATEC Web of Conferences2261-236X2016-01-01680600110.1051/matecconf/20166806001matecconf_iciea2016_06001A Hybrid Algorithm for Strip Packing Problem with Rotation ConstraintChen Huan0Ye Furong1Si Yain-Whar2Department of Computer Science, Xiamen UniversityDepartment of Computer Science, Xiamen UniversityDepartment of Computer and Information Science, University of MacauStrip packing is a well-known NP-hard problem and it was widely applied in engineering fields. This paper considers a two-dimensional orthogonal strip packing problem. Until now some exact algorithm and mainly heuristics were proposed for two-dimensional orthogonal strip packing problem. While this paper proposes a two-stage hybrid algorithm for it. In the first stage, a heuristic algorithm based on layering idea is developed to construct a solution. In the second stage, a great deluge algorithm is used to further search a better solution. Computational results on several classes of benchmark problems have revealed that the hybrid algorithm improves the results of layer-heuristic, and can compete with other heuristics from the literature.http://dx.doi.org/10.1051/matecconf/20166806001 |
| spellingShingle | Chen Huan Ye Furong Si Yain-Whar A Hybrid Algorithm for Strip Packing Problem with Rotation Constraint MATEC Web of Conferences |
| title | A Hybrid Algorithm for Strip Packing Problem with Rotation Constraint |
| title_full | A Hybrid Algorithm for Strip Packing Problem with Rotation Constraint |
| title_fullStr | A Hybrid Algorithm for Strip Packing Problem with Rotation Constraint |
| title_full_unstemmed | A Hybrid Algorithm for Strip Packing Problem with Rotation Constraint |
| title_short | A Hybrid Algorithm for Strip Packing Problem with Rotation Constraint |
| title_sort | hybrid algorithm for strip packing problem with rotation constraint |
| url | http://dx.doi.org/10.1051/matecconf/20166806001 |
| work_keys_str_mv | AT chenhuan ahybridalgorithmforstrippackingproblemwithrotationconstraint AT yefurong ahybridalgorithmforstrippackingproblemwithrotationconstraint AT siyainwhar ahybridalgorithmforstrippackingproblemwithrotationconstraint AT chenhuan hybridalgorithmforstrippackingproblemwithrotationconstraint AT yefurong hybridalgorithmforstrippackingproblemwithrotationconstraint AT siyainwhar hybridalgorithmforstrippackingproblemwithrotationconstraint |