Как оптимизировать продолжительность рабочего труда до максимального использования времени с учетом ряда возможных задач - PullRequest
Новая
       9

Как оптимизировать продолжительность рабочего труда до максимального использования времени с учетом ряда возможных задач

1 голос
/ 13 июня 2019

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

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

Цель этого подхода - сделать последнего работника максимально свободным, чтобы он мог выполнять эти задачи только тогда, когда это действительно необходимо

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

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

Пока я пробовал ...

  • Проблема Job-Shop: похоже, что это не так, поскольку задачи не могут быть сгруппированы как задания, которые должны обрабатываться конкретными машинами (в нашем случае это рабочие). В моем сценарии задача может быть выполнена любым работником без предпочтений.
  • Гибкая JSP: я действительно думал, что это мой случай, так как задачи могут быть обработаны любой машиной (рабочими). Но я не мог понять, как сгруппировать мои задачи по заданиям, так как они не имеют четкой последовательности, а только в сроки.

Я тоже пробовал подходы через Google OR-Tools, но ни один из них не подходил для этой проблемы. Поскольку это выглядит как NP-полная проблема, я не думаю, что брутфорс, объединяющий задачи, чтобы найти решение, является способом, хотя набор задач и рабочих не такой большой.

Вот несколько статей, которые я прочитал, чтобы найти похожее решение:

Заранее спасибо!

1 Ответ

1 голос
/ 13 июня 2019

Изоморфные проблемы решены.Я предполагаю, что для выполнения каждой задачи требуются определенные усилия, и что работники взаимозаменяемы: например, Пол сможет завершить задачу № 17 ровно за то же время, что и Эбби.

При этом получается планированиебыть тривиальным: вычислить «самое позднее время начала» (LST) для каждой задачи, крайний срок минус требуемые усилия.Например, задание, которое занимает 4 часа и должно быть выполнено в 18:00, имеет LST 14:00.

вызывает число доступных работников N+1, где +1 является включенным.Требуется работник.

Сортировка задач по LST и назначение их N доступных работников в указанном порядке.Заполните расписание с очевидными интервалами: по мере того, как каждый работник завершает текущую задачу, назначьте следующую доступную задачу.

Если вы достигли точки в расписании, где у вас есть LST без назначенного работника, поместите его вочередь для работника по требованию, N+1.Когда вы дойдете до конца, если у работника N+1 больше задач, чем у него есть время, то у вас нет решения.

Например, при 2 + 1 работниках и задачах 

    Due  Effort  LST (computed from input)
A    5      3     2
B    3      2     1
C    1      1     0
D    5      2     3
E    4      3     1

Сортировка списка по LST 

    Due  Effort  LST
C    1      1     0
E    4      3     1
B    3      2     1
A    5      3     2
D    5      2     3

Теперь мы начинаем планировать расписание для каждого работника по часам 

    0  1  2  3  4
#1  C  B  B
#2  E  E  E

. В этот момент мы видим, что задача A должна быть запущена, нодва нормальных рабочих уже заняты.Мы должны присвоить что-то # 3.Перегрузка для промежутка задания составляет 1 час (на самом деле, это перегрузка всего расписания), поэтому поменяйте 1-часовое задание на # 3 и запустите задание «перегрузка» на его LST (это уменьшит количество возвратов и повторных запросов)пытается в сложной ситуации).

    0  1  2  3  4
#1  B  B  A  A  A
#2  E  E  E
#3  C

Теперь задача D легко назначается на # 2, и мы закончили.

Это заставляет вас двигаться?

...