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