基于穴度的三维时空优化问题的贪心调度算法

Caving-Degree Based Greedy Scheduling Algorithm for Three-Dimensional Space-Time Optimization Problem

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

This paper addresses the three- dimensional space- time optimization (3D- STO) problem based on twodimensionalrectangular packing problem. Given a large rectangular sheet and a set of rectangular items, each itemneeds to be continuously processed with a time length on the sheet. The question is how to arrange each item??s loadingtime and its location and orientation during the processing period, and the goal is to minimize the total utilization timeof the sheet, i.e. the makespan of the schedule. Differing from classical packing problems, each item??s location and orientationon the sheet can be changed over time such that the sheet is utilized more fully. Based on the definitions of realcorner and real corner action, this paper designs an enhanced caving-degree algorithm for the sub-problem, the twodimensionalrectangular packing problem. Then by assigning a higher priority to items with longer remaining processingtime 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 orientationon the sheet can??t be changed over time. Four small benchmarks with no guillotine cut constraint presented inthe experiments, CGSA achieves optimal solutions whose makespan is 2. But if the experiments regard the time as aspace dimension, indicating that the items can??t move over time, the shortest makespan is 3. Further, this paper gener-ates 21 groups with a total of 210 guillotine cut constraint benchmarks. Experiments show that CGSA not onlyachieves more optimal solutions than CGSA′, but also obtains shorter average scheduling length than CGSA′.