四维时空高效利用的装箱调度问题及其可计算性证明

• 作者: 何琨 黄文奇
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 可计算性 装箱 调度 优化 NP难度
• 年，卷（期）: 2013,（9）
• 所属期刊栏目: 计算机理论
• 页码范围: 1880-1888
• 页数: 9页
• 分类号: TP301
• 字数: 7847字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2013.01880

摘要

提出了四维时空中考虑时间因素的一个长方体装箱工作的优化调度问题.已知一个形状大小任意给定的长方体形的箱子和有限个形状大小分别任意给定的长方体形的刚性物体,又知每个物体须在箱中连续烘烤的时间长度,问应如何安排每个物体的入箱时刻,以及至出箱前这段时间内它在每个时刻上的位置和方向,才能使整个箱子的被使用时间最少.问题中涉及的箱子及诸长方形刚体的长、宽、高以及各刚体须连续烘烤的时间长度均为分别任意给定的正实数.与经典装箱问题的不同之处在于,各物体在箱子内可以随时间而改变其位置和方向,从而使四维时空得到更真实、更充分的利用.进一步地,通过枚举长方体的各种排列,并证明对每一种排列,按照某种贪心策略可得到该排列下问题的最优解,从而给出了原问题具有可计算性的严格证明.在此基础上,今后有望对此问题发展出各种有效的实用求解算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄文奇	华中科技大学计算机科学与技术学院	88	1090	21.0	27.0
2	何琨	华中科技大学计算机科学与技术学院	31	263	10.0	16.0