Сортировка задач для назначения

У меня проблема, не знаю с чего начать. Буду очень признателен за помощь.

Проблема:

У меня есть несколько задач T, которые должны быть выполнены за D дней всего одним сотрудником (давайте забудем прямо сейчас об использовании нескольких ресурсов). Каждое задание можно выполнять несколько раз (не все задания можно выполнять постоянно). например: если мой сотрудник начинает работать в 8 часов, и одной задачей является «позвонить клиенту». Может быть, клиентский офис открывается в 9 часов.

Также у каждой задачи есть продолжительность (действительно оцененная). Предполагается, что дней D достаточно, чтобы выполнить все задания.

Я должен отсортировать задачи сотруднику. например: в понедельник в 8:00 выполнить задание 7, затем в 9:30 начать с задания 2. В примере продолжительность задания 7 будет 1,5 часа.

Спасибо за помощь!

Диего

PD: Если у кого-то есть способ сделать это, и это не алгоритм, неважно, ответьте, и я сумею придумать алгоритм. Я просто не знаю, как справиться с проблемой.

Изменить Будет ли Project полезен?

Редактировать 2. Зависимость между задачами и заданиями НЕ требуется.


task scheduled-tasks algorithm variable-assignment
person Diego    schedule 12.11.2010    source источник
comment
Это домашнее задание? Пахнет домашней работой.   -  person Asaph    schedule 12.11.2010
comment
Нет, это небольшая часть приложения для клиента компании, в которой я работаю.   -  person Diego    schedule 12.11.2010

Ответы (5)


arrow_upward
2
arrow_downward

Если это «небольшая часть приложения», вы можете обсудить это с клиентом: Расписание работы магазина является NP-complete (вульго: становится очень сложно очень быстро с увеличением сложности ).
Несколько моментов для размышления:

  • вам нужно присвоить дням какую-то «мощность», отмечая временные интервалы, когда возможно выполнение какой-либо задачи (начало и окончание работы вашего сотрудника, часы работы других офисов и т. д.)
  • вам нужно сообщить различным задачам (или рабочим местам, как их называют), какие способности они требуют и как долго: необходимые инструменты, люди, которых нужно охватить и т. д.
  • вам может понадобиться какая-то направленная связь между, скажем, заданием 17 («позвонить в офис XYZ и запросить смету») и заданием 18 («переслать смету начальнику»): задание 17 должно быть выполнено до того, как можно будет начать задание 18. .

Если вы погуглите «расписание работы магазина», вы наткнетесь на больше научных работ, чем когда-либо захотите прочитать для «маленькой части приложения»…

(Раскрытие информации: я работаю в компании, которая предлагает разные инструменты для выполнения подобных задач.)

person Christian Severin    schedule 12.11.2010
comment
Очень полезно. Прямо сейчас, как я сказал в некоторых других комментариях (я добавлю это в вопрос), зависимость рабочих мест не требуется. Переговоры не проблема, очень хороший клиент и будет платить за отработанный час. - person Diego; 12.11.2010

arrow_upward
0
arrow_downward

Ваша проблема является частью проблемы исследования операций. Эта тема массово изучена и простого алгоритма от этого нет. Такие задачи планирования обычно не полиномиальны, поэтому в основном вам нужно пробовать все комбинации, но вы можете отключиться, когда ограничение нарушено. То есть нет необходимости пробовать все комбинации, начиная со звонка клиенту в 8:00, если вы знаете, что не сможете сделать это раньше 9:00.

Так что погуглите про исследование операций и алгоритмы программирования с ограничениями и комбинаторную оптимизацию.

person mb14    schedule 12.11.2010

arrow_upward
0
arrow_downward

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

  • количество участников (в настоящее время всегда 1, но если это может измениться, вам нужно подумать об этом заранее)
  • периоды времени, в течение которых задача может быть выполнена (текущее время дня, но это также может быть день недели или даже день месяца)
  • у участников могут быть свои требования (например, рабочее время, но может быть и что-то большее)
  • задача может зависеть от какой-либо другой задачи или задач, которые должны быть выполнены в первую очередь

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

person Dialecticus    schedule 12.11.2010
comment
Спасибо за ответ. На данный момент требования к приложению такие же, как я описал выше. Количество участников всегда будет 1, потому что задача назначается сотруднику вручную. Периоды времени: например, текущее время дня, это также может быть день недели или день месяца, как вы сказали. У сотрудников сейчас только два требования: рабочее время и не выполнять 2 задачи одновременно. Такс зависимости не является требованием. - person Diego; 12.11.2010
comment
Что ж, тогда все сводится к тому, чтобы попытаться удовлетворить одно требование за раз. Возможно, вам поможет эта статья: en.wikipedia.org/wiki/Job_shop_scheduling - person Dialecticus; 12.11.2010

arrow_upward
0
arrow_downward

Вы можете решить такие проблемы, используя программирование с ограничениями, при условии, что количество элементов не слишком велико.

Взгляните на ECLiPSe (см. http://eclipseclp.org/).

person Patrick    schedule 12.11.2010

arrow_upward
0
arrow_downward

Вот еще одна библиотека для подобных задач: Drools Planner (с открытым исходным кодом, java ).

Обратите внимание, что он решает все требования (= ограничения) вместе, потому что, особенно если у вас есть жесткие и мягкие ограничения, вы обнаружите, что обычно можно решить все жесткие ограничения, но невозможно решить все мягкие ограничения (вы все еще хотите минимизировать их как можно больше).

person Geoffrey De Smet    schedule 23.12.2010