2
$\begingroup$

I am trying to solve this task :

There are three datasets: first data on offices in cities: each city has a certain number of offices and each office has its own capacity of employees. second data on teams and open positions in these teams. third data on candidates for positions, showing their id, city and position. we have to allocate applicants across teams and offices in such a way as to maximize the number of employees of one team located in one office together. at the same time, we have to minimize number of cases when there are less than 2 employees of a certain team in certain office

Example:

input:

city_data:

    city          office_id           capacity     
 New York           A                     3
 New York           B                     2
 New York           C                     6
 Boston             D                     2
 Boston             E                     5

team_data:

team_id         position
alpha            Manager
alpha            Manager
alpha            Engineer
alpha            Engineer
alpha            Engineer
alpha            Engineer
alpha            Designer
beta             Engineer
beta             Engineer
beta             Engineer
gamma            Designer
gamma            Engineer

employees_data:

employee_id               city                  position
1                        New York              Manager
2                        New York              Manager
3                        New York              Engineer
4                        New York              Engineer
5                        New York              Engineer
6                        New York              Engineer
7                        New York              Engineer
8                        New York              Designer
9                        New York              Designer
10                       Boston                Engineer
11                       Boston                Engineer
12                       Boston                Engineer

possible output:

team_id      employee_id          position           city            office_id
alpha            1                Manager         New York              C
alpha            2                Manager         New York              C
alpha            3                Engineer         New York             C
alpha            4                Engineer         New York             C
alpha            5                Engineer         New York             C
alpha            6                Engineer         New York             B
alpha            7                Designer         New York             B
beta             8                Engineer         Boston               E
beta             9                Engineer         Boston               E
beta             10               Engineer         Boston               E
alpha            11                Designer        New York             A
alpha            12                Engineer        New York             A

i tried to solve this way:

  1. Sort the employee_data in decreasing order of the count of employees for each position and city.
  2. For each city and position, assign the employee_id to the team_id and office_id with the maximum capacity until it reaches the capacity limit.
  3. Repeat the step 2 until all employees are assigned to the team_id and office_id.

and wrote this code:

from collections import defaultdict

def allocate_employees(city_data, team_data, employee_data):
    city_office_capacity = defaultdict(dict)
    for city, office, capacity in city_data:
        city_office_capacity[city][office] = capacity
    
    team_positions = defaultdict(list)
    for team, position in team_data:
        team_positions[team].append(position)
    
    employee_allocations = []
    for employee, city, position in employee_data:
        max_capacity = 0
        max_office = None
        for office, capacity in city_office_capacity[city].items():
            if capacity > max_capacity:
                max_capacity = capacity
                max_office = office
        city_office_capacity[city][max_office] -= 1
        for team, positions in team_positions.items():
            if position in positions:
                employee_allocations.append((team, employee, position, city, max_office))
                break
    return employee_allocations

city_data = [("New York", "A", 3), 
             ("New York", "B", 2), 
             ("New York", "C", 6), 
             ("Boston", "D", 2), 
             ("Boston", "E", 5)]

team_data = [("alpha", "Manager"), 
             ("alpha", "Manager"), 
             ("alpha", "Engineer"), 
             ("alpha", "Engineer"), 
             ("alpha", "Engineer"), 
             ("alpha", "Engineer"), 
             ("alpha", "Designer"), 
             ("beta", "Engineer"), 
             ("beta", "Engineer"), 
             ("beta", "Engineer"), 
             ("gamma", "Designer"), 
             ("gamma", "Engineer")]

employee_data = [(1, "New York", "Manager"), 
                 (2, "New York", "Manager"), 
                 (3, "New York", "Engineer"), 
                 (4, "New York", "Engineer"), 
                 (5, "New York", "Engineer"), 
                 (6, "New York", "Engineer"), 
                 (7, "New York", "Engineer"), 
                 (8, "New York", "Designer"), 
                 (9, "New York", "Designer"), 
                 (10, "Boston", "Engineer"), 
                 (11, "Boston", "Engineer"), 
                 (12, "Boston", "Engineer")]

allocate_employees(city_data, team_data, employee_data)

but i get the wrong output:

[('alpha', 1, 'Manager', 'New York', 'C'),
 ('alpha', 2, 'Manager', 'New York', 'C'),
 ('alpha', 3, 'Engineer', 'New York', 'C'),
 ('alpha', 4, 'Engineer', 'New York', 'A'),
 ('alpha', 5, 'Engineer', 'New York', 'C'),
 ('alpha', 6, 'Engineer', 'New York', 'A'),
 ('alpha', 7, 'Engineer', 'New York', 'B'),
 ('alpha', 8, 'Designer', 'New York', 'C'),
 ('alpha', 9, 'Designer', 'New York', 'A'),
 ('alpha', 10, 'Engineer', 'Boston', 'E'),
 ('alpha', 11, 'Engineer', 'Boston', 'E'),
 ('alpha', 12, 'Engineer', 'Boston', 'E')]

how could i solve it? i tried greedy algorithm here, but maybe there are better solutions using graphs for example?

$\endgroup$
3
  • 1
    $\begingroup$ Note: Has been cross-posted on operations research stackexchange: or.stackexchange.com/questions/9908/… $\endgroup$
    – student91
    Commented Feb 9, 2023 at 10:31
  • $\begingroup$ Please be precise about what it is you want to optimize. You can do this by defining a loss function, which assigns a numerical value to each potential arrangement. Something like, #(office/team pairs with fewer than two employees) - sum(largest number of teams grouped together), but maybe you want a weighted sum. Alternatively, you can say that one of the goals has priority, so you want to maximize one, and only minimize the second as a tie-breaker. $\endgroup$ Commented Feb 9, 2023 at 17:34
  • $\begingroup$ Cross posted to SO: How to solve this algorithmic task in Python? $\endgroup$ Commented Mar 7, 2023 at 12:45

0

You must log in to answer this question.