四维时空高效利用的装箱调度问题

研究如下关于时空充分利用的三维空间中的长方体装箱调度问题。已知一个形状大小任意给定的长方体形的箱子和有限个形状大小各自任意给定的长方体形的刚性物体，又知每个物体须在箱中连续烘烤的时间长度，考虑应如何安排每个物体的入箱时刻，以及至出箱前这段时间内它在每个时刻上的位置和方向，才能使得整个箱子的被使用时间最少。与经典装箱问题的不同之处在于，各物体在箱子内可以改变其位置和方向。正因为如此，按本数学模型，四维时空才可以得到更真实、更充分的利用。本项研究为新鲜课题，具有高的理论和实用价值。研究的哲学途径为"拟人"，即挖掘几千年以来全人类的有关实践经验，利用西方近现代的数学语言，将它们说确切、说透彻、说完整，并加以有针对性的发展和提高，最后形式化为确切的求解算法。据我们所知，类似研究在国际上尚未起步，我们将作前瞻性的工作，取得创新性的成果。

Packing问题和调度问题有着重要的理论研究意义和广泛的实际应用价值。 本项目对我们提出的三维空间与一维时间所构成的四维时空中长方体装箱工作的优化调度问题(简称：四维装箱调度问题)的模型和算法进行了研究。项目研究工作进展顺利，达到了预期研究目标，推广和发展了传统意义上的Packing 工作，为今后更高水平的研究工作奠定了基础。.所取得的主要成果包括：1) 问题的建模、实参数下的弱可计算性分析、计算复杂度分析; 2) 其核心子问题二维/三维矩形Packing问题的较低复杂度的完备算法的设计，以及基于“动作空间”和“穴度”提出的一系列拟人高效算法；3) 其三维退化问题即二维空间与一维时间所构成的三维时空中的矩形布局的优化调度问题（简称：三维装箱调度问题）的拟人求解算法研究，与将时间简单类比为空间的相应算法的对比研究，以及多样性算例的自动生成算法的设计； 4）对四维装箱调度问题的拟人求解算法研究，将时间简单类比为空间的相应算法的对比研究，以及多样性算例的自动生成算法的设计。.在本项目支持下，在国内外权威期刊和重要学术会议上发表和录用了论文27篇，其中在SCI影响因子排名前20%的运筹学或计算机科学权威期刊以及理论计算机科学的权威期刊《Theoretical Computer Science》上共发表了8篇，在国内三大权威期刊《中国科学》、《计算机学报》、《软件学报》上共发表了9篇。学术论文被SCI收录9篇次、EI收录18篇次、ISTP收录2篇次。相关工作得到国内外同行的较多引用，从2011年至今仅项目负责人参与发表的论文的SCI他引为28次、Google引用为202次。.在人才培养方面，共培养博士毕业生5名，硕士毕业生9名；正在培养的博士研究生6名，正在培养的硕士研究生7名；培养了二十余名本科生的科研兴趣，指导本科生在ICDM等会议和期刊上发表了学术论文3篇。在本项目的资助下，积极参与国内外学术交流，分别与法国Picardie Jules Verne 大学、美国的斯坦福大学和康奈尔大学进行了交流与合作。