EN|RU

Том 22, номер 4, 2015 г., Стр. 63–79

УДК 519.2+621.391
Романова А. А.
Алгоритмы решения одной задачи построения расписания минимальной длины для двух машин

Аннотация:
Рассматривается NP-трудная задача составления расписания выполнения операций единичной длительности на двух машинах при наличии частичного порядка между операциями c критерием минимизации момента завершения всех операций. Предложен приближённый алгоритм решения задачи с гарантированной оценкой точности. Доказана полиномиальная разрешимость задачи в случае, когда каждая операция, выполняющаяся на первой машине, связана отношениями предшествования ровно с двумя операциями, выполняющимися на второй машине, разработан соответствующий алгоритм.
Ил. 9, библиогр. 8.

Ключевые слова: кросс-докинг, расписание, частичный порядок, приближённый алгоритм.

DOI: 10.17377/daio.2015.22.483

Романова Анна Анатольевна 1,2
1. Омская юридическая академия
ул. Короленко, 12, 644010 Омск, Россия
2. Омский гос. университет
пр. Мира, 55-a, 644077 Омск, Россия
e-mail: anna.a.r@bk.ru

Статья поступила 17 марта 2015 г.
Исправленный вариант — 6 мая 2015 г.

Литература

[1] Романова А. А., Чередова И. Б. Задача обработки деталей на двух станках при наличии частичного порядка между операциями // Тр. V Междунар. азиатской школы-семинара «Проблемы оптимизации сложных систем» (Бишкек, Кыргызстан, 12–22 августа, 2009 г.). Новосибирск: Ин-т вычисл. математики и мат. геофизики СО РАН, 2009. С. 119–124.

[2] Apte U. M., Viswanathan S. Effective cross docking for improving distribution efficiencies // Int. J. Logist. Res. Appl. 2000. Vol. 3, No. 3. P. 291–302.

[3] Boysen N., Fliedner M. Cross dock scheduling: Classification, literature review and research agenda // Omega. 2010. Vol. 38, No. 6. P. 413–422.

[4] Chen F., Lee Ch.-Yee. Minimizing the makespan in a two-machine cross-docking flow-shop problem // Eur. J. Oper. Res. 2009. Vol. 193, No. 1. P. 59–72.

[5] Chen F., Song K. Minimizing makespan in two-stage hybrid cross docking scheduling problem // Comput. Oper. Res. 2009. Vol. 36, No. 6. P. 2066–2073.

[6] Johnson S. M. Optimal two- and three-stage production schedules with set-up times included // Naval Res. Logist. Quart. 1954. Vol. 1, No. 1. P. 61–68.

[7] Prot D., Rapine C. Approximations for the two-machine cross-docking flow shop problem // Discrete Appl. Math. 2013. Vol. 161, No. 13–14. P. 2107–2119.

[8] Vahdani B., Zandieh M. Scheduling trucks in cross-docking systems: Robust meta-heuristics // Comput. Ind. Eng. 2010. Vol. 58, No. 1. P. 12–24.

 © Институт математики им. С. Л. Соболева, 2015