English
The Orthogonal Packing and Scheduling Problem: Model, Heuristic and Benchmark
文件大小：
1498k
资源说明：### 正交打包与调度问题：模型、启发式算法及基准测试
#### 摘要概览
本文探讨了一个新的正交打包与时间调度问题——三维空间时间优化问题（3D-STO）。该问题旨在最小化给定矩形板材上的加工时间总耗时（即最晚完成时间，makespan）。在三维空间时间优化问题中，每个矩形物品都需要在板材上进行连续加工，并具有一定的加工时间长度。问题的核心是确定每件物品的装载时间、位置和方向，以使板材的总利用率最大化。
#### 模型介绍
三维空间时间优化问题（3D-STO）实质上是将一系列二维矩形打包问题（2D-RPP）扩展到整个调度周期。如果将每个物品的加工时间视为一个额外的空间维度，则3D-STO可以简化为一个NP难问题——三维条带打包问题（3D-SPP）。然而，3D-STO与3D-SPP的关键区别在于，物品的位置和方向可以在加工过程中变化，这使得3D-STO的搜索空间远大于3D-SPP。因此，3D-STO的最优解至少不劣于3D-SPP的最优解，且有可能找到更好的解决方案。
#### 启发式算法
鉴于文献中尚未有关于3D-STO的算法或基准测试实例，作者提出了一种基于洞度的调度算法（CDS），这是首个针对3D-STO提出的算法。此外，作者还建立了混合整数规划模型，并使用ILOG CPLEX求解器进行求解。为了评估算法性能，研究团队设计了一种合成方法来生成包含吉尔丁（Guillotine）和非吉尔丁（Non-Guillotine）切割约束的共计195个不同基准测试实例。
#### 混合整数规划模型
3D-STO被形式化为混合整数规划模型。该模型考虑了物品的大小、位置、方向以及加工时间等因素，通过优化目标函数来最小化最晚完成时间。混合整数规划模型能够有效处理此类复杂问题，但计算资源需求较高。
#### 算法评价
通过比较CDS算法与ILOG CPLEX求解器的结果，研究发现CDS算法在解决3D-STO问题方面更加有效。此外，当将CDS应用于3D-STO与适应后的CDS应用于3D-SPP时，结果表明3D-STO模型可以提高物品布局的灵活性，从而实现更优的解决方案。
#### 结论
本文提出了一个新的三维空间时间优化问题，并首次引入了基于洞度的调度算法（CDS）来解决这一问题。通过对大量基准测试实例的研究，证明了CDS算法的有效性。未来的研究可以进一步探索3D-STO的其他解法，以及如何将其应用到实际生产环境中，如制造业中的材料利用和生产线调度等场景。
本文为三维空间时间优化问题的研究奠定了基础，并为解决类似问题提供了有价值的参考。通过综合考虑物品的尺寸、方向、位置及其加工时间，该研究不仅有助于提高材料利用率，还能够优化生产过程，减少浪费，进而提升整体生产效率。
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
