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

摘要：

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

关键词：可计算性、装箱、调度、优化、NP难度

所属期刊栏目：36

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金61173180,61272014资助.This work is supported by the National Natural Science Foundation of China .61173180,61272014

在线出版日期：2013-10-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：1880-1888