Solving the parallel processor scheduling and bin packing problems with contiguity constraints: Mathematical models and computational studies
综述了带连续性约束的并行处理器调度与装箱问题的现有数学模型，通过实验评估了模型增强、下界技术及新方法（如中途相遇模式）的效果，发现模型选择对求解能力影响大，而对称性约束无实际优势，旨在帮助设计更有效的算法。
The parallel processor scheduling and bin packing problems with contiguity constraints are important in the field of combinatorial optimization because both problems can be used as components of effective exact decomposition approaches for several two-dimensional packing problems. In this study, we provide an extensive review of existing mathematical formulations for the two problems, together with some model enhancements and lower bounding techniques, and we empirically evaluate the computational behavior of each of these elements using a state-of-the-art solver on a large set of literature instances. We also assess whether recent developments such as meet-in-the middle patterns and the reflect formulation can be used to solve the two problems more effectively. Our experiments demonstrate that some features, such as the mathematical model used, have a major impact on whether an approach is able to solve an instance, whereas other features, such as the use of symmetry-breaking constraints, do not bring any empirical advantage despite being useful in theory. Overall, our goal is to help the research community design more effective yet simpler algorithms to solve the parallel processor scheduling and bin packing problems with contiguity constraints and closely related extensions so that, eventually, those can be integrated into a larger number of exact methods for two-dimensional packing problems.