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

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