Epidemiology-constrained Seating Plan Problem

• Autorzy: Dąbkowski Jakub , Kacperski Przemysław , Kaleta Mariusz

Identyfikatory

DOI

10.2478/fcds-2022-0013

• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

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

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2022
• Tom: Vol. 47, No. 3
• Strony: 235--246
• Opis fizyczny: Bibliogr. 7 poz., rys., tab.

Twórcy

autor

Dąbkowski Jakub

• Faculty of Electronics and Information Technology, Warsaw University of Technology, Warsaw

autor

Kacperski Przemysław

• Faculty of Electronics and Information Technology, Warsaw University of Technology, Warsaw

autor

Kaleta Mariusz

• Faculty of Electronics and Information Technology, Warsaw University of Technology, Warsaw

Bibliografia

• [1] Chaki P. K. and Anirban S. Algorithm for efficient seating plan for centralized exam system, in 2016 International Conference on Computational Techniques in Information and Communication Technologies (ICCTICT), 2016, 320–325.
• [2] Karp R. M. Reducibility among combinatorial problems, in Miller R. E., Thatcher J. W., and Bohlinger J. D. (eds.),Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, Springer, Boston, MA, 1972, 85–103.
• [3] Lewis R. and Carroll F. Creating seating plans: a practical application. Journal of the Operational Research Society,67, 11, 2016, 1353–1362.
• [4] McCorskey J. C. and McVetta R. W. Classroom seating arrangements: Instructional communication theory versus student preferences. Communication Education,27, 2, 1978, 99–111.
• [5] Mehrabian A. and Diamond S. G. Seating arrangement and conversation.Socio-metry,34, 2, 1971, 281–289.
• [6] Nakagawa S., Shibata M., and Fukasawa N. Optimization system of reserved/non-reserved seating plans for improving convenience and revenue of intercity express trains. International Journal of Transport Development and Integration,1, 3,2017, 359–370.
• [7] Sailer K. Degrees of opposition and cooperation. How seating plans and parliament layouts reflect and give rise to political cultures, in Proceedings of the Parliament Buildings International Conference 2021, London, 2021.