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.
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:
кабинеты = ["Cabinet 1", "Cabinet 2", "Cabinet 3", "Cabinet 4", "Cabinet 5", "Cabinet 6", "Cabinet 7"];
officeassign(offices)
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:
имена = ["Anna", "Artem", "Alena", "Anton", "Andrey", "Anastasia"];
Let's create binary variables indexed by office numbers and employee names.
model = Model(HiGHS.Optimizer)
@variable(model, occupies[i in names, j in offices],
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.
Length of service = [9, 2, 5, 4, 1.5, 10];
weight_vector = length of service/sum(length of service);
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.
Anna = [1, 3, 3, 3, 10, 40, 40];
Artyom = [0, 0, 0, 0, 20, 40, 40];
Alyona = [0, 0, 0, 0, 30, 40, 30];
Anton = [0, 0, 0, 10, 10, 40, 50]
Andrew = [3, 4, 1, 2, 10, 40, 40];
Anastasia = [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.
PM = zeros(length(names), length(cabinets))
for i in 1:length(names)
for j in 1:length(cabinets)
PM[i, j] = weight_vector[i] * matrix of representations[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(model, Max, sum(occupies[i, j] * PM[findfirst(isequal(i), names), findfirst(isequal(j), cabinets)]
for I in names, j in cabinets));
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(model, restriction1[i in names], sum(occupies[i, j] for j in cabinets) == 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(model, restriction2[j in cabinets], sum(occupies[i, j] for i in names) <= 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, занимает["Alena","Cabinet 1"] + sum(занимает["Anton", j] for j in кабинеты) - занимает["Anton","Cabinet 2"] <= 1);
@constraint(модель, ограничение_Алёна_Антон_2, занимает["Alena","Cabinet 2"] + sum(занимает["Anton", j] for j in кабинеты) - занимает["Anton","Cabinet 1"] - занимает["Anton","Cabinet 3"] - занимает["Anton","Cabinet 5"] <= 1);
@constraint(модель, ограничение_Алёна_Антон_3, занимает["Alena","Cabinet 3"] + sum(занимает["Anton", j] for j in кабинеты) - занимает["Anton","Cabinet 2"] - занимает["Anton","Cabinet 4"] - занимает["Anton","Cabinet 6"] <= 1);
@constraint(модель, ограничение_Алёна_Антон_4, занимает["Alena","Cabinet 4"] + sum(занимает["Anton", j] for j in кабинеты) - занимает["Anton","Cabinet 3"] - занимает["Anton","Cabinet 7"] <= 1);
@constraint(модель, ограничение_Алёна_Антон_5, занимает["Alena","Cabinet 5"] + sum(занимает["Anton", j] for j in кабинеты) - занимает["Anton","Cabinet 2"] - занимает["Anton","Cabinet 6"] <= 1);
@constraint(модель, ограничение_Алёна_Антон_6, занимает["Alena","Cabinet 6"] + sum(занимает["Anton", j] for j in кабинеты) - занимает["Anton","Cabinet 3"] - занимает["Anton","Cabinet 5"] - занимает["Anton","Cabinet 7"] <= 1);
@constraint(модель, ограничение_Алёна_Антон_7, занимает["Alena","Cabinet 7"] + sum(занимает["Anton", j] for j in кабинеты) - занимает["Anton","Cabinet 4"] - занимает["Anton","Cabinet 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, занимает["Andrey","Cabinet 1"] + sum(занимает["Anastasia", j] for j in кабинеты) - занимает["Anastasia","Cabinet 2"] <= 1);
@constraint(модель, ограничение_Андрей_Анастасия_2, занимает["Andrey","Cabinet 2"] + sum(занимает["Anastasia", j] for j in кабинеты) - занимает["Anastasia","Cabinet 1"] - занимает["Anastasia","Cabinet 3"] - занимает["Anastasia","Cabinet 5"] <= 1);
@constraint(модель, ограничение_Андрей_Анастасия_3, занимает["Andrey","Cabinet 3"] + sum(занимает["Anastasia", j] for j in кабинеты) - занимает["Anastasia","Cabinet 2"] - занимает["Anastasia","Cabinet 4"] - занимает["Anastasia","Cabinet 6"] <= 1);
@constraint(модель, ограничение_Андрей_Анастасия_4, занимает["Andrey","Cabinet 4"] + sum(занимает["Anastasia", j] for j in кабинеты) - занимает["Anastasia","Cabinet 3"] - занимает["Anastasia","Cabinet 7"] <= 1);
@constraint(модель, ограничение_Андрей_Анастасия_5, занимает["Andrey","Cabinet 5"] + sum(занимает["Anastasia", j] for j in кабинеты) - занимает["Anastasia","Cabinet 2"] - занимает["Anastasia","Cabinet 6"] <= 1);
@constraint(модель, ограничение_Андрей_Анастасия_6, занимает["Andrey","Cabinet 6"] + sum(занимает["Anastasia", j] for j in кабинеты) - занимает["Anastasia","Cabinet 3"] - занимает["Anastasia","Cabinet 5"] - занимает["Anastasia","Cabinet 7"] <= 1);
@constraint(модель, ограничение_Андрей_Анастасия_7, занимает["Andrey","Cabinet 7"] + sum(занимает["Anastasia", j] for j in кабинеты) - занимает["Anastasia","Cabinet 4"] - занимает["Anastasia","Cabinet 6"] <= 1);
Decision
Let's solve the optimization problem.
optimize!(model);
solution = value.(occupies);
function_value = objective_value(model);
exit status_status = termination_status(model);
output data = raw_status(model);
Visualization of the solution
We visualize the optimal distribution of office space among employees.
number of classrooms = length(classrooms);
cabinet = Vector{Vector{String}}(undef, number of cabinets);
for i=1:the number of cabinets
cabinet[i] = names[findall(x -> x > 0.5, [solution[name, cabinets[i]] for name in names])]
end
who is in the classroom = copy(classrooms);
for i=1:the number of cabinets
if isempty(cabinet[i])
кто_в_кабинете[i] = " empty ";
else
who is in the study[i] = study[i][1];
end
end
officeassign(who is in the cabinet);
function_value,exit status_out_data
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.