<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>The emergence of an infectious disease pandemic may result in the introduction of restrictions in the distance and number of employees, as was the case of COVID-19 in 2020/2021. In the face of fluctuating restrictions, the process of determining seating plans in office space requires repetitive execution of seat assignments, and manual planning becomes a time-consuming and error-prone task. In this paper, we introduce the Epidemiology-constrained Seating Plan problem (ESP), and we show that it, in general, belongs to the NP-complete class. However, due to some regularities in input data that could a affect computational complexity for practical cases, we conduct experiments for generated test cases. For that reason, we developed a computational environment, including the test case generator, and we published generated benchmarking test cases. Our results show that the problem can be solved to optimality by CPLEX solver only for specific settings, even in regular cases. Therefore, there is a need for new algorithms that could optimize seating plans in more general cases.</p>
</abstract>

The emergence of an infectious disease pandemic may result in the introduction of restrictions in the distance and number of employees, as was the case of COVID-19 in 2020/2021. In the face of fluctuating restrictions, the process of determining seating plans in office space requires repetitive execution of seat assignments, and manual planning becomes a time-consuming and error-prone task. In this paper, we introduce the Epidemiology-constrained Seating Plan problem (ESP), and we show that it, in general, belongs to the NP-complete class. However, due to some regularities in input data that could a affect computational complexity for practical cases, we conduct experiments for generated test cases. For that reason, we developed a computational environment, including the test case generator, and we published generated benchmarking test cases. Our results show that the problem can be solved to optimality by CPLEX solver only for specific settings, even in regular cases. Therefore, there is a need for new algorithms that could optimize seating plans in more general cases.

Epidemiology-constrained Seating Plan Problem

Foundations of Computing and Decision Sciences

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"Epidemiology-constrained Seating Plan Problem"}

The emergence of an infectious disease pandemic may result in the introduction of restrictions in the distance and number of employees, as was the case of...

Epidemiology-constrained Seating Plan Problem

Publié en ligne: 08 oct. 2022

Pages: 235 - 246

Reçu: 22 juil. 2021

Accepté: 16 mars 2022

DOI: https://doi.org/10.2478/fcds-2022-0013

Mots clés
seating plan, office seat allocation, distancing policy, mixed-integer programming, NP-complete problem

© 2022 Jakub Dąbkowski et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Epidemiology-constrained Seating Plan Problem

Publié en ligne: 08 oct. 2022

Pages: 235 - 246

Reçu: 22 juil. 2021

Accepté: 16 mars 2022

DOI: https://doi.org/10.2478/fcds-2022-0013

Mots clésseating plan, office seat allocation, distancing policy, mixed-integer programming, NP-complete problem

© 2022 Jakub Dąbkowski et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Mots clés
seating plan, office seat allocation, distancing policy, mixed-integer programming, NP-complete problem