<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

Published Online: Oct 08, 2022

Page range: 235 - 246

Received: Jul 22, 2021

Accepted: Mar 16, 2022

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

Keywords
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

Published Online: Oct 08, 2022

Page range: 235 - 246

Received: Jul 22, 2021

Accepted: Mar 16, 2022

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

Keywordsseating 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.

Keywords
seating plan, office seat allocation, distancing policy, mixed-integer programming, NP-complete problem