vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"vestifm-203Research ArticleИНФОРМАТИКАINFORMATICSОПТИМИЗАЦИЯ ВЫПУСКА И ИНТЕНСИВНОСТЕЙ ОБРАБОТКИ ГРУППЫ ДЕТАЛЕЙ ПРИ НЕСТАЦИОНАРНОМ СПРОСЕOPTIMIZING THE OUTPUT AND THE INTENSITIES OF PROCESSING A BATCH OF PARTS UNDER NON-STATIONARY DEMANDЛЕВИНГ. М.LEVING. M.levin@newman.bas-net.byРОЗИНБ. М.ROZINB. M.rozin@newman.bas-net.byДОЛГИЙА. Б.DOLGUIA. B.Alexandre.Dolgui@mines-nantes.frОбъединенный институт проблем информатики Национальной академии наук БеларусиUnited Institute of Informatics Problems of National Academy of Sciences of BelarusГорная школа НантаEcole des Mines de Nantes20162211201603102109Copyright © ЛЕВИН Г.М., РОЗИН Б.М., ДОЛГИЙ А.Б., 20162016ЛЕВИН Г.М., РОЗИН Б.М., ДОЛГИЙ А.Б.LEVIN G.M., ROZIN B.M., DOLGUI A.B.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/203

Рассматривается задача оптимизации размеров выпуска группы деталей и интенсивностей их обработки на многопозиционном оборудовании блоками инструментов при нестационарном спросе на заданных временных интервалах. Состав группы не меняется от интервала к интервалу. В качестве целевой функции принята сумма затрат на производство, хранение избытков деталей и штрафы за неудовлетворенный спрос на них. Затраты на выпуск группы деталей зависят от интенсивностей их обработки. Предложен декомпозиционный метод решения задачи.

We consider a problem of optimizing the output of a batch of parts and intensities of its processing with tool blocks on a multiposition equipment under non-stationary demand and predetermined time intervals. The batch content does not vary from one interval to another. The objective function is the sum of production cost, storage cost of excess parts, and penalties for unmet demand. The production cost depends on processing intensities. A decomposition method for solving the problem is proposed.

размер партиигруппа деталейинтенсивность обработкиминимизация затратдекомпозиционный методlot sizebatch of partsintensity of processingcost minimizationdecomposition methodReferencesKarimi, B. The capacitated lot sizing problem: a review of models and algorithms / B. Karimi, S. M. T. Fatemi Ghomi, J. M. Wilson // Omega. – 2003. – Vol. 31, N 5. – P. 365–378.Karimi, B. The capacitated lot sizing problem: a review of models and algorithms / B. Karimi, S. M. T. Fatemi Ghomi, J. M. Wilson // Omega. – 2003. – Vol. 31, N 5. – P. 365–378.Ullah, H. A Literature Review on Inventory Lot Sizing Problems / H. Ullah, S. Parveen // Global J. Res. Eng. – 2010. – Vol. 10, N 5. – P. 21–36.Ullah, H. A Literature Review on Inventory Lot Sizing Problems / H. Ullah, S. Parveen // Global J. Res. Eng. – 2010. – Vol. 10, N 5. – P. 21–36.Robinson, P. Coordinated deterministic dynamic demand lot-sizing problem: A review of models and algorithms / P. Robinson, A. Narayanan, F. Sahin // Omega. – 2009. – Vol. 37, N 1. – P. 3–15.Robinson, P. Coordinated deterministic dynamic demand lot-sizing problem: A review of models and algorithms / P. Robinson, A. Narayanan, F. Sahin // Omega. – 2009. – Vol. 37, N 1. – P. 3–15.Van Hoesel, C. P. M. Fully polynomial approximation schemes for single-item capacitated economic lot-sizing problems / C. P. M. Van Hoesel, A. P. M. Wagelmans // Math. Oper. Res. – 2001. – Vol. 26, N 2. – P. 339–57.Van Hoesel, C. P. M. Fully polynomial approximation schemes for single-item capacitated economic lot-sizing problems / C. P. M. Van Hoesel, A. P. M. Wagelmans // Math. Oper. Res. – 2001. – Vol. 26, N 2. – P. 339–57.Ng, 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. – P. 621–624.Ng, 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. – P. 621–624.Absi, N. The multi-item capacitated lot-sizing problem with safety stocks and demand shortage costs / N. Absi, S. Kedad- Sidhoum // Comput. Oper. Res. – 2009. – Vol. 36, N 11. – P. 2926–2936.Absi, N. The multi-item capacitated lot-sizing problem with safety stocks and demand shortage costs / N. Absi, S. Kedad- Sidhoum // Comput. Oper. Res. – 2009. – Vol. 36, N 11. – P. 2926–2936.Florian, M. Deterministic production planning: Algorithms and complexity / M. Florian, J. K. Lenstra, A. H. G. R. Kan // Management Science. – 1980. – Vol. 26. – P. 669–679.Florian, M. Deterministic production planning: Algorithms and complexity / M. Florian, J. K. Lenstra, A. H. G. R. Kan // Management Science. – 1980. – Vol. 26. – P. 669–679.Bitran, G. R. Computational complexity of the capacitated lot size problem / G. R. Bitran, H. H. Yanasse // Management Science. – 1982. – Vol. 28, N 10. – P. 1174–1186.Bitran, G. R. Computational complexity of the capacitated lot size problem / G. R. Bitran, H. H. Yanasse // Management Science. – 1982. – Vol. 28, N 10. – P. 1174–1186.Chen, W. H. Analysis of relaxations for the multi-item capacitated lot-sizing problem / W. H. Chen, J. M. Thizy // Ann. Oper. Res. – 1990. – Vol. 26. – P. 29–72.Chen, W. H. Analysis of relaxations for the multi-item capacitated lot-sizing problem / W. H. Chen, J. M. Thizy // Ann. Oper. Res. – 1990. – Vol. 26. – P. 29–72.Dixon, P. S. A heuristic solution procedure for the multi-item, single level, limited capacity, lot sizing problem / P. S. Dixon, E. A. Silver // J. of Operations Management. – 1981. – Vol. 21, N 1. – P. 23–40.Dixon, P. S. A heuristic solution procedure for the multi-item, single level, limited capacity, lot sizing problem / P. S. Dixon, E. A. Silver // J. of Operations Management. – 1981. – Vol. 21, N 1. – P. 23–40.Maes, J. A simple heuristic for the multi-item single level capacitated lot sizing problem / J. Maes, L. N. Van Wassenhove // Oper. Res. Lett. – 1986. – Vol. 4, N 6. – P. 265–273.Maes, J. A simple heuristic for the multi-item single level capacitated lot sizing problem / J. Maes, L. N. Van Wassenhove // Oper. Res. Lett. – 1986. – Vol. 4, N 6. – P. 265–273.Dogramaci, A. The dynamic lot-sizing problem for the multiple items under limited capacity / A. Dogramaci, J. C. Panayiotopoulos, N. R. Adam // AIIE Transactions. – 1981. – Vol. 13, N 4. – P. 294–303.Dogramaci, A. The dynamic lot-sizing problem for the multiple items under limited capacity / A. Dogramaci, J. C. Panayiotopoulos, N. R. Adam // AIIE Transactions. – 1981. – Vol. 13, N 4. – P. 294–303.Karni, R. A heuristic algorithm for the multi-item lot sizing problem with capacity constraints / R. Karni, Y. Roll // AIIE Transactions. – 1982. – Vol. 14, N 4. – P. 249–259.Karni, R. A heuristic algorithm for the multi-item lot sizing problem with capacity constraints / R. Karni, Y. Roll // AIIE Transactions. – 1982. – Vol. 14, N 4. – P. 249–259.Gunther, H. O. Planning lot sizes and capacity requirements in a single stage production systems / H. O. Gunther // Eur. J. Oper. Res. – 1987. – Vol. 31, N 2. – P. 223–231.Gunther, H. O. Planning lot sizes and capacity requirements in a single stage production systems / H. O. Gunther // Eur. J. Oper. Res. – 1987. – Vol. 31, N 2. – P. 223–231.Thizy, J. M. Lagrangean relaxation for the multi-item capacitated lot-sizing problem: a heuristic implementation / J. M. Thizy, L. N. Van Wassenhove // IIE Transactions. – 1985. – Vol. 17, N 4. – P. 308–313.Thizy, J. M. Lagrangean relaxation for the multi-item capacitated lot-sizing problem: a heuristic implementation / J. M. Thizy, L. N. Van Wassenhove // IIE Transactions. – 1985. – Vol. 17, N 4. – P. 308–313.Gelders, L. F. A branch and bound algorithm for the multi item single level capacitated dynamic lotsizing problem / L. F. Gelders, J. Maes, L. N. Van Wassenhove // Multistage production planning and inventory control. Lecture notes in economics and mathematical systems / eds.: S. Axaster, Ch. Schneeweiss, E. Silver. – Berlin: Springer, 1986. – Vol. 266. – P. 92–108.Gelders, L. F. A branch and bound algorithm for the multi item single level capacitated dynamic lotsizing problem / L. F. Gelders, J. Maes, L. N. Van Wassenhove // Multistage production planning and inventory control. Lecture notes in economics and mathematical systems / eds.: S. Axaster, Ch. Schneeweiss, E. Silver. – Berlin: Springer, 1986. – Vol. 266. – P. 92–108.Leung, J. M. Y. Facets and algorithms for capacitated lot sizing / J. M. Y. Leung, T. L. Magnanti, R. Vachani // Mathematical Programming. – 1989. – Vol. 45. – P. 331–359.Leung, J. M. Y. Facets and algorithms for capacitated lot sizing / J. M. Y. Leung, T. L. Magnanti, R. Vachani // Mathematical Programming. – 1989. – Vol. 45. – P. 331–359.Belvaux, G. Bc-prod: a specialised branch-and-cut system for lot-sizing problems / G. Belvaux, L. A. Wolsey // Management Science. – 2000. – Vol. 46, N 5. – P. 993–1007.Belvaux, G. Bc-prod: a specialised branch-and-cut system for lot-sizing problems / G. Belvaux, L. A. Wolsey // Management Science. – 2000. – Vol. 46, N 5. – P. 993–1007.Belvaux, G. Modelling practical lot-sizing problems as mixed integer programs / G. Belvaux, L. A. Wolsey // Management Science. – 2001. – Vol. 47, N 7. – P. 724–738.Belvaux, G. Modelling practical lot-sizing problems as mixed integer programs / G. Belvaux, L. A. Wolsey // Management Science. – 2001. – Vol. 47, N 7. – P. 724–738.Barany, I. Strong formulations for multi-item capacitated lot sizing / I. Barany, T. J. Van Roy, L. A. Wolsey // Management Science. – 1984. – Vol. 30, N 10. – P. 1255–1261.Barany, I. Strong formulations for multi-item capacitated lot sizing / I. Barany, T. J. Van Roy, L. A. Wolsey // Management Science. – 1984. – Vol. 30, N 10. – P. 1255–1261.Leung, J. M. Y. Facets and algorithms for capacitated lot sizing / J. M. Y. Leung, T. L. Magnanti, R. Vachani // Mathematical Programming. – 1989. – Vol. 45. – P. 331–359.Leung, J. M. Y. Facets and algorithms for capacitated lot sizing / J. M. Y. Leung, T. L. Magnanti, R. Vachani // Mathematical Programming. – 1989. – Vol. 45. – P. 331–359.Eppen, G. D. Solving multi-item capacitated lot sizing problems using variable redefinition / G. D. Eppen, R. K. Martin // Oper. Res. – 1987. – Vol. 35, N 6. – P. 832–848.23. Wagelmans, A. Economic lotsizing: an O(n log n) algorithm that runs in linear time in the Wagner – Whitin case / A. Wagelmans, S.van Hoesel, A. Kolen // Oper. Res. – 1992. – Vol. 40. – P. 145–155.Eppen, G. D. Solving multi-item capacitated lot sizing problems using variable redefinition / G. D. Eppen, R. K. Martin // Oper. Res. – 1987. – Vol. 35, N 6. – P. 832–848.23. Wagelmans, A. Economic lotsizing: an O(n log n) algorithm that runs in linear time in the Wagner – Whitin case / A. Wagelmans, S.van Hoesel, A. Kolen // Oper. Res. – 1992. – Vol. 40. – P. 145–155.Aggarwal, A. Improved algorithms for economic lot-size problem / A. Aggarwal, J. K. Park // Oper. Res. – 1993. – Vol. 41, N 3. – P. 549–571.Aggarwal, A. Improved algorithms for economic lot-size problem / A. Aggarwal, J. K. Park // Oper. Res. – 1993. – Vol. 41, N 3. – P. 549–571.Federgruen, A. A simple forward algorithm to solve general dynamic lot sizing models with n periods in O(n log n) or O(n) time / A. Federgruen, M. A. Tzur // Management Science. – 1991. – Vol. 37, N 8. – P. 909–925.Federgruen, A. A simple forward algorithm to solve general dynamic lot sizing models with n periods in O(n log n) or O(n) time / A. Federgruen, M. A. Tzur // Management Science. – 1991. – Vol. 37, N 8. – P. 909–925.Левин, Г. М. Линейная аппроксимация задачи оптимизации интенсивностей последовательно-параллельного выполнения пересекающихся множеств операций / Г. М. Левин, Б. М. Розин, А. Б. Долгий // Информатика. – 2014. – № 3. – С. 44–51.Левин, Г. М. Линейная аппроксимация задачи оптимизации интенсивностей последовательно-параллельного выполнения пересекающихся множеств операций / Г. М. Левин, Б. М. Розин, А. Б. Долгий // Информатика. – 2014. – № 3. – С. 44–51.

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