Projects per year
Abstract
The guillotine rectangular cutting problem deals with a single rectangular plate of raw material and a collection of rectangular items to be cut from the plate. Each item is associated with a profit and a demand. The problem searches for a feasible layout of a subset of items on the plate so as to maximize the total profit of selected items. The guillotine constraint restricts feasible layouts to those that can be obtained via guillotine edge-to-edge cuts that run parallel to an edge of the plate. We propose a novel constraint programming model that is suitable for guillotine cutting with an arbitrary number of stages of alternating horizontal and vertical guillotine cuts. This is an assignment-based model that models guillotine cuts using a constant number of rectangular regions, with some regions allocated to items. It treats the entire plate as a primary region and decides on the guillotine cuts required to split the regions recursively till they produce space for the items. To speed the search, the model explores the strength of cumulative scheduling relaxations of the cutting problem. Our model is a successful alternative to more traditional mixed-integer linear programming (MILP) models. It outperforms a number of state-of-the-art MILPs on a set of small and moderate size benchmark instances and proves optimality for several instances that remain challenging for these MILPs.
Original language | English |
---|---|
Title of host publication | Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling 2023 |
Editors | Sven Koenig, Roni Stern, Mauro Vallati |
Place of Publication | Palo Alto CA USA |
Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
Pages | 352-360 |
Number of pages | 9 |
Volume | 33 |
Edition | 1 |
ISBN (Electronic) | 9781577358817 |
DOIs | |
Publication status | Published - 2023 |
Event | International Conference on Automated Planning and Scheduling 2023 - Prague, Czechia Duration: 8 Jul 2023 → 13 Jul 2023 Conference number: 33rd https://ojs.aaai.org/index.php/ICAPS/issue/view/562 https://icaps23.icaps-conference.org/ (Website) |
Conference
Conference | International Conference on Automated Planning and Scheduling 2023 |
---|---|
Abbreviated title | ICAPS 2023 |
Country/Territory | Czechia |
City | Prague |
Period | 8/07/23 → 13/07/23 |
Internet address |
Keywords
- Applications and case studies of plannin and scheduling techniques
Projects
- 1 Active
-
ARC Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications (OPTIMA)
Smith-Miles, K., Stuckey, P., Taylor, P. G., Ernst, A., Aickelin, U., Garcia De La Banda Garcia, M., Pearce, A., Wallace, M., Bondell, H., Hyndman, R., Alpcan, T., Thomas, D. A., Anjomshoa, H., Kirley, M. G., Tack, G., Costa, A., Fackrell, M., Zhang, L., Glazebrook, K., Branke, J., O'Sullivan, B., O'Shea, N., Cheah, A., Meehan, A., Wetenhall, P., Bowly, D., Bridge, J., Faka, S., Mareels, I., Coleman, R. A., Crook, J., Liebman, A. & Aleti, A.
Equans Services Australia Pty Limited
23/09/21 → 23/09/26
Project: Research