Создать распределение доступных значений - Python

Question

Я надеюсь создать дистрибутив , который отображает время, когда сотрудник доступен для работы. Аналогично этому показателю, который находится по этой ссылке штатное расписание .

Чтобы добиться этого, я создал staff_availability_df, который содержит количество сотрудников, которых можно выбрать, который находится в столбце ['Person']. min - max часов, которые они могут работать, сколько им платят, помечены как таковые. Доступное время, которое они могут работать, разделено на часы ['Availability_Hr'], которые представляют время, которое они могут работать, в часах. Итак, первый человек - '8-18', то есть 8:00:00am - 18:00:00pm. ['Availability_15min_Seg'] по сути то же самое, но часы разделены на 4 сегмента. Таким образом, первый человек - '1-41', который снова 8:00:00am - 18:00:00pm.

Примечание: стандартная смена работает между 8:00:00am - 3:30:00am, то есть около 20 часов.

staff_requirements_df отображает Time на протяжении всей смены и необходимое People мне нужно.

import pandas as pd
import matplotlib.pyplot as plt
import matplotlib.dates as dates

#This is the employee availability:
staff_availability = pd.DataFrame({
    'Person' : ['C1','C2','C3','C4','C5','C6','C7','C8','C9','C10','C11'],                 
    'MinHours' : [5,5,5,5,5,5,5,5,5,5,5],    
    'MaxHours' : [10,10,10,10,10,10,10,10,10,10,10],                 
    'HourlyWage' : [26,26,26,26,26,26,26,26,26,26,26],  
    'Availability_Hr' : ['8-18','8-18','8-18','9-18','9-18','9-18','12-1','12-1','17-3','17-3','17-3'],                              
    'Availability_15min_Seg' : ['1-41','1-41','1-41','5-41','5-41','5-41','17-69','17-69','37-79','37-79','37-79'],                              
    }) 

#These are the staffing requirements:
staffing_requirements = pd.DataFrame({
    'Time' : ['0/1/1900 8:00:00','0/1/1900 9:59:00','0/1/1900 10:00:00','0/1/1900 12:29:00','0/1/1900 12:30:00','0/1/1900 13:00:00','0/1/1900 13:02:00','0/1/1900 13:15:00','0/1/1900 13:20:00','0/1/1900 18:10:00','0/1/1900 18:15:00','0/1/1900 18:20:00','0/1/1900 18:25:00','0/1/1900 18:45:00','0/1/1900 18:50:00','0/1/1900 19:05:00','0/1/1900 19:07:00','0/1/1900 21:57:00','0/1/1900 22:00:00','0/1/1900 22:30:00','0/1/1900 22:35:00','1/1/1900 3:00:00','1/1/1900 3:05:00','1/1/1900 3:20:00','1/1/1900 3:25:00'],                 
    'People' : [1,1,2,2,3,3,2,2,3,3,4,4,3,3,2,2,3,3,4,4,3,3,2,2,1],                      
     })

Я экспортировал потребности в персонале в 15-минутных сегментах, которые происходят между 8:00:00am - 3:30:00am, используя следующие функции. Каждые 15 минут назначаются на string 'T'. Так T1 = 8:00:00am и T79 = 3:00:00am

staffing_requirements['Time'] = ['/'.join([str(int(x.split('/')[0])+1)] + x.split('/')[1:]) for x in staffing_requirements['Time']]
staffing_requirements['Time'] = pd.to_datetime(staffing_requirements['Time'], format='%d/%m/%Y %H:%M:%S')
formatter = dates.DateFormatter('%Y-%m-%d %H:%M:%S') 

staffing_requirements = staffing_requirements.groupby(pd.Grouper(freq='15T',key='Time'))['People'].max().ffill()
staffing_requirements = staffing_requirements.reset_index(level=['Time'])

staffing_requirements.insert(2, 'T', range(1, 1 + len(staffing_requirements)))
staffing_requirements['T'] = 'T' + staffing_requirements['T'].astype(str)

st_req = staffing_requirements['People'].tolist()

[1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 4.0, 4.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 3.0, 2.0]

Я надеюсь использовать эти функции для создания linear programming matrix, который возвращает распределение времени, когда каждый сотрудник доступен для работы. Но я надеюсь использовать 15-минутные сегменты, а также часы. например Примечание. Этот экспорт будет расширен до 3:30am. Таким образом, он будет содержать 79 сегментов.

Примечание: для ясности. Я надеюсь вернуть график распространения, чтобы его можно было использовать в будущем. Не просто фигура.

Есть несколько сотрудников, доступных пример 1 пример 2 подходит с использованием mixed-integer linear programming, но они используют программное обеспечение с закрытым исходным кодом. Я надеюсь перевести это на Python.

Answer 1

Это действительно отличная работа для целочисленного программирования;вы можете использовать pulp, который вам сначала нужно будет установить через командную строку, например pip install pulp

Манипулирование данными, чтобы настроить себя на успех

Затем сначала убедитесь, что ваш DataFrames находятся в оптимальной форме, поэтому мы можем приступить к решению проблемы:

# Since timeslots for staffing start counting at 1, also make the
# DataFrame index start counting at 1
staffing_requirements.index = range(1, len(staffing_requirements) + 1) 
print(staffing_requirements.tail())

staff_availability.set_index('Person')

staff_costs = staff_availability.set_index('Person')[['MinHours', 'MaxHours', 'HourlyWage']]
availability = staff_availability.set_index('Person')[['Availability_15min_Seg']]
availability[['first_15min', 'last_15min']] =  availability['Availability_15min_Seg'].str.split('-', expand=True).astype(int)

availability_per_member =  [pd.DataFrame(1, columns=[idx], index=range(row['first_15min'], row['last_15min']+1))
 for idx, row in availability.iterrows()]

availability_per_member = pd.concat(availability_per_member, axis='columns').fillna(0).astype(int).stack()
availability_per_member.index.names = ['Timeslot', 'Person']
availability_per_member = (availability_per_member.to_frame()
                            .join(staff_costs[['HourlyWage']])
                            .rename(columns={0: 'Available'}))

, где availability_per_member теперь является MultiIndex DataFrame, в котором есть один ряд на человека на временной интервал, что указывает на его / ее доступность и заработную плату:

#                 Available  HourlyWage
#Timeslot Person                       
#1        C1              1          26
#         C2              1          26
#         C3              1          26
#         C4              0          26
#         C5              0          26

Кроме того, мы немного изменили реквизиты, чтобы проблема была фактически решаемой;см. приложение о том, почему это необходимо

import numpy as np
np.random.seed(42)
staffing_requirements['People'] = np.random.randint(1, 4, size=len(staffing_requirements))
staff_costs['MinHours'] = 3

Решить проблему целочисленного программирования с помощью pulp

Теперь мы можем заставить работать целлюлозу: поставьте задачу с целью минимизациизатраты и добавление ограничений, которые вы упомянули один за другим, см. в комментарии к коду.staffed - это теперь словарь целлюлозы, в котором указано, работает ли человек в определенном временном интервале (0 или 1).

import pulp
prob = pulp.LpProblem('CreateStaffing', pulp.LpMinimize) # Minimize costs

timeslots = staffing_requirements.index
persons = availability_per_member.index.levels[1]

# A member is either staffed or is not at a certain timeslot
staffed = pulp.LpVariable.dicts("staffed",
                                   ((timeslot, staffmember) for timeslot, staffmember 
                                    in availability_per_member.index),
                                     lowBound=0,
                                     cat='Binary')

# Objective = cost (= sum of hourly wages)                              
prob += pulp.lpSum(
    [staffed[timeslot, staffmember] * availability_per_member.loc[(timeslot, staffmember), 'HourlyWage'] 
    for timeslot, staffmember in availability_per_member.index]
)

# Staff the right number of people
for timeslot in timeslots:
    prob += (sum([staffed[(timeslot, person)] for person in persons]) 
    == staffing_requirements.loc[timeslot, 'People'])


# Do not staff unavailable persons
for timeslot in timeslots:
    for person in persons:
        if availability_per_member.loc[(timeslot, person), 'Available'] == 0:
            prob += staffed[timeslot, person] == 0

# Do not underemploy people
for person in persons:
    prob += (sum([staffed[(timeslot, person)] for timeslot in timeslots])
    >= staff_costs.loc[person, 'MinHours']*4) # timeslot is 15 minutes => 4 timeslots = hour

# Do not overemploy people
for person in persons:
    prob += (sum([staffed[(timeslot, person)] for timeslot in timeslots])
    <= staff_costs.loc[person, 'MaxHours']*4) # timeslot is 15 minutes => 4 timeslots = hour

. Затем необходимо разрешить pulp задачу:

prob.solve()
print(pulp.LpStatus[prob.status])

output = []
for timeslot, staffmember in staffed:
    var_output = {
        'Timeslot': timeslot,
        'Staffmember': staffmember,
        'Staffed': staffed[(timeslot, staffmember)].varValue,
    }
    output.append(var_output)
output_df = pd.DataFrame.from_records(output)#.sort_values(['timeslot', 'staffmember'])
output_df.set_index(['Timeslot', 'Staffmember'], inplace=True)
if pulp.LpStatus[prob.status] == 'Optimal':
    print(output_df)

Теперь будет возвращаться фрейм данных output_df, который в каждом временном интервале и человеке содержит данные о том, укомплектованы ли они персоналом:

#                      Staffed
#Timeslot Staffmember         
#1        C1               1.0
#         C2               1.0
#         C3               1.0
#         C4               0.0
#         C5               0.0
#         C6               0.0
#         C7               0.0
#         C8               0.0
#         C9               0.0
#         C10              0.0
#         C11              0.0
#2        C1               1.0
#         C2               1.0

Я адаптировал код http://benalexkeen.com/linear-programming-with-python-and-pulp-part-5/ это отличный учебник по целлюлозному и линейному программированию, поэтому обязательно ознакомьтесь с ним.

Приложение: ваши требования неосуществимы.

С вашими условиями это действительно вернет 'Infeasible',Легко понять, почему это:
Вы видите, что требуется больше сотрудников, чем доступно в последние несколько временных интервалов.Этот сюжет был создан:

fig, ax = plt.subplots()
staffing_requirements.plot(y='People', ax=ax, label='Required', drawstyle='steps-mid')
availability_per_member.groupby(level='Timeslot')['Available'].sum().plot(ax=ax, 
                               label='Available', drawstyle='steps-mid')
plt.legend()

Answer 2

Сверху моей головы, жадный алгоритм может работать. Выберите опцию, которая максимально увеличивает вашу функцию оптимизации и т. Д .; если для следующего шага нет доступных вариантов, вернитесь назад и выберите следующий лучший вариант и т. д.

Как объяснено в ссылке, насколько оптимальным было бы найденное решение, сильно зависит от вида функции оптимизации.