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

作     者：黄文奇 何琨 HUANG Wen-Qi;HE Kun

作者机构：华中科技大学计算机科学与技术学院武汉430074 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2013年第36卷第9期

页      面：1880-1888页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金(61173180 61272014)资助~~ 

主　　题：可计算性 装箱 调度 优化 NP难度 

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