Том 18, номер 5, 2011 г., Стр. 54-79

УДК 519.7
Еремеев А. В., Коваленко Ю. В.
О задаче составления расписаний с группировкой машин по технологиям

Аннотация:
Рассматривается задача составления расписаний многопродуктового производства. Особенностью постановки является то, что каждый продукт имеет несколько технологий производства, при выполнении которых используется сразу несколько машин, работающих одновременно. Задача исследуется в двух вариантах: с возможностью прерываний выполнения технологий и без неё. Для обоих случаев построены модели частично целочисленного линейного программирования и разработаны генетические алгоритмы с равномерным кроссинговером и с оптимальной рекомбинацией. Исследована сходимость предложенных алгоритмов. Выполнены численные эксперименты, проведён анализ сложности задачи.
Ил. 1, табл. 5, библиогр. 28.

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

Еремеев Антон Валентинович ¹
Коваленко Юлия Викторовна ²
1. Омский филиал Института математики им. С. Л. Соболева СО РАН,
ул. Певцова, 13, 644099 Омск, Россия
2. Омский гос. университет им. Ф. М. Достоевского,
пр. Мира, 55а, 644077 Омск, Россия
е-mail: eremeev@ofim.oscsbras.ru, juliakoval86@mail.ru

Статья поступила 17 декабря 2010 г.
Исправленный вариант — 18 мая 2011 г.

Литература

[1] Борисовский П. А. Генетический алгоритм для одной задачи составления производственного расписания с переналадками // Тр. XIV Байкальской междунар. школы-семинара «Методы оптимизации и их приложения». — Иркутск: ИСЭМ СО РАН, 2008. — Т. 4. — С. 166–173.

[2] Гмурман В. Е. Теория вероятностей и математическая статистика: Уч. пос. — М.: Высшее образование, 2006. — 479 с.

[3] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982. — 416 с.

[4] Ильев В. П. Оценки погрешности приближённого алгоритма для задачи о раскраске графа // Тр. XIII Байкальской междунар. школы-семинара «Методы оптимизации и их приложения». — Иркутск: ИСЭМ СО РАН, 2005. — Т. 1. — С. 491–495.

[5] Китаев А., Шень А., Вялый М. Классические и квантовые вычисления. — М.: МЦНМО, ЧеРо, 1999. – 192 с.

[6] Коваленко Ю. В. Модель с непрерывным представлением времени для задачи составления расписаний многопродуктового производства // Препринт arxiv: 1105.2437 [math.OC]. — Cornell: Cornell University, 2011. — 8 с.

[7] Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечёткие системы. — М.: Горячая линия– Телеком, 2006. — 452 с.

[8] Танаев В. С., Ковалев М. Я., Шафранский Я. М. Теория расписаний. Групповые технологии. — Минск: Ин-т техн. кибернетики НАН Беларуси, 1998. — 290 с.

[9] Хачиян Л. Г. Полиномиальные алгоритмы в линейном программировании // Докл. АН СССР. — 1979. — Т. 244. — С. 1093–1096.

[10] Bianco L., Blazewicz J., Dell’Ohno P., Drozdowski M. Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors // Ann. Oper. Res. — 1995. — Vol. 58. — P. 493–517.

[11] Blazewicz J., Dell’Ohno P., Drozdowski M., Speranza M. G. Scheduling multiprocessor tasks on three dedicated processors // Inf. Process. Lett. — 1992. — Vol. 41. — P. 275–280; Corrigendum: Vol. 49. — P. 269–270.

[12] Borisovsky P. A., Dolgui A., Eremeev A. V. Genetic algorithms for a supply management problem: MIP–recombination vs greedy decoder // Eur. J. Oper. Res. — 2009. — Vol. 195, N 3. — P. 770–779.

[13] Dolgui A., Eremeev A. V., Kovalyov M. Y. Multi-product lot-sizing and scheduling on unrelated parallel machines // Res. Report No. 2007–500–011. — St.-Etienne: Ecole des Mines de St.-Etienne, 2007. — 15 p.

[14] Drozdowski M. Scheduling multiprocessor tasks — an overview // Eur. J. Oper. Res. — 1996. — Vol. 94. — P. 215–230.

[15] Feige U., Kilian J. Zero knowledge and the chromatic number // J. Comput. Syst. Sci. — 1998. — Vol. 57, N 2. — P. 187–199.

[16] Floudas C. A., Kallrath J., Pitz H. J., Shaik M. A. Production scheduling of a large-scale industrial continuous plant: short-term and medium-term scheduling // Comp. Chem. Eng. — 2009. — Vol. 33. — P. 670–686.

[17] Grötschel M., Lovasz L., Schrijver A. The ellipsoid method and its consequences in combinatorial optimization // Combinatorica. — 1981. — Vol. 1. — P. 169–197.

[18] Håstad J. Clique is hard to approximate within $n^{1 - \epsilon}$ // Acta Math. — 1999. — Vol. 182. — P. 105–142.

[19] Holland J. H. Adaptation in natural and artificial systems. — Ann Arbor: Univ. Michigan Press, 1975. — 183 p.

[20] Hoogeven J. A., van de Velde S. L., Veltman B. Complexity of scheduling multiprocessor tasks with prespecified processors allocations // Discrete Appl. Math. — 1994. — Vol. 55. — P. 259–272.

[21] Ierapetritou M. G, Floudas C. A. Effective continuous-time formulation for short-term scheduling: I. Multipurpose batch process // Ind. Eng. Chem. Res. — 1998. — Vol. 37. — P. 4341–4359.

[22] Itai A., Papadimitriou C. H., Szwarcfiter J. L. Hamilton paths in grid graphs // SIAM J. Comput. — 1982. — Vol. 11, N 4. — P. 676–686.

[23] Jansen K., Porkolab L. Preemptive scheduling with dedicated processors: applications of fractional graph coloring // J. Scheduling. — 2004. — Vol. 7, N 1. — P. 35–48.

[24] Kubale M. Preemptive versus nonpreemptive scheduling of biprocessor tasks on dedicated processors // Eur. J. Oper. Res. — 1996. — Vol. 94. — P. 242–251.

[25] Lin X., Floudas C. A., Modi S., Juhasz N. M. Continuous-time optimization approach for medium-range production scheduling of a multiproduct batch plant // Ind. Eng. Chem. Res. — 2002. — Vol. 41. — P. 3884–3906.

[26] Papadimitriou C. H. Computational complexity. — Mass.: Addison Wesley, 1994. — 540 p.

[27] Reeves C. R. Genetic algorithms for the operation researcher // IN-FORMS J. Comput. — 1997. — Vol. 9, N 3. — P. 231–250.

[28] Rudolph G. Finite Markov chain results in evolutionary computation: a tour d’horizon // Fundam. Inform. — 1998. — Vol. 35, N 1–4. — P. 67–89.