A Caving-degree Based Greedy Scheduling Algorithm For The Three-dimensional Space-time Optimization Problem

This paper addresses the three-dimensional space-time optimization(3D-STO) problem, which is based on the 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 goal is to minimize the total utilization time of the sheet by arranging each item's loading time and its location and orientation during the processing period. Differs to 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, we design 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, we propose a caving-degree based greedy scheduling algorithm(CGSA) for the 3D-STO. For example, we also propose a scheduling algorithm called CGSA? in which each item's location and orientation on the sheet can?t be changed over time. In the experiments, we design four small benchmarks with no guillotine cut constraint, and CGSA achieves optimal solutions whose makespan is 2. But if we simply regard the time as a space dimension, indicating that the items could not move over time, the shortest makespan is 3. We also generate 21 groups with a total of 210 guillotine cut constraint benchmarks. Experiments significantly show that CGSA not only achieves more optimal solutions than CGSA?, but also obtains shorter average scheduling length than CGSA?.