vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"vestifm-256Research ArticleИНФОРМАТИКАINFORMATICSОПТИМИЗАЦИЯ ВЫПУСКА КОМПЛЕКТОВ ИЗДЕЛИЙ И ИНТЕНСИВНОСТЕЙ ИХ ИЗГОТОВЛЕНИЯ В УСЛОВИЯХ СЛУЧАЙНОГО СПРОСАOPTIMIZING THE OUTPUT OF PRODUCT BATCHES AND INTENSITY OF THEIR MANUFACTURE UNDER RANDOM DEMANDЛевинГ. М.LevinG. M.

доктор технических наук, главный научный сотрудник лаборатории исследования операций

D. Sc. (Engineering), Principle Researcher of the Operational Research Laboratory

levin@newman.bas-net.byРозинБ. М.RozinB. M.

кандидат технических наук, ведущий научный сотрудник лаборатории исследования операций

Ph. D. (Engineering), Leading Researcher of the Operational Research Laboratory

ozin@newman.bas-net.byОбъединенный институт проблем информатики Национальной академии наук БеларусиUnited Institute of Informatics Problems of the National Academy of Sciences of Belarus20170608201702110118Copyright © Левин Г.М., Розин Б.М., 20172017Левин Г.М., Розин Б.М.Levin G.M., Rozin B.M.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/256

Рассматривается задача оптимизации на ряде временных интервалов программы выпуска производственной линией комплектов изделий нескольких наименований и интенсивностей их изготовления. Линия состоит из ряда линейно упорядоченных рабочих позиций без буферов. Заготовки из входной последовательности, состоящей из циклически повторяющихся идентичных подпоследовательностей (комплектов), обрабатываются последовательно одна за другой на каждой рабочей позиции линии в порядке их расположения, и в каждый момент времени на каждой позиции обрабатывается только одна заготовка. Работа линии состоит из тактов одновременной обработки на всех позициях всех расположенных на них заготовок соответствующими позициям и заготовкам наборами инструментов. Состав комплекта не изменяется от интервала к интервалу. Диапазоны возможных величин спроса на каждое изделие комплекта и распределение вероятностей спроса в этих диапазонах считаются известными для каждого временного интервала. В качестве целевой функции используется сумма производственных затрат, затрат на хранение невостребованных изделий и/или штрафов за неудовлетворенный спрос на них. Производственные затраты зависят от принимаемой интенсивности обработки и возрастают с увеличением количества комплектов, выпускаемых в текущем интервале. Затраты на хранение невостребованных изделий каждого наименования, а также штрафы за недопоставленные заказчикам изделия не убывают с ростом числа таких изделий. Предложен двухуровневый декомпозиционный метод решения задачи, основанный на идеях многошаговой оптимизации. 

The problem of optimizing the output of multi-product batch and the intensities of its items manufacture in the production line over a number of time intervals is considered. The line has a linearly ordered multiple positions without buffers. Workpieces of the input sequence composed of cyclically repeated identical subsequences (batches) are processed consecutively one by one in each working position in the order of their location in the line. Only a single workpiece is disposed in each position at each time point. The operation of the line consists of takts of simultaneous processing of all workpieces located in respective positions by the sets of tools corresponding to workpieces and positions. The composition of a batch does not vary from interval to interval. The ranges of possible demand quantities for each product and the probability distribution of the demand in these ranges are assumed known for each time interval. The sum of manufacturing cost, costs of storage and/or penalties for unmet demand on products is used as objective function. Manufacturing cost depends on processing intensities to be defined and increases with an increase in the number of batches produced in the current interval. Storage cost of unclaimed product units as well as penalty for product units not supplied to the customer do not decrease with the increase of number of such units. A two-level decomposition method for solving the problem based on the ideas of multi-step optimization is proposed.

комплект изделийразмер партииинтенсивность обработкислучайный спросминимизация затратдекомпозиционный методbatch of productslot sizeprocessing intensityrandom demandcost minimizationdecomposition methodReferencesKarimi, B. The capacitated lot sizing problem: a review of models and algorithms / B. Karimi, S. Fatemi Ghomi, J. M. Wilson // Omega. – 2003. – Vol. 31, № 5. – P. 365–378.Karimi B., Fatemi Ghomi S., Wilson J. M. The capacitated lot sizing problem: a review of models and algorithms. Omega, 2003, vol. 31, no. 5, pp. 365–378. Doi: 10.1016/s0305-0483(03)00059-8Ullah, H. A Literature Review on Inventory Lot Sizing Problems / H. Ullah, S. Parveen // Global Journal of Researches in Engineering. – 2010. – Vol. 10, № 5. – P. 21–36.Ullah H., Parveen S. A Literature Review on Inventory Lot Sizing Problems. Global Journal of Researches in Engineering, 2010, vol. 10, no. 5, pp. 21–36.Jans, R. Modeling industrial lot sizing problems: a review / R. Jans, Z. Degraeve // Int. J. Prod. Res. – 2008. – Vol. 46, № 6. – P. 1619–1643.Jans R., Degraeve Z. Modeling industrial lot sizing problems: a review. International Journal of Production Research, 2008, vol. 46, no. 6, pp. 1619–1643. Doi: 10.1080/00207540600902262Ng, C. T. A simple FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure / C. T. Ng, M. Y. Kovalyov, T. C. E. Cheng // Eur. J. Oper. Res. – 2010. – Vol. 200, № 2. – P. 621–624.Ng C. T., Kovalyov M. Y., Cheng T. C. E. A simple FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure. European Journal of Operational Research, 2010, vol. 200, no. 2, pp. 621–624. Doi: 10.1016/j. ejor.2009.01.040Левин, Г. М. Оптимизация выпуска и интенсивностей обработки группы деталей при нестационарном спросе / Г. М. Левин, Б. М. Розин, А. Б. Долгий // Весцi Нац. акад. навук Беларусi. Сер. фiз.-мат. навук. – 2016.– № 3. – С. 102–109.Levin G. M., Rozin B. M., Dolgui A. B. Optimizing the output and the intensities of processing a batch of parts under non-stationary demand. Vestsi Natsyanal’nai akademii navuk Belarusi. Seryia fisika¬matematychnykh navuk [Proceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series], 2016, no. 3, pp. 102–109 (in Russian).Brandimarte, P. Multi-item capacitated lot-sizing with demand uncertainty / P. Brandimarte // Int. J. Prod. Res. – 2006. – Vol. 44, № 15. – P. 2997–3022.Brandimarte P. Multi-item capacitated lot-sizing with demand uncertainty. International Journal of Production Research, 2006, vol. 44, no. 15, pp. 2997–3022. Doi: 10.1080/00207540500435116Lee, S.-D. Economic lot sizing in a production system with random demand / S.-D. Lee, C.-M. Yang, S.-C. Lan // Int. J. Prod. Res. – 2016. – Vol. 47, № 5. – P. 1142–1154.Lee S.-D., Yang C.-M., Lan S.-C. Economic lot sizing in a production system with random demand. International Journal of Systems Science, 2014, vol. 47, no. 5, pp. 1142–1154. Doi: 10.1080/00207721.2014.915354Tempelmeier, H. ABCβ - a heuristic for dynamic capacitated lot sizing with random demand under a fillrate constraint / H. Tempelmeier, S. Herpers // Int. J. Prod. Res. – 2010. – Vol. 48, № 17. – P. 5181–5193.Tempelmeier H., Herpers S. ABCβ - a heuristic for dynamic capacitated lot sizing with random demand under a fillrate constraint. International Journal of Production Research, 2010, vol. 48, no. 17, pp. 5181–5193. Doi: 10.1080/00207540903179782Maes, J. Multi Item Single Level Capacitated Dynamic Lotsizing Heuristics: A Computational Comparison (Part II: Rolling Horizon) / J. Maes, L. N. Van Wassenhove // IIE Transactions. – 1986. – Vol. 18, № 2. – P. 124–129.Maes J., Van Wassenhove L. N. Multi Item Single Level Capacitated Dynamic Lotsizing Heuristics: A Computational Comparison (Part II: Rolling Horizon). IIE Transactions, 1986, vol. 18, no. 2, pp. 124–129. Doi: 10.1080/07408178608975339Гнеденко, Б. В. Курс теории вероятностей / Б. В. Гнеденко. – М.: Едиториал УРСС, 2005. – 448 с.Gnedenko B. V. Probability theory course. Мoscow, Editorial URSS Publ., 2005. 448 p. (in Russian).Левин, Г. М. Декомпозиционные методы оптимизации проектных решений / Г. М. Левин, В. С. Танаев. – Минск: Наука и техника, 1978. – 240 с.Levin G., Tanaev V. Decomposition techniques for optimization of design decisions. Minsk, Nauka i Technika Publ., 1978. 240 p. (in Russian).Левин, Г. М. Линейная аппроксимация задачи оптимизации интенсивностей последовательно-параллельного выполнения пересекающихся множеств операций / Г. М. Левин, Б. М. Розин, А. Б. Долгий // Информатика. – 2014. – № 3. – С. 44–51.Levin G. M., Rozin B. M., Dolgui A. B. Linear approximation for intensities optimization problem of sequential-parallel execution of intersecting operation sets. Informatika [Informatics], 2014, no. 3, pp. 44–51. (in Russian).

The authors declare that there are no conflicts of interest present.