三维装箱工作的优化调度问题

《三维装箱工作的优化调度问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第３８卷第１２期华中科技大学学报（自然科学版）Ｖｏｌ．３８Ｎｏ．１２２０１０年１２月Ｊ．ＨｕａｚｈｏｎｇＵｎｉｖ．ｏｆＳｃｉ．＆Ｔｅｃｈ．（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）Ｄｅｃ．２０１０三维装箱工作的优化调度问题黄文奇何琨（华中科技大学计算机科学与技术学院，湖北武汉４３００７４）摘要：提出了如下关于时空充分利用的三维空间中的长方体装箱工作的调度问题：已知一个形状大小任意给定的长方体形的箱子和有限个形状大小分别任意给定的长方体形的物体，又知每个物体须在箱中连续烘烤的时间长度，考虑应如何安排每个物体的入箱时刻，以及

2、至出箱前这段时间内它在每个时刻上的位置和方向，才能使得整个箱子的被使用时间最少．与经典装箱问题的不同之处在于，各物体在箱子内可以改变其位置和方向．正因为如此，按本数学模型，四维时空才可以得到更真实、更充分的利用．关键词：布局问题；优化；装箱；调度；四维时空中图分类号：ＴＰ３０１文献标志码：Ａ文章编号：１６７１－４５１２（２０１０）１２－０１０２－０３Ｏｐｔｉｍａｌｔｉｍｅｓｃｈｅｄｕｌｉｎｇｏｆｔｈｒｅｅ－ｄｉｍｅｎｓｉｏｎａｌｓｐａｃｅｐａｃｋｉｎｇＨｕａｎｇＷｅｎｑｉＨｅＫｕｎ（ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎ

3、ｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＨｕａｚｈｏｎｇＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ４３００７４，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ａｐｒｏｂｌｅｍｏｆｔｈｅｆｏｕｒ－ｄｉｍｅｎｓｉｏｎａｌｓｐａｃｅ－ｔｉｍｅ′ｓｅｆｆｉｃｉｅｎｔｐａｃｋｉｎｇａｎｄｓｃｈｅｄｕｌｉｎｇｗａｓｐｒｏ－ｐｏｓｅｄｉｎｔｈｉｓｐａｐｅｒ．Ｇｉｖｅｎａｃｕｂｏｉｄｃｏｎｔａｉｎｅｒａｎｄａｓｅｔｏｆｃｕｂｏｉｄｉｔｅｍｓ，ｔｈｅｔｉｍｅｔｈａｔｅａｃｈｉｔｅｍｗａｓｂａｋｅｄｃｏｎｔｉｎｕｏｕｓｌｙｉｎｔｈｅｃ

4、ｏｎｔａｉｎｅｒｗａｓｇｉｖｅｎｔｏｏ，ｔｈｅｐｒｏｂｌｅｍｗａｓｈｏｗｔｏａｒｒａｎｇｅｅａｃｈｉｔｅｍ′ｓｌｏａｄ－ｉｎｇｔｉｍｅ，ａｎｄｔｈｅｌｏｃａｔｉｏｎａｎｄｏｒｉｅｎｔａｔｉｏｎｏｆｅａｃｈｌｏａｄｅｄｉｔｅｍａｔｅａｃｈｔｉｍｅｂｅｆｏｒｅｔｈｅｉｔｅｍｃｏｕｌｄｂｅｔａｋｅｎｏｕｔ．Ｔｈｅｐｕｒｐｏｓｅｗａｓｔｈａｔｔｈｅｔｏｔａｌｕｓｅｄｔｉｍｅｏｆｔｈｅｃｏｎｔａｉｎｅｒｗａｓｍｉｎｉｍｉｚｅｄ．Ｄｉｆｆｅｒｉｎｇｆｒｏｍｃｌａｓｓｉｃａｌｐａｃｋｉｎｇｐｒｏｂｌｅｍｓ，ｔｈｅｌｏｃａｔｉｏｎａｎｄｏｒ

5、ｉｅｎｔａｔｉｏｎｏｆｉｔｅｍｓｃｏｕｌｄｂｅｃｈａｎｇｅｄｉｎｔｈｅｃｏｎｔａｉｎｅｒ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｅｆｏｕｒ－ｄｉｍｅｎｓｉｏｎａｌｓｐａｃｅ－ｔｉｍｅｃｏｕｌｄｂｅｕｔｉｌｉｚｅｄｍｏｒｅｔｒｕｌｙａｎｄｍｏｒｅｆｕｌｌｙ．Ｋｅｙｗｏｒｄｓ：ｐａｃｋｉｎｇｐｒｏｂｌｅｍ；ｏｐｔｉｍｉｚａｔｉｏｎ；ｐａｃｋｉｎｇ；ｓｃｈｅｄｕｌｉｎｇ；ｆｏｕｒ－ｄｉｍｅｎｓｉｏｎａｌｓｐａｃｅ－ｔｉｍｅ［７］Ｐａｃｋｉｎｇ问题（布局问题）是一类典型的ＮＰ的应用包括多阶段资金预算问题等．时间与空难度问题．根据布局空间的维度，可

6、将之分为一间是构成宇宙的基本要素，时间与空间综合考虑维、二维、三维和四维及以上的高维Ｐａｃｋｉｎｇ问的高维Ｐａｃｋｉｎｇ问题具有重要的科学意义和现实题．高维Ｐａｃｋｉｎｇ问题可以是非材料布局，也可以的应用价值．［１］由特殊材料布局问题转化而来．相关的研究主通过进一步的观察，可以发现现实生活中很要包括两类：一类是对高维几何布局问题进行纯多与Ｐａｃｋｉｎｇ有关的问题，例如饼干的烘制、内存［２］理论性的研究；另一类是将其他非几何物理量空间的分配、数据库存储空间的分配等，这些需要类比成几何维度以构成高维几何布局问题，然后一定烘烤时间

7、的物体或有一定存活期的数据在存分析求解这些非几何物理量的不嵌入运筹问题．放区域内可以随时间而改变其位置和方向，且这其中：一类典型的物理量是时间，相关的应用包括种改变能使时间和空间得到更充分的利用．因此，［３］［４］空间调度问题、组装线问题、多处理器调度问本文拟对三维空间与一维时间所构成的四维时空［５，６］题等；另一类典型的物理量是资金数量，相关中长方体装箱工作的调度问题进行研究．与高维收稿日期：２０１０－０４－２９．作者简介：黄文奇（１９３８－），男，教授；何琨（通信作者），讲师，Ｅ－ｍａｉｌ：ｂｒｏｏｋｌｅｔ６０＠ｇｍａｉ

8、ｌ．ｃｏｍ．基金项目：国家自然科学基金资助项目（６０７７３１９４）．第１２期黄文奇等：三维装箱工作的优化调度问题·１０３·Ｐａｃｋｉｎｇ问题的不同之处在于，本项研究中物体入烤盘的时刻、取出烤盘的时刻以及在烤盘中每从放入容器到取出这段时间内可以改变其位置和个时刻饼干的位置和方向．设烤盘开始工