Рецензия на работу Новый алгоритм решения двухмашинной задачи open shop и его приложение к одной задаче маршрутизации

Рецензия на работу:

Новый алгоритм решения двухмашинной задачи open shop и его приложение к одной задаче маршрутизации

Вуз:

Общий комментарий к рецензии:

Рассматриваемая в работе двухмашинная задача орел shop была сформулирована и решена в статье Гонзалеза и Сани в 1976. В этой задаче требуется составить кратчайшее расписание выполнения операций множества работ двумя машинами: каждая машина выполняет по одной операции для каждой работы, время выполнения известно для каждой операции, при этом порядок операций не задан, но операции одной машины или одной работы не могут выполняться одновременно. Для этой задачи было доказано, что длина оптимального расписания совпадает с тривиальной нижней оценкой и может быть построено за линейное от числа работ время. В алгоритме Гонзалеза-Сани множество работ разбивается на два подмножества (в зависимости от того, операция какой из машин имеет большую длительность), и операции работ каждого из подмножеств (за исключением так называемой диагональной работы) выполняются единым блоком — в любом порядке, но при этом подмножества не перемешиваются. Известны и другие алгоритмы решения данной задачи. Например, Пинедо и Шраге (1982) предложили, по сути, жадный алгоритм с одним дополнительным условием, который гарантирует построение оптимального расписания для двухмашинной задачи ореn shop с такой же линейной трудоемкостью. Другие известные алгоритмы решения двухмашинной задачи орел shop были предложены де Верра (1989) и Сопером (2013). В квалификационной работе А. Храмовой предлагается новый алгоритм решения этой классической задачи. Он тоже имеет линейную трудоемкость, однако позволяет выполнять операции каждой машины в почти произвольном порядке (без разбиения на два подмножества). Следует отметить, что подобным свойством обладает также и расписание, получаемое алгоритмом Сопера, однако одним из важных преимуществ алгоритма Храмовой является существенная простота его описании и доказательства оптимальности получаемого решения. Другое важное преимущество заключается в возможности применить этот алгоритм к решению существенно более общей постановки задачи: ореn shop с маршрутизацией, нефиксированной базой и независимыми временами перемещения (при условии, что нам известен кратчайший обход транспортной сети). В этой задаче неподвижные работы расположены в узлах транспортной сети, заданной реберно-взвешенным связным графом, а мобильные машины перемещаются по сети, выполняя операции работ в рамках ограничений классической задачи ореn shop. При этом машины начинают и заканчивают движение в одном и том же узле, называемом базой. База выбирается при составлении расписания. Следует отметить, что в случае, когда база задана изначально, задача является NР-трудной даже в случае, когда времена перемещения машин одинаковы и транспортная сеть состоит всего из двух узлов (включая базу). Для задачи с выбираемой базой известно, что она полиномиалыно разрешима в случае древесной структуры транспортной сети, но до сих пор не было известно, является ли задача в такой постановке полиномиально разрешимой в случае, когда структура сети произволная, но нам известен кратчайший ее обход. Алгоритм Храмовой ставит точку в этом вопросе: задача с выбираемой базой и известным кратчайшим обходом разрешима за линейное время. Квалификационная работа безусловно заслуживает оценки "отлично", а ее автору я даю рекомендацию на поступление в аспирантуру.

Автор рецензии:

18.84

Антонина Храмова

Скачать - 0 байт