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