Том 26, номер 2, 2019 г., Стр. 60-78

УДК 519.8
Кононова П. А., Кочетов Ю. А.
Алгоритм локального поиска для построения расписаний работы одного станка с переналадкой оборудования и складом

Аннотация:
Получена новая математическая модель оптимизации расписаний работы одного станка, описывающая реальное производство тротуарной плитки. Модель учитывает технологические задержки при переходе от одного типа продукции к другому, минимальные объёмы производства, разнородность заказов клиентов и наличие запасов на складе. В качестве критерия оптимизации выступает штраф за опоздание заказов относительно директивных сроков и суммарная стоимость хранения готовой продукции на складе. Построена модель частично-целочисленного линейного программирования, позволяющая решать задачи небольшой размерности. Для реальных задач месячного планирования разработан вероятностный метод локального поиска с запретами. Приводятся результаты численных экспериментов на тестовых примерах одной компании Новороссийска.
Табл. 3, ил. 1, библиогр. 25.

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

DOI: 10.33048/daio.2019.26.634

Кононова Полина Александровна ^1,2
Кочетов Юрий Андреевич ^1,2
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: pkononova@math.nsc.ru, jkochet@math.nsc.ru

Статья поступила 11 октября 2018 г.
После доработки — 4 февраля 2019 г.
Принята к публикации 27 февраля 2019 г.

Литература

[1] Давыдов И. А., Кононова П. А., Кочетов Ю. А. Локальный поиск с окрестностью экспоненциальной мощности для задачи балансировки нагрузки на серверы // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 6. С. 21–34.

[2] Давыдов И. А., Мельников А. A., Кононова П. А. Локальный поиск для задач балансировки нагрузки серверов большой размерности // Автоматика и телемеханика. 2017. № 3. С. 34–50.

[3] Кочетов Ю. А., Панин А. A., Плясунов А. В. Генетический локальный поиск и сложность аппроксимации задачи балансировки нагрузки на серверы // Автоматика и телемеханика. 2017. № 3. С. 51–62.

[4] Лавлинский С. М., Панин А. A., Плясунов А. В. Двухуровневая модель планирования государственно-частного партнерства // Автоматика и телемеханика. 2015. № 11. С. 89–103.

[5] Панин А. A., Пащенко М. Г., Плясунов А. В. Двухуровневые модели конкурентного размещения производства и ценообразования // Автоматика и телемеханика. 2014. № 4. С. 153–169.

[6] Aarts E. H. L., Korst J. H. M., van Laarhoven P. J. M. Simulated annealing // Local search in combinatorial optimization. Chichester: Wiley, 1997. P. 91–120.

[7] Allahverdi A. The third comprehensive survey on scheduling problems with setup times/costs // Eur. J. Oper. Res. 2015. Vol. 246, No. 2. P. 345–378.

[8] Bigras L.-P., Gamache M., Savard G. The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times // Discrete Optim. 2008. Vol. 5, No. 4. P. 685–699.

[9] Brimberg J., Hansen P., Mladenovic N. Attraction probabilities in variable neighborhood search // 4OR. 2010. Vol. 8, No. 2. P. 181–194.

[10] Brucker P. Scheduling algorithms. Berlin; Heidelberg: Springer, 2007.

[11] Chen B., Potts C. N., Woeginger G. J. A review of machine scheduling: Complexity, algorithms and approximability // Handbook of combinatorial optimization. Vol. 3. Dordrecht: Kluwer Acad. Publ., 1998. P. 21–169.

[12] Dolgui A., Eremeev A. V., Kovalyov M. Y., Kuznetsov P. M. Multiproduct lot sizing and scheduling on unrelated parallel machines // IIE Trans. 2010. Vol. 42, No. 7. P. 514–524.

[13] Erzin A. I., Mladenovi$\acute{c}$ N., Plotnikov R. V. Variable neighborhood search variants for min-power symmetric connectivity problem // Comput. Oper. Res. 2017. Vol. 78. P. 557–563.

[14] Erzin A. I., Plotnikov R. V. Using VNS for the optimal synthesis of the communication tree in wireless sensor networks // Electron. Notes Discret. Math. 2015. Vol. 47. P. 21–28.

[15] Glover F., Laguna M. Tabu Search. Norwell, MA: Kluwer Acad. Publ., 1997.

[16] Iellamo S., Alekseeva E. V., Chen L., Coupechoux M., Kochetov Yu. A. Competitive location in cognitive radio networks // 4OR. 2015. Vol. 13, No. 1. P. 81–110.

[17] Jackson J. R. Scheduling a production line to minimize maximum tardiness. Res. Rep. No. 43. Los Angeles: Univ. Calif., 1955.

[18] Janak S. L., Floudas Ch. A., Kallrath J., Vormbrock N. Production scheduling of a large-scale industrial batch plant. I. Short-term and medium-term scheduling // Ind. Eng. Chem. Res. 2006. Vol. 45. P. 8234–8252.

[19] Kochetov Yu. A. Facility location: discrete models and local search methods // Combinatorial optimization. Methods and applications. Amsterdam: IOS Press, 2011. P. 97–134.

[20] Kochetov Yu., Kondakov A. A. VNS matheuristic for a bin packing problem with a color constraint // Electron. Notes Discret. Math. 2017. Vol. 58. P. 39–46.

[21] Korte B. H., Vygen J. Combinatorial optimization: Theory and algorithms. New York: Springer, 2012.

[22] Mladenovic N., Brimberg J., Hansen P., Moreno-Pérez J. A. The $p$-median problem: A survey of metaheuristic approaches // Eur. J. Oper. Res. 2007. Vol. 179, No. 3. P. 927–939.

[23] Pochet Y., Wolsey L. A. Production planning by mixed integer programming. New York: Springer, 2005.

[24] Smith W. E. Various optimizers for single-stage production // Nav. Res. Logist. Q. 1956. Vol. 3, No. 1–2. P. 59–66.

[25] Talbi E.-G. Metaheuristics: From design to implementation. Hoboken, NJ: Wiley, 2009.