수동 계획을 넘어서: 대규모 조직을 위한 좌석 배정

Beyond Manual Planning: Seating Allocation for Large Organizations

본 논문에서는 평면도 상에서 계층적으로 구조화된 조직 팀을 물리적 좌석에 최적으로 배치하는 계층적 좌석 배정 문제(HSAP)를 소개한다. 이 문제는 거대한 계층 구조를 가진 대규모 조직이 밀접한 계층적 관계를 가진 팀들(예: 연구 그룹이 인접한 구역을 점유하는 것 등)을 서로 가까운 곳에 배치해야 할 필요성 때문에 발생한다. 현재 이 문제는 수동으로 관리되고 있어 재계획이 자주 이루어지지 않으며 결과 또한 비효율적이다. 이러한 수동 프로세스를 개선하기 위해, 우리는 HSAP를 해결하는 엔드투엔드 프레임워크를 제안한다. 확률적 로드맵(PRM)과 급속 탐색 랜덤 트리(RRT)를 사용하여 모든 좌석 쌍 간의 거리를 계산하는 확장 가능한 접근 방식을 취하며, 이를 휴리스틱 탐색 및 동적 계획법과 결합하여 정수 계획법을 통해 HSAP를 해결한다. 우리는 PRM 프레임워크와 그에 따른 배정 결과를 정량적 및 정성적으로 평가하여 다양한 규모의 사례에서 본 접근 방식의 유효성을 입증한다.

We introduce the Hierarchical Seating Allocation Problem (HSAP) which addresses the optimal assignment of hierarchically structured organizational teams to physical seating arrangements on a floor plan. This problem is driven by the necessity for large organizations with large hierarchies to ensure that teams with close hierarchical relationships are seated in proximity to one another, such as ensuring a research group occupies a contiguous area. Currently, this problem is managed manually leading to infrequent and suboptimal replanning efforts. To alleviate this manual process, we propose an end-to-end framework to solve the HSAP. A scalable approach to calculate the distance between any pair of seats using a probabilistic road map (PRM) and rapidly-exploring random trees (RRT) which is combined with heuristic search and dynamic programming approach to solve the HSAP using integer programming. We demonstrate our approach under different sized instances by evaluating the PRM framework and subsequent allocations both quantitatively and qualitatively.