Посещая наш сайт, вы соглашаетесь с нашей политикой конфиденциальности в отношении файлов cookie, статистики отслеживания и т. д.

Главная » Вопросы и ответы

Линейное программирование для планирования рабочего времени

На чтение 5 мин Опубликовано
Содержание
  1. Вопрос или проблема
  2. Оптимизация графика работы сотрудников ресторана:
  3. Ответ или решение
  4. Проблема оптимизации расписания сотрудников ресторана
  5. Введение
  6. Данные
  7. Ограничения
  8. Модель линейного программирования
  9. Заключение

Вопрос или проблема

Оптимизация графика работы сотрудников ресторана:

Цель: Создать оптимизированный график работы сотрудников для ресторана, который минимизирует общее количество отработанных часов, при этом удовлетворяя всем требованиям по штату.

Данные:

  • Задачи: Функции ресторана, требующие кадрового обеспечения:

    • Персонал: Общие задачи ресторана, такие как обслуживание, уборка и т. д.
    • Менеджер: Дежурный менеджер, ответственный за контроль работы.

  • Требования: Количество сотрудников, необходимых для каждой задачи, по каждому часу суток, в течение 7 дней недели. Это представлено в виде словаря:

    requirements = {
    'Crew': [[0, 0, 0, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 4, 4, 4, 4, 0, 4, 8, 4, 4, 4, 0], 
              [0, 0, 0, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 6, 4, 4, 4, 4, 0, 4, 4, 4, 4, 4, 0],
              [0, 0, 0, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 0, 4, 4, 4, 4, 4, 0],
              [0, 0, 0, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 0, 4, 8, 4, 4, 4, 0],
              [0, 0, 0, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 4, 4, 4, 4, 0, 4, 4, 4, 4, 4, 0],
              [0, 0, 0, 2, 4, 4, 4, 4, 4, 4, 4, 4, 5, 6, 6, 4, 4, 4, 0, 4, 4, 4, 4, 4, 0],
              [0, 0, 0, 2, 4, 4, 4, 4, 4, 4, 4, 5, 6, 8, 7, 5, 4, 4, 0, 4, 4, 4, 4, 4, 0]], 
    'MOD': [[0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0], 
             [0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0],
             [0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0],
             [0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0],
             [0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0],
             [0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0],
             [0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0]]
}

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

    skills = {
    'Emp_159': {'Crew': 0, 'MOD': 0}, 'Emp_160': {'Crew': 0, 'MOD': 0}, 'Emp_161': {'Crew': 0, 'MOD': 0}, 
    'Emp_162': {'Crew': 0, 'MOD': 0}, 'Emp_163': {'Crew': 0, 'MOD': 0}, 'Emp_164': {'Crew': 0, 'MOD': 0}, 
    'Emp_165': {'Crew': 0, 'MOD': 0}, 'Emp_166': {'Crew': 0, 'MOD': 0}, 'Emp_167': {'Crew': 0, 'MOD': 0}, 
    'Emp_168': {'Crew': 0, 'MOD': 0}, 'Emp_169': {'Crew': 0, 'MOD': 0}, 'Emp_170': {'Crew': 0, 'MOD': 0}, 
    'Emp_171': {'Crew': 0, 'MOD': 0}, 'Emp_172': {'Crew': 0, 'MOD': 0}, 'Emp_173': {'Crew': 0, 'MOD': 0}, 
    'Emp_174': {'Crew': 0, 'MOD': 0}, 'Emp_175': {'Crew': 0, 'MOD': 0}, 'Emp_30': {'Crew': 1, 'MOD': 0}, 
    'Emp_31': {'Crew': 1, 'MOD': 0}, 'Emp_32': {'Crew': 1, 'MOD': 0}, 'Emp_33': {'Crew': 1, 'MOD': 0}, 
    'Emp_34': {'Crew': 1, 'MOD': 1}, 'Emp_35': {'Crew': 1, 'MOD': 1}, 'Emp_36': {'Crew': 1, 'MOD': 1}, 
    'Emp_37': {'Crew': 1, 'MOD': 0}, 'Emp_38': {'Crew': 1, 'MOD': 0}, 'Emp_40': {'Crew': 1, 'MOD': 0}
}

  • Тип сотрудника: Каждый сотрудник классифицируется как “Полный рабочий день” или “Неполный рабочий день”:

    employee_type = {
    'Emp_30': 'Полный рабочий день', 'Emp_160': 'Неполный рабочий день', 'Emp_161': 'Неполный рабочий день', 'Emp_163': 'Неполный рабочий день', 
    'Emp_31': 'Полный рабочий день', 'Emp_33': 'Неполный рабочий день', 'Emp_37': 'Полный рабочий день', 'Emp_35': 'Полный рабочий день', 
    'Emp_167': 'Неполный рабочий день', 'Emp_172': 'Неполный рабочий день', 'Emp_168': 'Неполный рабочий день', 'Emp_175': 'Неполный рабочий день', 
    'Emp_174': 'Неполный рабочий день', 'Emp_159': 'Неполный рабочий день', 'Emp_169': 'Неполный рабочий день', 'Emp_170': 'Неполный рабочий день', 
    'Emp_164': 'Неполный рабочий день', 'Emp_165': 'Неполный рабочий день', 'Emp_38': 'Неполный рабочий день', 'Emp_40': 'Неполный рабочий день', 
    'Emp_32': 'Неполный рабочий день', 'Emp_34': 'Полный рабочий день', 'Emp_171': 'Неполный рабочий день', 'Emp_166': 'Неполный рабочий день', 
    'Emp_162': 'Неполный рабочий день', 'Emp_173': 'Неполный рабочий день', 'Emp_36': 'Полный рабочий день'
}

Ограничения:

  1. Назначение на основе навыков: Сотрудникам следует назначать только те задачи, которые соответствуют их навыкам.
  2. Неделя отдыха: Каждый сотрудник должен иметь один выходной день в неделю.
  3. Максимальные часы: Сотрудники на полный рабочий день могут работать не более 9 часов в день, а сотрудники на неполный рабочий день – не более 5 часов в день.
  4. Единая смена: Каждый сотрудник может работать только одну смену в день.
  5. Согласованность смен: Время начала смены сотрудника должно быть согласованным на протяжении всей недели, с максимальным отклонением в 2 часа, если это абсолютно необходимо. Например, если время начала – 9:00, рабочие часы на протяжении недели могут варьироваться от 8:00 до 10:00, допускается отклонение на 2 часа.
  6. Выполнение требований: График должен стремиться максимально соответствовать требованиям по штату по часам для каждой задачи. Стремитесь назначить хотя бы одного сотрудника там, где есть требование по штату, и если идеальное распределение невозможно, стремитесь к равному соотношению распределения сотрудников.

Цель: Цель заключается в создании графика работы сотрудников, который соответствует вышеуказанным ограничениям, минимизируя общее количество отработанных часов всеми сотрудниками.

Мой вопрос/проблема
При выполнении следующего кода я замечаю, что модель стремится к глобальной оптимизации. И в этом процессе происходит следующее:

  • Некоторые требования остаются полностью невыполненными, то есть ни один сотрудник не назначен на конкретную задачу в определенный час.

Что я хочу, так это чтобы хотя бы 1 сотрудник был назначен там, где есть требование, но в то же время модель должна стремиться к общей оптимизации.

import pulp

# Создание модели
model = pulp.LpProblem("Weekly_Employee_Scheduling", pulp.LpMinimize)

# Переменные решения
X = pulp.LpVariable.dicts("assign", 
                          [(i, j, d, h) for i in employees for j in tasks for d in days for h in hours],
                          cat="Binary")
Z = pulp.LpVariable.dicts("shift_start", 
                          [(i, d, h) for i in employees for d in days for h in hours],
                          cat="Binary")
Y = pulp.LpVariable.dicts("work_day", 
                          [(i, d) for i in employees for d in days],
                          cat="Binary") 

# Переменные предпочитаемого времени начала
S = pulp.LpVariable.dicts("Preferred_Start_Time", 
                          [(i, h) for i in employees for h in hours], 
                          cat="Binary")

# Переменные для гибкости требований
slack_req = pulp.LpVariable.dicts("Slack_Req", [(j, d, h)
                                                for j in tasks
                                                for d in days
                                                for h in hours], lowBound=0)

# Определение коэффициентов штрафа
TASK_PENALTY = 200

# Целевая функция
model += pulp.lpSum(X[i,j,d,h] for i in employees for j in tasks for d in days for h in hours) + \
        TASK_PENALTY * pulp.lpSum(slack_req.values())

# Ограничения
for j in tasks:
    for d in days:
        for h in hours:
            model += pulp.lpSum(X[i, j, d, h] for i in employees) + slack_req[(j, d, h)]  >= requirements[j][d][h]

#навыки      
for i in employees:
    for j in tasks:
        for d in days:
            for h in hours:
                model += X[i,j,d,h] <= skill[i][j]

# Сотрудник может работать в любые 4 дня из первых 5, т.е. выходные должны быть между понедельником и пятницей.
for i in employees:
    model += pulp.lpSum(Y[i,d] for d in days[:-2]) <= 4

# Каждый сотрудник может начать только одну смену в день
for i in employees:
    for d in days:
        model += pulp.lpSum(Z[i,d,h] for h in hours) <= Y[i,d]

# Каждый сотрудник имеет только одно предпочитаемое время начала
for i in employees:
    model += pulp.lpSum(S[i,h] for h in hours) <= 1

# Связь начала смены с предпочитаемым временем начала с допустимым отклонением
for i in employees:
    for d in days:
        for h in hours:
            model += Z[i,d,h] <= pulp.lpSum(S[i,h_flex] for h_flex in range(max(0, h-2), min(len(hours), h+3)))

# Ограничение непрерывности
for i in employees:
    for d in days:
        for h in hours:
            if h == 0:
                model += pulp.lpSum(X[i,j,d,h] for j in tasks) <= Z[i,d,h]
            else:
                model += pulp.lpSum(X[i,j,d,h] - X[i,j,d,h-1] for j in tasks) <= Z[i,d,h]

# Максимальные рабочие часы в день 
for i in employees:
    for d in days:
        if emp_type[i] == 'Неполный рабочий день':
            model += pulp.lpSum(X[i,j,d,h] for j in tasks for h in hours) <= 5
        else:
            model += pulp.lpSum(X[i,j,d,h] for j in tasks for h in hours) <= 9

# Каждый сотрудник может выполнять до 1 задачи каждый час
for i in employees:
    for d in days:
        for h in hours:
            model += pulp.lpSum(X[i,j,d,h] for j in tasks) <= 1

# Решение проблемы
model.solve(pulp.PULP_CBC_CMD(timeLimit=30))

Ответ или решение

Проблема оптимизации расписания сотрудников ресторана

Введение

Оптимизация расписания сотрудников является важной задачей для ресторанов, так как она позволяет минимизировать затраты на рабочую силу, одновременно удовлетворяя потребности в staffing в определённое время. В данном проекте мы разработаем модель линейного программирования для оптимизации расписания сотрудников ресторана на основе данных о рабочих часах, необходимых задачах и навыках сотрудников. Основная цель — минимизация общего количества рабочих часов сотрудников, соблюдая все заданные ограничения.

Данные

  1. Задачи:

    • Crew: Общие ресторанные задачи, такие как обслуживание, уборка и т.д.
    • MOD: Менеджер на дежурстве, ответственный за руководство операциями.

  2. Требования (количество сотрудников для выполнения каждой задачи в каждый час в течение недели):

    requirements = {
   'Crew': [[0, 0, 0, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 4, 4, 4, 4, 0, 4, 8, 4, 4, 4, 0], 
             ...],
   'MOD': [[0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0], 
            ...]
}

  3. Навыки сотрудников:

    skills = {
   'Emp_159': {'Crew': 0, 'MOD': 0}, 
   'Emp_160': {'Crew': 0, 'MOD': 0}, 
   ...
   'Emp_34': {'Crew': 1, 'MOD': 1}, 
   ...
}
  4. Типы сотрудников: 
    employee_type = {
   'Emp_30': 'Full Time', 
   'Emp_160': 'Part Time', 
   ...
   'Emp_36': 'Full Time'
}

Ограничения

  1. Назначение по навыкам: Сотрудники должны выполнять только задачи, соответствующие их навыкам.
  2. Выходной день: У каждого сотрудника должен быть один выходной день в неделю.
  3. Максимальные часы: Полные рабочие сотрудники могут работать до 9 часов в день, а неполные — до 5 часов.
  4. Единственный сменный график: Каждый сотрудник может работать только одну смену в день.
  5. Консистентность смены: Время начала смены должно оставаться практически неизменным в течение недели с допустимым отклонением до 2 часов.
  6. Выполнение требований: Расписание должно стремиться к полному удовлетворению часовых потребностей для каждой задачи.

Модель линейного программирования

Ниже приводится реализация модели с использованием библиотеки PuLP в Python.

import pulp

# Создание модели
model = pulp.LpProblem("Weekly_Employee_Scheduling", pulp.LpMinimize)

# Переменные решения
X = pulp.LpVariable.dicts("assign", 
                           [(i, j, d, h) for i in employees for j in tasks for d in days for h in hours],
                           cat="Binary")
Y = pulp.LpVariable.dicts("work_day", 
                           [(i, d) for i in employees for d in days],
                           cat="Binary")

# Целевая функция: минимизация общего количества рабочих часов
model += pulp.lpSum(X[i,j,d,h] for i in employees for j in tasks for d in days for h in hours)

# Ограничения по требованиям
for j in tasks:
    for d in days:
        for h in hours:
            model += pulp.lpSum(X[i, j, d, h] for i in employees) >= requirements[j][d][h]

# Ограничения по навыкам
for i in employees:
    for j in tasks:
        for d in days:
            for h in hours:
                model += X[i,j,d,h] <= skills[i][j]

# Ограничение на выходной день
for i in employees:
    model += pulp.lpSum(Y[i,d] for d in days) <= 6  # 6 рабочих дней

# Максимальное количество часов в день
for i in employees:
    for d in days:
        if employee_type[i] == 'Part Time':
            model += pulp.lpSum(X[i,j,d,h] for j in tasks for h in hours) <= 5
        else:
            model += pulp.lpSum(X[i,j,d,h] for j in tasks for h in hours) <= 9

# Смена может начинаться только в одном часу
for i in employees:
    for d in days:
        model += pulp.lpSum(X[i,j,d,h] for j in tasks for h in hours) <= 1

# Решение проблемы
model.solve(pulp.PULP_CBC_CMD(timeLimit=30))

# Вывод результата
for i in employees:
    for d in days:
        for h in hours:
            if X[i,j,d,h].varValue > 0:  # Если есть назначение
                print(f"Employee {i} assigned to {j} on {d} at {h}")

Заключение

Предложенная модель позволяет оптимально распределять рабочие часы сотрудников в ресторане, соблюдая все установленные ограничения. Гибкая настройка целевой функции и ограничений поможет обеспечить не только минимизацию затрат, но и максимальное качество услуг за счёт полного покрытия потребностей в staffing.

linear-programming optimization pulp scheduled-tasks
Оцените материал
Добавить комментарий

Капча загружается...

© 2024 IZ6.RU
*В материалах сайта упоминаются социальные сети Фейсбук / Инстаграм, принадлежащие Meta Platforms Inc., деятельность которой запрещена на территории РФ в части реализации данных социальных сетей на основании осуществления ею экстремистской деятельности