Автор Тема: Планирование с выравниванием по ресурсам  (Прочитано 4486 раз)

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Другое дело алгоритмы планирования. Это был уникальный случай - сменилось три разработчика, прежде чем, производство заработало так, как задумывалось. То, что видно на "экранке" - это один из первых работоспособных вариантов с массой опций. Работал медленно и ошибался. Но, для общего представления, его вполне достаточно. Материала по планированию было наработано столько, что хватило бы на десяток кандидатских диссертаций. Тема, работы на графах вообще очень интересная... если не сводить её к пресловутому "циклу Дейкстры"... :)
Это мне напомнило борьбу с MSProject. Он использовался для планирования и было большое желание от него избавиться. Я написал расчет критического пути, но оказалось, что нужно было выравнивать задачи по ресурсам.

Для тех, кто не в теме, поясню на пальцах. Предположим, для решения задачи некоего типа длительностью 1 день нужна 1 единица ресурсов, н-р, 1 человек. При планировании на какой-то день выпало 4 таких задачи. Какие-то две из четырех задач нужно откладывать на потом. Сдвинутые задачи могут начать конфликтовать по ресурсам с другими задачами, опять надо какие-то переносить на потом, и.т.д.

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

Может быть Вы или еще кто-то прокомментирует эту историю.
« Последнее редактирование: Август 27, 2012, 08:45:14 pm от Peter Almazov »

alexus

  • Гость
Re: Планирование с выравниванием по ресурсам
« Ответ #1 : Август 27, 2012, 08:46:55 pm »
Может быть Вы или еще кто-то прокомментирует эту историю.
Одно из самых простых решений - у отложенных задач повышается приоритет...

Влад Жаринов

  • Full Member
  • ***
  • Сообщений: 189
    • Просмотр профиля
Re: Планирование с выравниванием по ресурсам
« Ответ #2 : Август 29, 2012, 11:37:36 am »
Кстати, для конкретных ситуаций планирование даже формализуется. Так, в ГРАФКОНТ введена алгебра процессов для типичных случаев связи работ (в данном случае - программных задач РВ). Можно упрощать алгоритм, сохраняя его смысл (генерацию заданных сигналов в допустимые интервалы времени). Здесь, как я понимаю, управление прежде всего разомкнутое - но м.б. и замкнутым по логическим условиям...

Влад Жаринов

  • Full Member
  • ***
  • Сообщений: 189
    • Просмотр профиля
Re: Планирование с выравниванием по ресурсам
« Ответ #3 : Август 29, 2012, 05:32:07 pm »
Да. кстати. Вот это, я так понимаю, все знают?..

Влад Жаринов

  • Full Member
  • ***
  • Сообщений: 189
    • Просмотр профиля
Планирование вычислтельных ресурсов
« Ответ #4 : Сентябрь 03, 2012, 08:48:59 am »
Вот о подходе к планированию на основе числовых характеристик. Хотя предмет - машинные задачи, надо думать, немашинные как объекты планирования принципиально от них не отличаются... :)

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Планирование с выравниванием по ресурсам
« Ответ #5 : Апрель 12, 2014, 11:32:49 am »
Вот, пришлось вернуться к выравниванию ресурсов. Раньше использовался 1 ресурс на задачу, теперь потребовалось несколько. Оказалось, что полный перебор все еще работает.

Предлагаю кусочек задачи для граждан у которых "нет проблем с циклами".
Формулировка задачи совсем не сложная.
Дано:
1. Доступность ресурсов – массив с целыми числами. Ресурс – это индекс.
2. Массив задач, которые конфликтуют по ресурсам (это уже выяснено). Для каждой задачи дано время старта и длительность (все в минутах), используемые ресурсы (массив целых такой же размерности, как в п.1), ну и номер для удобства.

Нужно устранить конфликты – если задача с более старшим индексом конфликтует с предыдущими (т.е. сумма по какому-либо ресурсу превышает доступность из п. 1), то нужно сдвигать ее вправо, пока она не "впишется". Первая задача, естественно, никогда не сдвигается.
Т. е., нужно получить новые времена старта задач.

Потренироваться можно на таких данных
Доступность ресурсов: {7,10,10,16,18,13}
Задачи:
№ 7 старт=10560 длит=960 ресурсы={4, 1, 4, 3, 9, 8 }
№ 8 старт=10560 длит=960 ресурсы={5, 5, 4, 0, 9, 1 }
№ 10 старт=9600 длит=2880 ресурсы={1, 5, 4, 6, 7, 3 }
№ 11 старт=10560 длит=480 ресурсы={3, 3, 2, 4, 5, 1 }
Ответ: новые времена старта {10560, 11520, 9600, 12480 }

Если кому интересно, вся задача взята отсюда http://kisi.deu.edu.tr/guzin.kavrukkoca/BISMaster/ResourceLevelingUsingGeneticAlgorithms.pdf

Честно говоря, я не рассчитываю на ответы. Т.к. придется напрячься (мне – пришлось, но был стимул), а у каждого своих дел по горло и стимула нет.
Ну, на нет и суда нет.