Optimization of office space allocation among employees
Introduction
This example presents a solution to the problem of optimal allocation of a limited resource — office space — among employees, taking into account a number of organizational requirements. The optimization criteria are the personal preferences of employees, weighted by their length of service, as well as a prerequisite for the adjacency of jobs for two pairs of employees engaged in joint projects. The task is formalized in the form of an integer linear programming model in order to maximize the total weighted satisfaction of preferences while observing all established constraints.
Distribution of premises
Our task is to distribute seven office spaces among six employees.
The names of the employees are: Anna, Artyom, Alyona, Anton, Andrey, Anastasia.
Each employee gets exactly one office, and there can be no more than one person in each office. Thus, one room will inevitably remain empty.
Employees can indicate their preferences for choosing jobs, and these wishes are taken into account in accordance with their work experience in the company: the longer a person has been working in the company, the higher their priority.
The layout of the rooms is heterogeneous: some of the offices have windows, others do not, and one of the windows is noticeably smaller than the others. An additional complication is that Alyona and Anton often work in pairs, so they should be placed in adjacent rooms. The same applies to Andrey and Anastasia — their jobs should also be adjacent.
We will add the necessary libraries and the layout function.
import Pkg
Pkg.add(["JuMP", "HiGHS"])
using JuMP, HiGHS, LinearAlgebra
include("officeassign.jl")
Layout of the premises
Offices 1, 2, 3 and 4 are located inside the building — these are rooms without windows. Rooms 5, 6, and 7 have access to natural light, but it is important to note that the window in Room 5 is significantly smaller than in the other two.
The layout of the offices:
кабинеты = ["Кабинет 1", "Кабинет 2", "Кабинет 3", "Кабинет 4", "Кабинет 5", "Кабинет 6", "Кабинет 7"];
officeassign(кабинеты)
Setting the task
Let's present the problem in the form of a mathematical model. Let's create binary variables that will indicate whether the office belongs to a specific employee.
List of employee names:
имена = ["Анна", "Артём", "Алёна", "Антон", "Андрей", "Анастасия"];
Let's create binary variables indexed by office numbers and employee names.
модель = Model(HiGHS.Optimizer)
@variable(модель, занимает[i in имена, j in кабинеты],
Int, lower_bound=0, upper_bound=1);
Employee experience
It is necessary to assign weighting factors for employee preferences depending on their length of service. Thus, the longer a person has been working at MathWorks, the more weight their wishes have.
The length of service of employees is distributed as follows:
-
Anna is 9 years old
-
Artyom — 2 years old
-
Alyona — 5 years old
-
Anton — 4 years old
-
Andrey — 1.5 years old
-
Anastasia is 10 years old
Based on these data, it is required to construct a normalized vector of weighting coefficients.
стаж = [9, 2, 5, 4, 1.5, 10];
весовой_вектор = стаж/sum(стаж);
Employee preferences
Let's build a preference matrix in which the rows correspond to offices, and the columns correspond to employees. Each person should be asked to rate each office on a scale so that the sum of all their grades (that is, the sum of the column) is 100. The higher the value, the more desirable this office is considered for the employee. Each person's preferences are represented as a vector column.
Анна = [1, 3, 3, 3, 10, 40, 40];
Артём = [0, 0, 0, 0, 20, 40, 40];
Алёна = [0, 0, 0, 0, 30, 40, 30];
Антон = [0, 0, 0, 10, 10, 40, 50]
Андрей = [3, 4, 1, 2, 10, 40, 40];
Анастасия = [10, 10, 10, 10, 20, 20, 20];
Each i-th element of each employee's preference vector shows how much they value the i-th office.
Thus, the final preference matrix looks like this:
матрица_предпочтений = [Анна Артём Алёна Антон Андрей Анастасия]';
Multiply the preference matrix by the weight vector to scale the columns based on seniority.
ПМ = zeros(length(имена), length(кабинеты))
for i in 1:length(имена)
for j in 1:length(кабинеты)
ПМ[i, j] = весовой_вектор[i] * матрица_предпочтений[i, j]
end
end
Target function
The goal of the task is to maximize employee satisfaction based on their seniority. Now you need to create an optimization task and include this objective function in it.
@objective(модель, Max, sum(занимает[i, j] * ПМ[findfirst(isequal(i), имена), findfirst(isequal(j), кабинеты)]
for i in имена, j in кабинеты));
Limitations
The first condition ensures that each employee gets exactly one office. Mathematically, this means that for each person, the sum of the values of a variable is занимает It must be exactly equal to one for all offices.
@constraint(модель, ограничение1[i in имена], sum(занимает[i, j] for j in кабинеты) == 1);
The second group of conditions is represented by inequalities. These restrictions ensure that there will be no more than one person in each office.
@constraint(модель, ограничение2[j in кабинеты], sum(занимает[i, j] for i in имена) <= 1);
It is required that Alyona and Anton are located in offices, the distance between which does not exceed one office. A similar condition applies to Anastasia and Andrey.
We will set up restrictions to ensure that Alyona and Anton will be no further than one office away from each other.
@constraint(модель, ограничение_Алёна_Антон_1, занимает["Алёна","Кабинет 1"] + sum(занимает["Антон", j] for j in кабинеты) - занимает["Антон","Кабинет 2"] <= 1);
@constraint(модель, ограничение_Алёна_Антон_2, занимает["Алёна","Кабинет 2"] + sum(занимает["Антон", j] for j in кабинеты) - занимает["Антон","Кабинет 1"] - занимает["Антон","Кабинет 3"] - занимает["Антон","Кабинет 5"] <= 1);
@constraint(модель, ограничение_Алёна_Антон_3, занимает["Алёна","Кабинет 3"] + sum(занимает["Антон", j] for j in кабинеты) - занимает["Антон","Кабинет 2"] - занимает["Антон","Кабинет 4"] - занимает["Антон","Кабинет 6"] <= 1);
@constraint(модель, ограничение_Алёна_Антон_4, занимает["Алёна","Кабинет 4"] + sum(занимает["Антон", j] for j in кабинеты) - занимает["Антон","Кабинет 3"] - занимает["Антон","Кабинет 7"] <= 1);
@constraint(модель, ограничение_Алёна_Антон_5, занимает["Алёна","Кабинет 5"] + sum(занимает["Антон", j] for j in кабинеты) - занимает["Антон","Кабинет 2"] - занимает["Антон","Кабинет 6"] <= 1);
@constraint(модель, ограничение_Алёна_Антон_6, занимает["Алёна","Кабинет 6"] + sum(занимает["Антон", j] for j in кабинеты) - занимает["Антон","Кабинет 3"] - занимает["Антон","Кабинет 5"] - занимает["Антон","Кабинет 7"] <= 1);
@constraint(модель, ограничение_Алёна_Антон_7, занимает["Алёна","Кабинет 7"] + sum(занимает["Антон", j] for j in кабинеты) - занимает["Антон","Кабинет 4"] - занимает["Антон","Кабинет 6"] <= 1);
Now we will set up restrictions to ensure that Anastasia and Andrey will be no further than one office away from each other.
@constraint(модель, ограничение_Андрей_Анастасия_1, занимает["Андрей","Кабинет 1"] + sum(занимает["Анастасия", j] for j in кабинеты) - занимает["Анастасия","Кабинет 2"] <= 1);
@constraint(модель, ограничение_Андрей_Анастасия_2, занимает["Андрей","Кабинет 2"] + sum(занимает["Анастасия", j] for j in кабинеты) - занимает["Анастасия","Кабинет 1"] - занимает["Анастасия","Кабинет 3"] - занимает["Анастасия","Кабинет 5"] <= 1);
@constraint(модель, ограничение_Андрей_Анастасия_3, занимает["Андрей","Кабинет 3"] + sum(занимает["Анастасия", j] for j in кабинеты) - занимает["Анастасия","Кабинет 2"] - занимает["Анастасия","Кабинет 4"] - занимает["Анастасия","Кабинет 6"] <= 1);
@constraint(модель, ограничение_Андрей_Анастасия_4, занимает["Андрей","Кабинет 4"] + sum(занимает["Анастасия", j] for j in кабинеты) - занимает["Анастасия","Кабинет 3"] - занимает["Анастасия","Кабинет 7"] <= 1);
@constraint(модель, ограничение_Андрей_Анастасия_5, занимает["Андрей","Кабинет 5"] + sum(занимает["Анастасия", j] for j in кабинеты) - занимает["Анастасия","Кабинет 2"] - занимает["Анастасия","Кабинет 6"] <= 1);
@constraint(модель, ограничение_Андрей_Анастасия_6, занимает["Андрей","Кабинет 6"] + sum(занимает["Анастасия", j] for j in кабинеты) - занимает["Анастасия","Кабинет 3"] - занимает["Анастасия","Кабинет 5"] - занимает["Анастасия","Кабинет 7"] <= 1);
@constraint(модель, ограничение_Андрей_Анастасия_7, занимает["Андрей","Кабинет 7"] + sum(занимает["Анастасия", j] for j in кабинеты) - занимает["Анастасия","Кабинет 4"] - занимает["Анастасия","Кабинет 6"] <= 1);
Decision
Let's solve the optimization problem.
optimize!(модель);
решение = value.(занимает);
значение_функции = objective_value(модель);
статус_выхода = termination_status(модель);
выходные_данные = raw_status(модель);
Visualization of the solution
We visualize the optimal distribution of office space among employees.
число_кабинетов = length(кабинеты);
кабинет = Vector{Vector{String}}(undef, число_кабинетов);
for i=1:число_кабинетов
кабинет[i] = имена[findall(x -> x > 0.5, [решение[имя, кабинеты[i]] for имя in имена])]
end
кто_в_кабинете = copy(кабинеты);
for i=1:число_кабинетов
if isempty(кабинет[i])
кто_в_кабинете[i] = " пусто ";
else
кто_в_кабинете[i] = кабинет[i][1];
end
end
officeassign(кто_в_кабинете);
значение_функции,статус_выхода,выходные_данные
Conclusion
As a result of solving the optimization problem, a distribution of cabinets was obtained that ensures the maximum value of the objective function while fully observing the specified conditions. The solution demonstrates the effectiveness of applying mathematical modeling methods to make objective management decisions in the context of conflicting criteria and limited resources. The approach used makes it possible to formalize and balance both subjective human preferences and strict operational requirements.