Комментарии 9
Очень познавательно, спасибо!=)
Хорошо оформленная статья, но к решению много-много вопросов.
Суть задачи: требуется определить минимально возможное время, за которое можно выполнить все работы.
А где в выводе посмотреть это самое минимально возможное время? На гитхабе вы пишете, что
Значение последней строки столбца t(rk, i) будет длиной критического пути (время выполнения всех работ для изготовления изделий).
Но это совершенно точно неправильно. Можете ввести две задачи. У первой длительность 1000 единиц, у второй 10. Предшественников нет ни у одной. Последнее значение будет 10. Правильное — 1000.
Спасибо за комментарий. Дополнила немного статью для лучшего понимания, основные моменты, которые добавила:
Граф должен быть полным (каждая вершина соединена ребром).
Вы должны знать конечную работу. Значение времени критического пути смотрится у конечной работы в столбце t(pk, i).
Также в статье написано:
Работы критического пути — это те работы, резервы времени которых нулевые (r(i) = 0).
Отвечаю на вопросы:
А где в выводе посмотреть это самое минимально возможное время?
Как раз для этого строится таблица, по которой можно проследить все подсчёты по формулам из алгоритма, можно проверить. Вы должны знать конечную работу, чтобы посмотреть в таблице время критического пути (по столбцу t(pk, i)).
Можете ввести две задачи. У первой длительность 1000 единиц, у второй 10. Предшественников нет ни у одной. Последнее значение будет 10. Правильное — 1000.
В задаче, что вы предложили граф неполный. Есть две работы (1000 и 10 единиц), которые между собой никак не связаны. Если построить таблицу по таким входным данным получится:
Резервы времени, что у первой работы, что у второй — равны нулю, значит это работы критического пути. Работы не связаны между собой, поэтому в ответе будет 1000 и 100, для первой и второй работы соответственно.
Если я не до конца ответила на вопросы, либо нужны ещё какие-то уточнения, то готова продолжить беседу :).
Давайте продолжим, если не возражаете, я по шагам буду продолжать )
Требование полноты графа, это вы конечно перестарались. В этом контексте бы и слабой связности навскидку хватило (кстати ваш алгоритм полноты не переживёт, можете проверить).
Но тогда еще нужно не забыть об ацикличности, а то возникнут проблемы
Очевидно абстрактная постановка. В реальном производстве имеют значение и другие показатели и резоны.
В частности, важно не только время операции, но и время перемещения, время на контроль, на переналадку оборудования. И например, как насчет возврата изделий на доработку после контрольной операции?
И даже если вы в своей модели учтете все возможные тайминги, то она все равно будет оторвана от реалии, так как в реальном техпроцессе возникают возмущающие воздействия, которые собственно и необходимо купировать управлением (автоматическим или ручным).
Но для начала, для понимания базового, конечно попытка годная.
Спасибо за комментарий! Согласна, в реальном производстве существует множество факторов, которые необходимо учитывать при планировании процесса производства. Моя статья была направлена на иллюстрацию решения алгоритма сетевого планирования, описательная часть которого была разработана ранее другими специалистами.
На программе, что я учусь, хотят открыть 2 новых направления (в рамках ПИШ), на которых будут дополнительно обучать прикладным задачам для производств (к слову, мне интересен другой профиль). Уверена, что ни одного алгоритма, приближенного к реальному, не будет в интернете в открытом доступе. Поэтому считаю, что для понимания основ базового алгоритма статья будет полезна :)
Мы такие алгоритмы, приближенные к реальности, писали ещё в начале 2000-х годов в специальном ПО. Я могу включить старого деда и долго вспоминать, но буду краток: следующая ступень вашего развития в этом направлении звучит как "имитационное моделирование". Софта (проприетарного) - тьма, ещё под DOS написанного.
Суть в том, что ваш алгоритм надо прогнать тысячи и миллионы раз с небольшими вариациями параметров с целью определения узких мест и наличия интересных эффектов роста очередей там, где вы никогда бы не подумали. Для оптимизации поточного массового производства нужно именно имитационное моделирование, а не только лишь разработка алгоритма.
Решаем задачу сетевого планирования с помощью Python