Treffer: 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. • We study the parallel processor scheduling and bin packing problems with contiguity. • Both problems arise as a component of several two-dimensional packing problems. • We review mathematical formulations and model improvements for the two problems. • Those are computationally analyzed using a large benchmark of instances. • We demonstrate that some model improvements are useful whereas others are not. [ABSTRACT FROM AUTHOR]

Copyright of European Journal of Operational Research is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)