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

来源 :华中科技大学 | 被引量 : 0次 | 上传用户:xbh88
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
提出了基于二维装箱工作的三维时空优化问题。已知一个宽、高分别任意给定的大矩形框和有限个需要持续加工时间要求的宽、高分别任意的小矩形块,问如何安排每个小矩形块到框内加工的时刻及其出框前每一时刻的位置和方向,使得所有小矩形块的总加工时间即总调度长度makespace最短。三维时空优化问题与经典布局问题的不同之处在于,各矩形块在框内可随时间的绵延而改变其位置和方向,从而能更充分的利用矩形框的空间。基于实角与实占角动作的定义,设计了求解其子问题二维装箱工作的增强穴度算法。然后,每步迭代优先考虑剩余加工时间长的矩形块,设计了求解此问题的贪心穴度调度算法(A Caving-degree based Greedy Scheduling Algorithm,CGSA)。作为比较,同时设计了矩形块在框内不可随时间移动的将时间简单类比为空间的对应Packing问题的调度算法CGSA′。设计了满足非闸断模式的4个小型算例,它们在原问题上的最优调度长度为2,但若将时间简单的类比为空间,即矩形块放入框内后不可随时间移动其方位,则其最优调度长度为3。实验表明,贪心穴度算法CGSA在这4个非闸断算例上均得到了最优调度。进一步地,设计了满足闸断模式的21组共210个自动生成算例,通过实验验证了算法CGSA的最优解的数目明显多于算法CGSA′,且CGSA的平均调度长度明显短于CGSA′。
其他文献
当今社会,信息技术的迅速发展对人们的生活及工作方式带来巨大改变,计算机已成为人们生活、学习、工作的必要工具,其应用遍及各个行业。但新疆南部,经济发展相对落后,学校信
本文探索了一种利用MC算法,对国际参考电离层模型产生的某一区域三维电子浓度大数据进行可视化显示的一种方法。该方法利用osgearth地理信息平台,可快速构建某一区域三维电子浓度图像,形象展示了在某一时刻某一区域内电离层的状态,解决电离层大数据背景条件下直观化展示电离层当前状态的问题,为决策者提取电离层参数提供辅助支持。
<正>一你见过北京早上五点的天空吗?是全黑的,看不到几颗星星,仰头呼出的白气一瞬间就被吞噬。我见过那样冷冽肃杀的天空,在我高三独自赴京艺考时。因为要待一个月,为了省钱,