Abstract: This paper addresses the three-dimensional space-time optimization (3D-STO) problem based on two-dimensional rectangular packing problem. Given a large rectangular sheet and a set of rectangular items, each item needs to be continuously processed with a time length on the sheet. The question is how to arrange each item′s loading time and its location and orientation during the processing period, and the goal is to minimize the total utilization time of the sheet, i.e. the makespan of the schedule. Differing from classical packing problems, each item′s location and orientation on the sheet can be changed over time such that the sheet is utilized more fully. Based on the definitions of real corner and real corner action, this paper designs an enhanced caving-degree algorithm for the sub-problem, the two-dimensional rectangular packing problem. Then by assigning a higher priority to items with longer remaining processing time at each step, this paper proposes a caving-degree based greedy scheduling algorithm (CGSA) for the 3D-STO. For comparison, this paper also proposes a scheduling algorithm called CGSA′ in which each item′s location and orientation on the sheet can′t be changed over time. Four small benchmarks with no guillotine cut constraint presented in the experiments, CGSA achieves optimal solutions whose makespan is 2. But if the experiments regard the time as a space dimension, indicating that the items can′t move over time, the shortest makespan is 3. Further, this paper generates 21 groups with a total of 210 guillotine cut constraint benchmarks. Experiments show that CGSA not only achieves more optimal solutions than CGSA′, but also obtains shorter average scheduling length than CGSA′.

Key words: space-time optimization, greedy scheduling, packing, benchmarks, placement

摘要： 研究了基于二维矩形Packing的三维时空优化问题，即对给定的一个任意宽、高的大矩形框和有限个有连续加工时间要求的任意宽、高的小矩形块，如何安排每个小矩形块的入框时刻及其出框前每一时刻的位置和方向，使得所有小矩形块的总加工时间即总调度长度makespan最短。与经典布局问题的不同之处在于，各矩形块在框内可随时间的绵延而改变其位置和方向，从而能更充分地利用矩形框的空间。基于实角与实占角动作的定义，设计了求解其子问题二维矩形Packing问题的增强穴度算法。然后，每步迭代优先考虑剩余加工时间长的矩形块，提出了求解此问题的贪心穴度调度算法（caving-degree based greedy scheduling algorithm，CGSA）。作为比较，同时设计了矩形块在框内不可随时间移动的将时间简单类比为空间的对应Packing问题的调度算法 CGSA′。对于实验中提出的满足非闸断模式的4个小型算例，它们在原问题上的最优调度长度为2，但若将时间简单地类比为空间，即矩形块放入框内后不可随时间移动其方位，则其最优调度长度为3。实验表明，算法CGSA在这4个非闸断算例上均得到了最优调度。进一步地研究出满足闸断模式的21组共210个自动生成算例，通过实验验证了算法CGSA的最优解的数目明显多于CGSA′，且CGSA的平均调度长度明显短于CGSA′。

关键词: 时空优化, 贪心调度, 装箱, 算例, 布局