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

Question

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

Проблема:

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

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

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

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

Диего

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

Редактировать Будет ли Проект полезным?

Редактировать 2 Зависимости задач / заданий НЕ являютсятребуется

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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

Посмотрите на ECLiPSe (см. http://eclipseclp.org/).

Answer 5

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