摘要
This paper addresses a new orthogonal packing and time scheduling problem-3D space-time optimization problem (3D-STO). Given a rectangular sheet and a set of rectangular items, each item needs to be continuously processed with a time length on the sheet, the 3D-STO consists in arranging each item's loading time, location, and orientation for a certain period such that the total utilization time of the sheet, i.e., the makespan of the schedule, is minimized. The 3D-STO involves a series of 2D rectangular packing problem (2D-RPP) for the whole scheduling period. If the processing time of each item is simply regarded as a space dimension for the packing, then the 3D-STO can be reduced to an NP-hard packing problem-3D strip packing problem (3D-SPP). The 3D-STO differs from the 3D-SPP in that the position and orientation of items can be changed over the processing time (the third dimension) such that the 3D-STO has a much larger search space compared with the 3D-SPP. Hereby, the optimal solution of the 3D-STO is better than or equal to the optimal solution of the 3D-SPP, and a possibly better solution could be found for the 3D-STO model. As a new model, there is no algorithm or benchmark in the literature. Moreover, the 2D-RPP and 3D-SPP algorithms are not suitable for solving the 3D-STO which considers the packing and scheduling simultaneously. Hereby, we propose a caving-degree-based scheduling algorithm (CDS) for the 3D-STO. This is the first proposed 3D-STO algorithm. We also formalize the problem as a mixed integer programming model and solve it by ILOG CPLEX. For evaluation, we provide a synthesized method to generate a total of 195 various benchmark instances with guillotine and nonguillotine cut constraints. The comparative results show that CDS is more effective than the CPLEX solver for the 3D-STO. Also, when comparing CDS for the 3D-STO and the adapted CDS for the 3D-SPP, we see that the new 3D-STO model can enhance the flexibility of the item arrangement and make maximum utilization of the sheet and time.
学科与关键词
- A reference length approach for the 3D strip packing problemWei, Lijun; Oon, Wee-Chong; Zhu, Wenbin*; Lim, AndrewEUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2012, 220(1): 37-47.被引 14
- Solving a 3D bin packing problem with stacking constraintsZhu, Weiwang; Chen, Sheng; Dai, Min; Tao, Jiping*COMPUTERS & INDUSTRIAL ENGINEERING, 2024, 188: 109814.被引 6
- A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraintBortfeldt, Andreas*; Jungmann, SabineAnnals of Operations Research, 2012, 196(1): 53-71.被引 11
