Affice Space Allocation Optimization
Rui Pereira，Kevin Cummiskey and Rex Kincaid
Abstract-In large organizations, the allocation of buildingsnd office space to departments and employees is a challengingtask. Optimal office space allocation has the potential tomaximize synergies between employees within an organizationIn this paper, we study the performance of a greedy searchalgorithm and a tabu search algorithm for generating highuality solutions to the office space allocation problem. Theobjectives are to maximize synergies in the organization, minimize the overusage of limited office space and maximize thenumber of buildings and rooms that can be completely closed.Computational experiments show that a tabu search algorithmgenerates higher quality solutions than a greedy local searchalgorithm with the same computational budget.
- INTRODUCTION
In large rganizations, the allocation of buildings andffice space to departments and employees is a challengingtask. For example, in 2004, the NASA Langley Research Center reorganized and reallocated personnel. This move consisted of assigning workspace to more than 3, 500 in-dividuals and 1, 600 research labs in approximately 6,200 rooms and 300 buildings. Reorganizations of this scale orlarger occur frequently in the business sector as mergers andacquisitions create the need for a top-to-bottom review of anorganizationrsquo;s footprint.
The purpose of this paper is to investigate the performanceof a tabu search heuristic for finding high-quality solutionsto office space allocation problems. Office space allocation problems consist of assigning employees workspace in aroffice building in an optimal fashion according to certainbjective criteria. Employees can be distinguished by rank( Professor or Assistant Professor, for example) or by func-tionality (Engineer or Analyst, for example)。 In addition.employees are frequently given organizational assignmentsbased on their membership in some subgroup of the organiza-tion. In practice. it is desirable to have several organizationalassignments for each employee which indicates a morecomplex organization structure than a single-tiered structure.
There are two cases of the office space allocation problemthat occur in practice. The first case is the complete reas-signment of every employee in the organization to a newworkspace. This occurs when an organization moves to a new building or undergoes some other transformation,such as a merger. In this case. it is economical to consider a full-scale reassignment of office space. The second case is themore frequent case where workspace is assigned to incomingpersonnel as the result of hiring and personnel turnover. Inthis case, strong consideration must be given to solutions thatminimize the disruption to the workforce. Only the first caseis considered in this study.
- Literature Review:
The office space allocation problem is a variant of the bin packing problem, the knapsack problem, and the generalizedassignment problems， all known to be in the class of NP-complete problems. A related research problem is officespace allocation in a university setting. A research group atthe University of Notting ham see references has a series of papers on this topic. These focus on heuristicand meta-heuristic approaches to finding good solutions to the office space all ocation problem. Solution approaches examined include genetic algorithms, simulated annealing，tabu search and asynchronous cooperative mechanisms。 The population based genetic algorithms were out-performed by hill climbing and simulated, computational experiments indicated that population based variants of tabu search generated the best solutionsfrom among local search and simulated annealing populationbased aysnchronous cooperation mechanisms.
Tabu search is a metaheuristic procedure that first appearedin the mid 1980s for solving optimization problems. Ithas been applied with much success to a wide variety ofoptimization problems including employee scheduling in [6]machine scheduling，quadratic assignment problemsin，and many others Currently, a NASA Langley Research research groupmploys a greedy local search algorithm for allocating employees from various organizations and divisions to research labs and offices[10].Figure 2 and figure 3 show NASas initial and final office space allocations, respectively, whereeach block represents a building and each color represents adifferent suborganization.
2. PROBLEM STATMENT
Our objectives are to minimize the distance betweenemployees in the same organization, minimize office spacemisallocation and maximize the number of vacant rooms.
The objective function seeks to capture the followingcharacteristics of candidate solutions: synergy, office spacemisallocation and building usage, We assume that the syner-gies between employees is greater when they are closer. Inother words, the synergy between two employees is inversely proportional to their distance from each other. Applyingthis concept to the organization as a whole, solutions thatminimize the sum of the distances between every pair ofemployees promote the greatest degree of cooperation andsynergistic behavior. In order to reflect the importance ofsuborganization affiliation, distances between employees ofthe same suborganization are weighted. Therefore, the firsttern in our objective function minimizes the sum of theweighted distances between all employees.
The second term of the objective function is office spacemisallocation. Employees have square footage require mentsbased upon their position and job description. For example,lab technicians require a laboratory which typically occupiesa larger amount of space. Similarly, management has specific space requirements. A penalty is added to the objective function if the size of the office assigned is less than the target size. The penalty i
剩余内容已隐藏，支付完成后下载完整资料
翻译：
办公空间配置优化
瑞·佩雷拉，凯文·康米斯基和雷克斯金凯德
在大型组织中，为部门和员工分配办公空间是一项具有挑战性的任务。最优的办公空间分配方法，具有最大限度地发挥组织内员工之间协同作用的作用。本文研究了办公空间的空间使用功能和最优分配方式，以为办公空间分配问题产生最好的的解决方案。其目标是最大限度地发挥组织内的协同作用，最大限度地减少有限办公空间的过度使用，并尽可能增加可完全关闭的建筑物和房间的数量。计算实验表明，在空间面积大小相同的情况下，办公空间优化分配具有更高的使用价值。
1.介绍
大型组织中，为部门和员工分配办公大楼和办公空间是一项具有挑战性的任务。例如，在2004年，NASA兰利研究组织针对办公空间使用分配，进行一项大规模的研究活动。这一举动包括在大约6200个房间和300栋建筑中为3500多个个人和1600个研究实验室分配工作空间。这种规模或更大的重组经常发生在业务部门，因为合并和收购需要对组织的足迹进行自上而下的审查。研究最核心的问题在于，根据一定的客观标准，以最优的方式分配员工办公空间。员工可以通过级别(例如教授或助理教授)或职能(例如工程师或分析师)来区分。员工经常根据他们在组织的某个子组中的成员资格来分配组织任务。在实践中，为每个员工分配几个组织任务是可取的，这表明组织结构比单层结构更复杂。实践中出现的办公空间分配问题有两种情况:第一种情况是将组织中的每个员工完全重新分配到一个新工作区 ，当员工迁移到一个新的办公建筑中时，工作环境得到改造，在这种情况下，考虑全面重新分配办公空间是经济的。第二种情况更为常见，由于招聘和人员流动，工作空间被分配给新来的人员。在这种情况下，必须认真考虑将对劳动力造成破坏最小化的解决方案。针对这点，本文有一个研究案例：
案例研究A
办公空间分配问题类似于垃圾分类问题。大学关于空间研究中，一个相关的研究问题是大学办公空间的分配。诺丁汉大学的一个研究小组就这个主题发表了一系列论文。这些重点是启发式和元启发式的方法，以找到好的解决方案的办公室空间分配问题。研究了遗传算法、模拟退火算法等求解方法，计算实验表明，基于种群的变量和基于模拟退火种群的同步合作机制中产生了最佳解。
禁忌搜索是20世纪80年代中期首次出现的一种求解优化问题的元启发式方法。它的成功应用,各种空间分配问题包括员工调度和机器调度的二次分配问题。目前，美国宇航局兰利研究小组使用贪婪的局部搜索算法来分配来自不同领域和部门的研究人员，显示了美国宇航局办公人员初始和最终的办公空间分配分别为，其中每个块表示一个建筑，每个颜色表示一个不同的子组织。
2.问题语句
我们的目标是尽量减少同一组织内员工之间的距离，尽量减少办公空间的分配，尽量增加空置房间的数量。目标函数试图捕捉候选解决方案的以下特征:协同、办公空间分配和建筑使用。换句话说，两个员工之间的协同作用与他们之间的距离成反比。将这一概念应用于整个组织，使每一对员工之间的距离之和最小化的解决方案可以促进最大程度的合作和协同行为。为了反映子组织从属关系的重要性，对同一子组织的员工之间的距离进行加权。因此，目标函数中的第一项最小化了所有员工之间加权距离的和。目标函数的第二项是办公空间分配，员工根据他们的职位和工作描述有面积要求。例如，实验室技术人员需要一个通常占用较大空间的实验室。同样，管理也有其特殊性空间要求。
如果分配的办公室规模小于目标大小，惩罚是由一个凸的分段线性函数来定义的，它可以对较大的违规行为产生越来越大的惩罚。目标函数的第三项计算与特定解决方案相关的空闲房间数量，并将此贡献添加到目标函数中。这个术语降低了目标函数的值，因为我们希望最大化与特定解决方案相关的空闲房间的数量。
举个小例子。请注意，更好的解决方案是让同一组织的五名员工在同一间屋子里。这样的解决方案是可行的，当一个组织的员工人数可以被房间的容量所整除，并且所有员工都有相同的方形步数。此外，更好的解决方案有更多的空房;这里优化后有8个房间是空的。
3解决方案方法
我们的问题空间由所有可能的员工人数分配到不同的空间中组成。这个简单的问题有八个房间。我们的分析侧重于将员工安置在房间中，而不是分配特定的空间中每个房间的总员工。因此，我们表示每个房间的质心由一个节点表示，节点的权重反映了该节点上的员工人数。对计算所有员工和所有房间之间的协同感兴趣，其中每条边都表示可能的协同关系。很明显，当我们处理一个完整的图表来模拟协同效应时，潜在解决方案的数量会随着每增加一个房间和每增加一个员工数量而显著增加。作为一个结果。所有可能的解决方案的枚举都是不切实际的，即使是在相对较小的实际问题上。此外，我们考虑一个两层的组织结构，三个较大的组织，每三个部门，这导致更多的可能的解决方案组合。决定员工与组织关系之间的距离。因此，个人的员工分配和组织的分配可以为目标函数贡献同等的权重。因此，第二个内存列表防止将来自组织B的员工与来自组织a的员工交换，然后将来自组织B的不同员工与来自组织a的员工交换，这将导致相同组的员工之间产生相同的有效距离。
贪婪本地搜索和禁忌搜索都可以根据从所有可能的交换中找到的解决方案是最佳解决方案。另外，在找到第一个改进的解决方案后，计算实验表明，在相关邻域中使用30%的可能移动，可以在运行时显著改进算法，对找到的最佳解决方案的风险降低较小。这是由于通过搜索解向量的排列，我们可以得到控制交换序列的随机常数顺序的解。因此，我们有效地搜索了30%以上的掉期，通过搜索解决方案向量的排列，大大减小了问题的规模。我们确保禁忌搜索算法能够概率地搜索到潜在的最佳方案，接受候选解决方案中的第一个改进方式。此外,如果禁忌搜索算法没有找到任何提高互换超过一定数量的迭代(这是一个特殊值),我们扩大社区大小更好的质量解决方案的运行时更大。
4.结果
我们的结果表明，我们的禁忌搜索程序比我们贪婪的本地搜索算法更高质量的解决方案。贪心局部搜索算法比禁忌搜索算法具有更短的搜索时间。作为一个结果。为了在中央处理器方面创造公平的竞争环境。为了与禁忌搜索算法的求解质量进行比较，我们从多变量初始分配中重新启动贪婪局部搜索过程。表三是我们计算实验的主要结果。所有的计算实验都在相同的机器上进行。
对于包含100名员工的测试问题，需要450次迭代。禁忌搜索过程平均花费2.71秒，这相当于22个随机重新启动的贪婪本地搜索的运行时。找到该问题最佳解的中位数迭代次数为318次。最小禁忌搜索解决方案超过50个副本。超过525个贪婪解的最小解是90.35%。此外，禁忌搜索算法的最大解在30个禁忌解以上，比使用等效在中央处理器时间的最小局部搜索解大15.14%。
包含150名员工的测试问题，进行750次迭代的禁忌搜索过程平均耗时19.11秒。这相当于31个随机重新启动的贪婪本地搜索的运行时。找到这个问题的最佳解决方案的中位数是519次迭代。最小选项卡搜索解决方案超过10次复制。然而。是300多个贪婪解的最小解的96.725。此外，禁忌搜索算法在10个禁忌解上的最大解为7。比使用等效在中央处理器时间的最小本地搜索解决方案大3%。描述了使用相同的y轴比例尺对四个测试问题进行的计算实验的解决方案质量。禁忌搜索过程对所找到的平均解的贪婪解产生了令人满意的显著改进。然而，由于问题的性质，我们通常更感兴趣的是等效在中央处理器时间下的最佳性能。同样，我们发现在所有的例子中禁忌搜索算法都优于贪心局部搜索算法。在每种情况下，很明显禁忌搜索在贪心局部搜索的基础上生成改进的非对称计算量。(注意，轴与轴之间的比例不同，以便更清楚地说明贪心局部搜索和禁忌搜索算法在解决方案质量上的差异)。
本实验对50余个副本的4个测试问题进行了补充。请注意，与我们的中心结果相反，这些结果考虑了邻居中更具攻击性的增长。如果禁忌搜索过程在20次迭代中没有找到一个改进的解决方案。因此，解决方案略好于表中报告的方案，但需要付出更大的计算努力。虽然目标函数值比较接近，但是150名员工的问题比较严重。然而，显示了与此结果相反的结果。
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[18715]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
