В крупных организациях распределение зданий и служебных помещений между отделами и сотрудниками является сложной задачей. Например, в 2004 году исследовательский центр NASA Langley реорганизовал и перераспределил персонал. Этот шаг заключался в предоставлении рабочего пространства более чем 3500 лицам и 1600 исследовательским лабораториям в примерно 6200 комнатах и 300 зданиях. Реорганизации такого масштаба или более масштабные часто происходят в бизнес-секторе, поскольку слияния и поглощения создают необходимость всестороннего анализа деятельности организации.
Целью данной работы является исследование производительности эвристики поиска Tabu для поиска качественных решений проблем распределения офисных площадей. Проблемы с распределением офисных помещений состоят в том, чтобы оптимально распределить рабочее место сотрудников в офисном здании (например, подобрать офисное помещение можно на сайте) в соответствии с определенными объективными критериями. Работников можно отличить по званию (например, профессор или доцент) или по функциональности (например, инженер или аналитик). Кроме того, сотрудникам часто назначаются организационные задания в зависимости от их принадлежности к какой-либо подгруппе организации. На практике желательно иметь несколько организационных назначений для каждого сотрудника, что указывает на более сложную организационную структуру, чем одноуровневая структура.
На практике встречаются два случая проблемы с распределением офисных помещений. Первый случай – это полное переназначение каждого сотрудника в организации на новое рабочее место. Это происходит, когда организация переезжает в новое здание или претерпевает какие-либо другие преобразования, такие как слияние. В этом случае целесообразно рассмотреть вопрос о полномасштабном перераспределении офисных площадей. Второй случай – это более частый случай, когда рабочее место назначается входящему персоналу в результате найма и текучести кадров. В этом случае, строгое внимание должно быть уделено решениям, которые сводят к минимуму нарушение работы рабочей силы. В этом исследовании рассматривается только первый случай.
Обзор литературы
Проблема распределения служебных помещений – это вариант проблемы упаковки в мусорное ведро, задачи о ранце и обобщенных задач о назначении [1,14], которые, как известно, относятся к классу NP-полных задач. Смежной проблемой исследования является распределение служебных помещений в университетах. Исследовательская группа в университете Ноттингема (см. Ссылки [1] – [5], [13]) имеет ряд статей по этой теме. Они сосредоточены на эвристических и метаэвристических подходах к нахождению хороших решений проблемы распределения офисных площадей. Рассматриваемые подходы к решению включают в себя генетические алгоритмы, моделируемый отжиг, поиск по Tabu и асинхронные кооперативные механизмы [1] [5], [13]. Генетические алгоритмы, основанные на популяциях, были лучше, чем восхождение на гору и имитация отжига [10]. В [13] вычислительные эксперименты показали, что варианты Tabu-поиска, основанные на населении, дают наилучшие решения среди локального поиска и механизмов асинхронного взаимодействия на основе имитации отжига.
Поиск по Tabu – это метаэвристическая процедура, впервые появившаяся в середине 1980-х годов для решения задач оптимизации. Он был с большим успехом применен к широкому кругу задач оптимизации, включая планирование сотрудников в [6], планирование машин в [12], задачи квадратичного назначения в [15] и многие другие.
В настоящее время исследовательская группа NASA Langley Research использует алгоритм Greedy локального поиска для распределения сотрудников из различных организаций и подразделений в исследовательские лаборатории и офисы [10]. На рисунках 2 и 3 показано начальное и окончательное распределение офисного пространства НАСА, соответственно, где каждый блок представляет здание, а каждый цвет представляет отдельную суборганизацию.
ВЫВОДЫ И БУДУЩИЕ РАБОТЫ
A. Выводы
Поиск по Tabu – эффективный метод для получения качественных решений задач назначения офисных помещений. Для каждого рассматриваемого размера проблемы поиск по табу значительно превосходил многостартовое жадное решение. Преимущество, получаемое при использовании поиска по табу по сравнению с многоэтапной жадной эвристикой, увеличивается с увеличением сложности тестового примера. Чем больше количество уровней организаций и типов сотрудников, тем выше преимущество поиска в Tabu.
Б. Будущие работы
Наша цель – применить алгоритм к реальным задачам распределения. Примером такого случая является перемещение исследовательского центра NASA Langley, в котором использовалась Greedy эвристика. Другой интересной областью является дальнейшее изучение взаимосвязи между параметрами тестового примера и относительной эффективностью процедур поиска. Одним из таких отношений, который следует учитывать, является отношение количества сотрудников к количеству комнат в здании (плотность сотрудников) к производительности эвристики.
Использованные источники
[1] E.K. Burke and D.B. Varley. ”‘Automating space allocation in higher education.”’ In Proceedings of the 2nd Asia Pacific Conference on Simulated Evoluation and Learning, pages 6673, Camberra, Australia, 1998.
[2] E.K. Burke, P. Cowling, and J.D. LandaSilva. ”‘Hybrid populationbased metaheuristics approaches for the space allocation problem.”’ In Proceedings of the 2001 Congress on Evolutionary Computation, pages 232239, 2001a.
[3] E.K. Burke, P. Cowling, J.D. Landa-Silva, and B. McMullan. ”‘Three methods to automate the space allocation process in UK universities.”’ In The Practice and Theory of Automated Timetabling III: Selected Papers from the 3rd International Conference on the Practice and Theory of Automated Timetabling (PATAT 2001), Lecture Note in Computer Science, pages 254273, Springer, New York, 2001b.
[4] E.K. Burke, P. Cowling, J.D. Landa-Silva, and S. Petrovic. ”‘Combining hybrid metaheuristcs and populations for the multiobjective optimisation of space allocation problems.”’ In Proceedings of the 2001 Genetic and Evolutionary Computation Conference (GECC 2001), 2001c.
[5] E.K. Burke, C. Beyrouthy, J.D. Landa-Silva, B. McCollum, and P. McMullan. ”‘Spacemap applying meta-heuristics to real world space allocation problems in academic institutions.”’ In Proceedings of the 2004 International Conference on the Practice and Theory of Automated Timetabling (PATAT 2004), pages 441 456, Pittsburgh USA, 2004.
[6] F. Glover and C. McMillan. 1986. The General Employee Scheduling Problem: An Integration of MS and AI. COMP. OPER. RES. Vol. 13, No. 5. pages 563-574.
[7] F. Glover, “Tabu Search, Part I,” ORSA J. on Computing, 1, pp. 190206, 1989.
[8] F. Glover. 1990. Tabu Search: A Tutorial. Interfaces. Vol. 20, No. 4. pages 74-94.
[9] F. Glover and M. Laguna, Tabu Search. Kluwer Academic Publishers, Norwell, MA, 1997.
[10] R. Kincaid, R. Gates, and R. Gage. ”‘Space allocation optimization at nasa langley research center.”’ In Proceedings of the Seventh Metaheuristics International Conference, Montreal, Canada, June 2530, 2007.
[11] R. Kincaid and L.G. Yellin“The P-Dispersion-Sum Problem: Results on Trees and Graphs” Location Science, 1 (1993) pp. 171-186.
[12] M. Laguna, J.W. Barnes, and F.W. Glover. 1991. Tabu Search Methods for a Single Machine Scheduling Problem. Journal of Intelligent Manufacturing. Vol. 2, No. 2. pages 63-73.
[13] J.D. Landa-Silva, J. Dario, and Edmund K. Burke. Asynchronous cooperative local search for the office space allocation problem. INFORMS Journal on Computing, 19(4):575587, Fall 2007.
[14] S. Martello and P. Toth. Knapsack Problems Algorithms and Computer Implementations. Wiley, New York, 1990.
[15] A. Ravi Ravindran (ed.) “Metaheuristics for Discrete Optimization,” chapter (60 pages) in Operations Research and Management Science Handbook, , CRC Press, Taylor and Francis, December, 2007. ISBN: 9780849397219
[16] J. Skorin-Kapov. 1990. Tabu search applied to the quadratic assignment problem. INFORMS Journal on Computing. Vol 2. No. 2. pages 33.
Office Space Allocation Optimization
Rui Pereira, Kevin Cummiskey, Rex Kincaid