В исследовании операций , то makespan проекта является расстоянием во время , которое проходит от начала работы до конца. Этот тип многорежимной задачи планирования проекта с ограниченными ресурсами (MRCPSP) направлен на создание кратчайшего логического расписания проекта за счет эффективного использования ресурсов проекта, добавления минимального количества дополнительных ресурсов, насколько это возможно, для достижения минимального времени выполнения. [1] Этот термин обычно используется в контексте планирования .
Пример
Это сложный проект, состоящий из нескольких подзадач. Мы хотим поручать работникам такие задачи, чтобы проект завершился в кратчайшие сроки. В качестве примера предположим, что «проект» состоит в том, чтобы накормить коз. Нужно кормить трех коз, один ребенок может кормить только одну козу за раз, и есть двое детей, которые могут их кормить: Шмуэль кормит каждую козу за 10 минут, а Шифра кормит каждую козу за 12 минут. Возможны несколько расписаний:
- Если мы позволим Шмуэлю накормить всех коз, то время приготовления будет 30 (3 × 10 для Шмуэля, 0 для Шифры);
- Если мы позволим Шифре кормить одного козла и Шмуэля двух коз, то время приготовления будет 20 (2 × 10 для Шмуэля, 12 для Шифры, работающей рядом и параллельно с Шмуэлем);
- Если мы позволим Шифре кормить двух коз и Шмуэля одну козу, то время приготовления будет 24 (2 × 12 для Шифры, 10 для Самуила, работающего рядом и параллельно с Шифрой);
- Если мы позволим Шифре накормить всех коз, то время приготовления будет 36 (3 × 12 для Шифры, 0 для Шмуэля).
Таким образом, в этом случае второе расписание достигает самого короткого промежутка времени, равного 20.
Типы задач минимизации рабочего времени
- Планирование цеха работы - есть n работ и m одинаковых станций. Каждое задание должно выполняться на одной станции. Обычно это рассматривается как онлайн-проблема.
- Планирование открытых магазинов - есть n вакансий и m разных станций. Каждое задание должно проводить некоторое время на каждой станции в свободном порядке.
- Планирование поточного цеха - есть n работ и m различных станций. Каждое задание должно проводить некоторое время на каждой станции в заранее определенном порядке.
- Справедливая минимизация времени выполнения - при назначении задач агентам требуется как минимизировать время выполнения, так и избежать зависти. Если самый быстрый работник получает работу, он должен получать компенсацию за его дополнительные усилия. Муалем представляет общую основу для решения задач оптимизации с гарантией отсутствия зависти с использованием денежных выплат. [2]
Рекомендации
- ^ Процедура решения для упреждающей задачи планирования многорежимного проекта с возможностью изменения режима на возобновление , Афшар-Наджафи, Б., в Прикладных вычислениях и информатике (2014)
- ^ Mu'alem A (2014). «Ярмарка по замыслу: многомерные механизмы без зависти». Игры и экономическое поведение . 88 : 29–46. DOI : 10.1016 / j.geb.2014.08.001 .