informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-103Research ArticleМАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕMATHEMATICAL MODELINGЗАДАЧИ БАЛАНСИРОВКИ СБОРОЧНЫХ ЛИНИЙ С НЕОПРЕДЕЛЕННЫМИ ЧИСЛОВЫМИ ПАРАМЕТРАМИASSEMBLY LINE BALANCING PROBLEMS WITH UNCERTAIN NUMERICAL PARAMETERSСотсковЮ. Н.SotskovYu. N.sotskov@newman.bas-net.byЗатюпоО. С.ZatsiupaA. S.ztp.oksana100@yandex.ruОбъединенный институт проблем информатики НАН БеларусиRussian Federation201301102016045465Copyright © Сотсков Ю.Н., Затюпо О.С., 20162016Сотсков Ю.Н., Затюпо О.С.Sotskov Y.N., Zatsiupa A.S.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/103

Рассматриваются задачи балансировки сборочных линий с неточными исходными данными (длительностями сборочных операций). Приводятся постановки задач балансировки сборочных линий с детерминированными, стохастическими и неопределенными параметрами. Описываются различные подходы к решению задач балансировки сборочных линий с неточными длительностями сборочных операций. Предлагается новая постановка задачи с неопределенными (интервальными) параметрами, когда для длительностей сборочных операций заданы только нижние и верхние гра-ницы (интервалы) их возможных значений. Обосновывается необходимость исследования задачи балансировки сборочных линий с интервальными параметрами.

Assembly line balancing problems with imprecise input data (durations of assembly operations, number of workstations) are considered. Problem settings with deterministic, stochastic, and uncertain parameters are discussed. Different approaches to the assembly line balancing problems with imprecise durations of assembly operations are analyzed. A new problem setting is proposed in which durations of assembly operations are given by lower and upper bounds of their possible values.

ReferencesSalveson, M.E. The assembly line balancing problem / M.E. Salveson // The J. of Industrial Engineering. – 1955. – Vol. 6, № 3. – P. 18–25.Salveson, M.E. The assembly line balancing problem / M.E. Salveson // The J. of Industrial Engineering. – 1955. – Vol. 6, № 3. – P. 18–25.Baybars, I. A survey of exact algorithms for the simple assembly line balancing problem /I. Baybars // Management Science. – 1986. – Vol. 32. – P. 909–932.Baybars, I. A survey of exact algorithms for the simple assembly line balancing problem /I. Baybars // Management Science. – 1986. – Vol. 32. – P. 909–932.Boysen, N. A classification of assembly line balancing problems / N. Boysen, M. Fliener, A. Scholl // European J. of Operational Research. – 2007. – Vol. 183. – P. 674–693.Boysen, N. A classification of assembly line balancing problems / N. Boysen, M. Fliener, A. Scholl // European J. of Operational Research. – 2007. – Vol. 183. – P. 674–693.Thomopoulos, N.T. Line balancing – sequencing for mixed model assembly / N.T. Thomopoulos // Management Science. – 1967. – Vol. 14. – P. 59–75.Thomopoulos, N.T. Line balancing – sequencing for mixed model assembly / N.T. Thomopoulos // Management Science. – 1967. – Vol. 14. – P. 59–75.Dar-El, E.M. Mixed-model assembly line sequencing problems / E.M. Dar-El // Omega. –1978. – Vol. 6. – P. 317–323.Dar-El, E.M. Mixed-model assembly line sequencing problems / E.M. Dar-El // Omega. –1978. – Vol. 6. – P. 317–323.Sparling, D. The mixed-model U-line balancing problem / D. Sparling, J. Miltenburg // International J. of Operational Research. – 1998. – Vol. 36. – P. 485–501.Sparling, D. The mixed-model U-line balancing problem / D. Sparling, J. Miltenburg // International J. of Operational Research. – 1998. – Vol. 36. – P. 485–501.Ege, Y. Assembly line balancing with station paralleling / Y. Ege, M. Azizoglu, N. Ozdemirel // Computers & Industrial Engineering. – 2009. – Vol. 57. – P. 1218–1225.Ege, Y. Assembly line balancing with station paralleling / Y. Ege, M. Azizoglu, N. Ozdemirel // Computers & Industrial Engineering. – 2009. – Vol. 57. – P. 1218–1225.Tonge, F.M. A Heuristic program for assembly line balancing / F.M. Tonge. – Englewood Cliffs, NJ : Prentice-Hall, 1961. – 362 p.Tonge, F.M. A Heuristic program for assembly line balancing / F.M. Tonge. – Englewood Cliffs, NJ : Prentice-Hall, 1961. – 362 p.Pinto, P.A. A branch and bound algorithm for assembly line balancing with paralleling /P.A. Pinto, D.G. Dannenbring, B.M. Khumawala // International J. of Production Res. – 1975. –Vol. 13. – P. 183–196.Pinto, P.A. A branch and bound algorithm for assembly line balancing with paralleling /P.A. Pinto, D.G. Dannenbring, B.M. Khumawala // International J. of Production Res. – 1975. –Vol. 13. – P. 183–196.Mansoor, E.M. Assembly line balancing – an improvement on the ranked positional weight technique / E.M. Mansoor // J. Industrial Engineering. – 1964. – Vol. 15. – P. 73–78.Mansoor, E.M. Assembly line balancing – an improvement on the ranked positional weight technique / E.M. Mansoor // J. Industrial Engineering. – 1964. – Vol. 15. – P. 73–78.Freeman, D.R. A general line balancing model / D.R. Freeman // Proc. 19th Annual Conf. AIIE. – Tampa, FLA, 1968. – P. 230–235.Freeman, D.R. A general line balancing model / D.R. Freeman // Proc. 19th Annual Conf. AIIE. – Tampa, FLA, 1968. – P. 230–235.Scholl, A. Balancing and sequencing of assembly line / A. Scholl; Second ed. – Heidelberg : Physical-Verlag, 1999. – 532 p.Scholl, A. Balancing and sequencing of assembly line / A. Scholl; Second ed. – Heidelberg : Physical-Verlag, 1999. – 532 p.Erel, E. A survey of the assembly line balancing procedures / E. Erel, S.C. Sarin // Production Planning and Control. – 1998. – Vol. 9. – P. 414–434.Erel, E. A survey of the assembly line balancing procedures / E. Erel, S.C. Sarin // Production Planning and Control. – 1998. – Vol. 9. – P. 414–434.Scholl, A. Balancing assembly lines effectively – A computational comparison / A. Scholl, R. Klein // European J. of Operational Research. – 1999. – Vol. 144. – P. 50–58.Scholl, A. Balancing assembly lines effectively – A computational comparison / A. Scholl, R. Klein // European J. of Operational Research. – 1999. – Vol. 144. – P. 50–58.Kottas, J.F. A cost oriented approach to stochastic line balancing / J.F. Kottas, H.S. Lau // AIIE Transactions. – 1973. – Vol. 5. – P. 164–171.Kottas, J.F. A cost oriented approach to stochastic line balancing / J.F. Kottas, H.S. Lau // AIIE Transactions. – 1973. – Vol. 5. – P. 164–171.Reeve, N.R. Balancing stochastic assembly lines / N.R. Reeve, W.H. Thomas // AIIE Transactions. – 1973. – Vol. 5. – P. 223–229.Reeve, N.R. Balancing stochastic assembly lines / N.R. Reeve, W.H. Thomas // AIIE Transactions. – 1973. – Vol. 5. – P. 223–229.Kottas, J.F. A cost oriented approach to stochastic line balancing / J.F. Kottas, H.S. Lau // AIIE Transactions. – 1973. – Vol. 5. – P. 164–171.Kottas, J.F. A cost oriented approach to stochastic line balancing / J.F. Kottas, H.S. Lau // AIIE Transactions. – 1973. – Vol. 5. – P. 164–171.Silverman, F.N. A cost- based methodology for stochastic line balancing with intermittent line stoppages / F.N. Silverman, J.C. Carter // Management Science. – 1986. – Vol. 32. – P. 455–463.Silverman, F.N. A cost- based methodology for stochastic line balancing with intermittent line stoppages / F.N. Silverman, J.C. Carter // Management Science. – 1986. – Vol. 32. – P. 455–463.Shin, D. An efficient heuristic for solving stochastic assembly line balancing problem /D. Shin // Computers and Industrial Engineering. – 1990. – Vol. 18. – P. 285–295.Shin, D. An efficient heuristic for solving stochastic assembly line balancing problem /D. Shin // Computers and Industrial Engineering. – 1990. – Vol. 18. – P. 285–295.Shin, D. Uniform assembly line balancing with stochastic task limes in just-in-time manufacturing / D. Shin, H. Min // International J. of Operations and Production Management. – 1991. –Vol. 11, №. 8. – P. 23–34.Shin, D. Uniform assembly line balancing with stochastic task limes in just-in-time manufacturing / D. Shin, H. Min // International J. of Operations and Production Management. – 1991. –Vol. 11, №. 8. – P. 23–34.Gen, M. Solving fuzzy assembly-line balancing problem with genetic algorithms / M. Gen, Y. Tsujimura, E. Kubot // Computers inc. Engineering. – 1995. – Vol. 29. – P. 543–547.Gen, M. Solving fuzzy assembly-line balancing problem with genetic algorithms / M. Gen, Y. Tsujimura, E. Kubot // Computers inc. Engineering. – 1995. – Vol. 29. – P. 543–547.Gen, M. Fuzzy assembly line balancing using genetic algorithms / M. Gen, Y. Tsujimura, Y. Li // Computers inc. Engineering. – 1996. – Vol. 31. – P. 631–634.Gen, M. Fuzzy assembly line balancing using genetic algorithms / M. Gen, Y. Tsujimura, Y. Li // Computers inc. Engineering. – 1996. – Vol. 31. – P. 631–634.Rabbani, M. Considering the conveyer stoppages in sequencing mixed-model assembly lines by a new fuzzy programming approach / M. Rabbani, F. Radmehr, N. Manavizadeh // International J. of Advance Manufacture Technology. – 2010. – Vol. 10. – P. 170-180.Rabbani, M. Considering the conveyer stoppages in sequencing mixed-model assembly lines by a new fuzzy programming approach / M. Rabbani, F. Radmehr, N. Manavizadeh // International J. of Advance Manufacture Technology. – 2010. – Vol. 10. – P. 170-180.Ozcan, U. Multiple-criteria decision-making in two-sided assembly line balancing: A goal programming and a fuzzy goal programming models / U. Ozcan, B. Toklu // Computers & Operations Research. – 2009. – Vol. 36. – P. 1955 – 1965.Ozcan, U. Multiple-criteria decision-making in two-sided assembly line balancing: A goal programming and a fuzzy goal programming models / U. Ozcan, B. Toklu // Computers & Operations Research. – 2009. – Vol. 36. – P. 1955 – 1965.Mastor, A.A. An experimental investigation and comparative evaluation of production line balancing techniques / A.A. Mastor // Management Science. – 1970. – Vol. 16. – P. 728-746.Mastor, A.A. An experimental investigation and comparative evaluation of production line balancing techniques / A.A. Mastor // Management Science. – 1970. – Vol. 16. – P. 728-746.Sotskov, Yu. Stability analysis of optimal balance for assembly line with fixed cycle time / Yu. Sotskov, A. Dolgui, M.-C. Portmann // European J. of Operational Research. – 2006. – Vol. 168. – P. 783–797.Sotskov, Yu. Stability analysis of optimal balance for assembly line with fixed cycle time / Yu. Sotskov, A. Dolgui, M.-C. Portmann // European J. of Operational Research. – 2006. – Vol. 168. – P. 783–797.Сотсков, Ю.Н. Теория расписаний. Системы с неопределенными числовыми параметрами / Ю.Н. Сотсков, Н.Ю. Сотскова. – Минск : ОИПИ НАН Беларуси, 2004. – 290 c.Сотсков, Ю.Н. Теория расписаний. Системы с неопределенными числовыми параметрами / Ю.Н. Сотсков, Н.Ю. Сотскова. – Минск : ОИПИ НАН Беларуси, 2004. – 290 c.Zatsiupa, A. Enumeration of the stable optimal line balances for a simple assembly line balancing problem with fixed cycle time / A. Zatsiupa, Yu.N. Sotskov, A. Dolgui // 22-nd Intern. Conf. on Production Research. – Brazil, Iquassu, 2013. – P. 1–6.Zatsiupa, A. Enumeration of the stable optimal line balances for a simple assembly line balancing problem with fixed cycle time / A. Zatsiupa, Yu.N. Sotskov, A. Dolgui // 22-nd Intern. Conf. on Production Research. – Brazil, Iquassu, 2013. – P. 1–6.Stability of optimal line balance with given station set / Yu.N. Sotskov [et al.] // A chapter in the book «Supply Chain Optimization», Applied Optimization. – Vol. 94. – USA, N.Y. : Springer, 2005. – P. 135–149.Stability of optimal line balance with given station set / Yu.N. Sotskov [et al.] // A chapter in the book «Supply Chain Optimization», Applied Optimization. – Vol. 94. – USA, N.Y. : Springer, 2005. – P. 135–149.Sotskov, Yu. Calculation of the stability radius of an optimal line balance / Yu. Sotskov, F. Werner, A. Zatsiupa // 14th IFAC symposium on information control problems in manufacturing. – Bucharest, Romania, 2012. – P. 192–197.Sotskov, Yu. Calculation of the stability radius of an optimal line balance / Yu. Sotskov, F. Werner, A. Zatsiupa // 14th IFAC symposium on information control problems in manufacturing. – Bucharest, Romania, 2012. – P. 192–197.Sotskov, Yu. Stable optimal line balances with a fixed set of the working stations /Yu. Sotskov, А. Zatsiupa, A. Dolgui // IFAC conference MIM 2013. – St. Petersburg, Russia, 2013.Sotskov, Yu. Stable optimal line balances with a fixed set of the working stations /Yu. Sotskov, А. Zatsiupa, A. Dolgui // IFAC conference MIM 2013. – St. Petersburg, Russia, 2013.Gurevsky, E. Stability measure for a generalized assembly line balancing problem /E. Gurevsky, O. Battaïa, A. Dolgui // Discrete Applied Mathematics. – 2013. – Vol. 161. – P. 377–394.Gurevsky, E. Stability measure for a generalized assembly line balancing problem /E. Gurevsky, O. Battaïa, A. Dolgui // Discrete Applied Mathematics. – 2013. – Vol. 161. – P. 377–394.Hifi, M. Sensitivity of the optimum to perturbations of the profit or weight of an item in the binary knapsack problem / M. Hifi, H. Mhalla, S. Sadfi // J. of Combinatorial Optimization. – 2005. – Vol. 10, № 3. – P. 239–260.Hifi, M. Sensitivity of the optimum to perturbations of the profit or weight of an item in the binary knapsack problem / M. Hifi, H. Mhalla, S. Sadfi // J. of Combinatorial Optimization. – 2005. – Vol. 10, № 3. – P. 239–260.Hifi, M. An adaptive algorithm for the knapsack problem: perturbation of the profit or weight of an arbitrary item / M. Hifi, H. Mhalla, S. Sadfi // European J. of Industrial Engineering. – 2008. – Vol. 2, №. 2. – P. 134–152.Hifi, M. An adaptive algorithm for the knapsack problem: perturbation of the profit or weight of an arbitrary item / M. Hifi, H. Mhalla, S. Sadfi // European J. of Industrial Engineering. – 2008. – Vol. 2, №. 2. – P. 134–152.Stability aspects of the traveling salesmen problem based on -best solutions / M. Libura [et al.] // Discrete Applied Mathematics. – 1998. – Vol. 87, № 1–3. – P. 159–185.Stability aspects of the traveling salesmen problem based on -best solutions / M. Libura [et al.] // Discrete Applied Mathematics. – 1998. – Vol. 87, № 1–3. – P. 159–185.Ramaswamy, R. Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs / R. Ramaswamy, J. Orlin, N. Chakravarti // Mathematical Programming. – 2005. – Vol. 102, № 2. – P. 355–369.Ramaswamy, R. Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs / R. Ramaswamy, J. Orlin, N. Chakravarti // Mathematical Programming. – 2005. – Vol. 102, № 2. – P. 355–369.Bräsel, H. Stability of a schedule minimizing mean flow time / H. Bräsel, Yu. Sotskov, F. Werner // Mathematical and Computer Modelling. – 1996. – Vol. 24, № 10. – P. 39–53.Bräsel, H. Stability of a schedule minimizing mean flow time / H. Bräsel, Yu. Sotskov, F. Werner // Mathematical and Computer Modelling. – 1996. – Vol. 24, № 10. – P. 39–53.Kravchenko, S. Optimal schedules with infinitely large stability radius / S. Kravchenko, Yu. Sotskov, F. Werner // Optimization. – 1995. – Vol. 33, № 3. – P. 271–280.Kravchenko, S. Optimal schedules with infinitely large stability radius / S. Kravchenko, Yu. Sotskov, F. Werner // Optimization. – 1995. – Vol. 33, № 3. – P. 271–280.Sotskov, Yu. Stability of an optimal schedule / Yu. Sotskov // European J. of Operational Research. – 1991. – Vol. 55, № 1. – P. 91–102.Sotskov, Yu. Stability of an optimal schedule / Yu. Sotskov // European J. of Operational Research. – 1991. – Vol. 55, № 1. – P. 91–102.Scheduling under uncertainty: Theory and Algorithms / Yu. Sotskov [et al.]. – Minsk : Belorusskaya Nauka, 2010. – 326 p.Scheduling under uncertainty: Theory and Algorithms / Yu. Sotskov [et al.]. – Minsk : Belorusskaya Nauka, 2010. – 326 p.Sotskov, Yu. Stability of an optimal schedule in a job shop / Yu. Sotskov, N. Sotskova, F. Werner // Omega. – 1997. – Vol. 25, № 4. – P. 397-414.Sotskov, Yu. Stability of an optimal schedule in a job shop / Yu. Sotskov, N. Sotskova, F. Werner // Omega. – 1997. – Vol. 25, № 4. – P. 397-414.Sotskov, Yu. Stability radius of an optimal schedule: a survey and recent developments /Yu. Sotskov, V. Tanaev, F. Werner // Industrial Applications of Combinatorial Optimization. – 1998. – Vol. 16. – P. 72–108.Sotskov, Yu. Stability radius of an optimal schedule: a survey and recent developments /Yu. Sotskov, V. Tanaev, F. Werner // Industrial Applications of Combinatorial Optimization. – 1998. – Vol. 16. – P. 72–108.Sotskov, Yu. On the calculation of the stability radius of an optimal or an approximate schedule / Yu. Sotskov, A. Wagelmans, F. Werner // Annals of Operations Research. – 1998. – Vol. 83. – P. 213–252.Sotskov, Yu. On the calculation of the stability radius of an optimal or an approximate schedule / Yu. Sotskov, A. Wagelmans, F. Werner // Annals of Operations Research. – 1998. – Vol. 83. – P. 213–252.Schedule execution for two-machine flow-shop with interval processing times / N.M. Matsveichuk [et al.] // Mathematical and Computer Modelling. – 2009. – Vol. 49. – Р. 991–1011.Schedule execution for two-machine flow-shop with interval processing times / N.M. Matsveichuk [et al.] // Mathematical and Computer Modelling. – 2009. – Vol. 49. – Р. 991–1011.Sotskov, Yu.N. Minimizing total weighted flow time of a set of jobs with interval processing times / Yu.N. Sotskov, N.G. Egorova, T.-C. Lai // Mathematical and Computer Modelling. – 2009. – Vol. 50. – Р 556–573.Sotskov, Yu.N. Minimizing total weighted flow time of a set of jobs with interval processing times / Yu.N. Sotskov, N.G. Egorova, T.-C. Lai // Mathematical and Computer Modelling. – 2009. – Vol. 50. – Р 556–573.Two-machine flow-shop minimum-length scheduling with interval processing times / C.T. Ng [et al.] // Asia-Pacific Journal of Operational Research. – 2009. – Vol. 26, № 6. – Р. 715–734.Two-machine flow-shop minimum-length scheduling with interval processing times / C.T. Ng [et al.] // Asia-Pacific Journal of Operational Research. – 2009. – Vol. 26, № 6. – Р. 715–734.Sotskov, Yu.N. Minimizing total weighted completion time with uncertain data: A stability approach / Yu.N. Sotskov, N.G. Egorova, F. Werner // Automation and Remote Control. – 2010. – Vol. 71, № 10. – Р. 2038–2057.Sotskov, Yu.N. Minimizing total weighted completion time with uncertain data: A stability approach / Yu.N. Sotskov, N.G. Egorova, F. Werner // Automation and Remote Control. – 2010. – Vol. 71, № 10. – Р. 2038–2057.Sotskov, Yu.N. Minimizing total weighted flow under uncertainty using dominance and a stability box / Yu.N. Sotskov, T.-C. Lai // Computers & Operations Research. – 2012. – Vol. 39. – Р. 1271–1289.Sotskov, Yu.N. Minimizing total weighted flow under uncertainty using dominance and a stability box / Yu.N. Sotskov, T.-C. Lai // Computers & Operations Research. – 2012. – Vol. 39. – Р. 1271–1289.Matsveichuk, N.M. The dominance digraph as a solution to the two-machine flow-shop problem with interval processing times / N.M. Matsveichuk, Yu.N. Sotskov, F. Werner // Optimization. – 2011. – Vol. 60, № 12. – Р. 1493–1517.Matsveichuk, N.M. The dominance digraph as a solution to the two-machine flow-shop problem with interval processing times / N.M. Matsveichuk, Yu.N. Sotskov, F. Werner // Optimization. – 2011. – Vol. 60, № 12. – Р. 1493–1517.Sotskov, Yu.N. Measures of problem uncertainty for scheduling with interval processing times / Yu.N. Sotskov, T.-C. Lai, F. Werner // OR Spectrum. – 2013. – Vol. 35. – Р. 659–689.Sotskov, Yu.N. Measures of problem uncertainty for scheduling with interval processing times / Yu.N. Sotskov, T.-C. Lai, F. Werner // OR Spectrum. – 2013. – Vol. 35. – Р. 659–689.Sotskov, Yu.N. Measure of uncertainty for Bellman-Johnson problem with interval data /Yu.N. Sotskov, N.M. Matsveichuk // Cybernetics and System Analysis – 2012. – Vol. 48, № 5. – P. 641–652.Sotskov, Yu.N. Measure of uncertainty for Bellman-Johnson problem with interval data /Yu.N. Sotskov, N.M. Matsveichuk // Cybernetics and System Analysis – 2012. – Vol. 48, № 5. – P. 641–652.

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