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

An Optimal Time Scheduling Problem on Cuboids Packing over Four-Dimensional Space-Time and Its Computability Proof

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

This paper proposes an optimal time scheduling problem on cuboids packing over the four dimensional space-time. Given a cuboid container and finite rigid cuboid items, the time length that each item should be continuously processed in the container is given too. The problem asks to arrange the starting time for each item being placed into the container and to arrange the position and orientation for each item at each time instant during its continuous baking period such that the total time length the container be utilized is as short as possible. Here all side lengths of the objects and the baking time lengths are positive real numbers arbitrarily given. Differs from classical packing problems, the position and orientation of each item in the container can be changed over time. Therefore, the four-dimensional space-time can be utilized more truly and more fully. By enumerating all permutations of the items, we proved that an optimal solution could be found by a greedy strategy for each permutation, and we then presented a rigorous proof on the original problem＇s computability. This makes a good foundation for future works on the problem ~ s approximate or heuristic approaches.