ЗАДАЧИ БАЛАНСИРОВКИ СБОРОЧНЫХ ЛИНИЙ С НЕОПРЕДЕЛЕННЫМИ ЧИСЛОВЫМИ ПАРАМЕТРАМИ
Аннотация
Рассматриваются задачи балансировки сборочных линий с неточными исходными данными (длительностями сборочных операций). Приводятся постановки задач балансировки сборочных линий с детерминированными, стохастическими и неопределенными параметрами. Описываются различные подходы к решению задач балансировки сборочных линий с неточными длительностями сборочных операций. Предлагается новая постановка задачи с неопределенными (интервальными) параметрами, когда для длительностей сборочных операций заданы только нижние и верхние гра-ницы (интервалы) их возможных значений. Обосновывается необходимость исследования задачи балансировки сборочных линий с интервальными параметрами.
Об авторах
Ю. Н. Сотсков
Объединенный институт проблем информатики НАН Беларуси
Россия
Россия
О. С. Затюпо
Объединенный институт проблем информатики НАН Беларуси
Россия
Россия
Список литературы
1. Salveson, M.E. The assembly line balancing problem / M.E. Salveson // The J. of Industrial Engineering. – 1955. – Vol. 6, № 3. – P. 18–25.
2. Baybars, I. A survey of exact algorithms for the simple assembly line balancing problem /I. Baybars // Management Science. – 1986. – Vol. 32. – P. 909–932.
3. 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.
4. Thomopoulos, N.T. Line balancing – sequencing for mixed model assembly / N.T. Thomopoulos // Management Science. – 1967. – Vol. 14. – P. 59–75.
5. Dar-El, E.M. Mixed-model assembly line sequencing problems / E.M. Dar-El // Omega. –1978. – Vol. 6. – P. 317–323.
6. Sparling, D. The mixed-model U-line balancing problem / D. Sparling, J. Miltenburg // International J. of Operational Research. – 1998. – Vol. 36. – P. 485–501.
7. Ege, Y. Assembly line balancing with station paralleling / Y. Ege, M. Azizoglu, N. Ozdemirel // Computers & Industrial Engineering. – 2009. – Vol. 57. – P. 1218–1225.
8. Tonge, F.M. A Heuristic program for assembly line balancing / F.M. Tonge. – Englewood Cliffs, NJ : Prentice-Hall, 1961. – 362 p.
9. 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.
10. 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.
11. Freeman, D.R. A general line balancing model / D.R. Freeman // Proc. 19th Annual Conf. AIIE. – Tampa, FLA, 1968. – P. 230–235.
12. Scholl, A. Balancing and sequencing of assembly line / A. Scholl; Second ed. – Heidelberg : Physical-Verlag, 1999. – 532 p.
13. 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.
14. Scholl, A. Balancing assembly lines effectively – A computational comparison / A. Scholl, R. Klein // European J. of Operational Research. – 1999. – Vol. 144. – P. 50–58.
15. 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.
16. Reeve, N.R. Balancing stochastic assembly lines / N.R. Reeve, W.H. Thomas // AIIE Transactions. – 1973. – Vol. 5. – P. 223–229.
17. 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.
18. 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.
19. Shin, D. An efficient heuristic for solving stochastic assembly line balancing problem /D. Shin // Computers and Industrial Engineering. – 1990. – Vol. 18. – P. 285–295.
20. 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.
21. 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.
22. Gen, M. Fuzzy assembly line balancing using genetic algorithms / M. Gen, Y. Tsujimura, Y. Li // Computers inc. Engineering. – 1996. – Vol. 31. – P. 631–634.
23. 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.
24. 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.
25. 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.
26. 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.
27. Сотсков, Ю.Н. Теория расписаний. Системы с неопределенными числовыми параметрами / Ю.Н. Сотсков, Н.Ю. Сотскова. – Минск : ОИПИ НАН Беларуси, 2004. – 290 c.
28. 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.
29. 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.
30. 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.
31. 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.
32. 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.
33. 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.
34. 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.
35. 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.
36. 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.
37. 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.
38. Kravchenko, S. Optimal schedules with infinitely large stability radius / S. Kravchenko, Yu. Sotskov, F. Werner // Optimization. – 1995. – Vol. 33, № 3. – P. 271–280.
39. Sotskov, Yu. Stability of an optimal schedule / Yu. Sotskov // European J. of Operational Research. – 1991. – Vol. 55, № 1. – P. 91–102.
40. Scheduling under uncertainty: Theory and Algorithms / Yu. Sotskov [et al.]. – Minsk : Belorusskaya Nauka, 2010. – 326 p.
41. 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.
42. 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.
43. 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.
44. 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.
45. 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.
46. 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.
47. 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.
48. 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.
49. 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.
50. 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.
51. 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.
Рецензия
Для цитирования:
Сотсков Ю.Н., Затюпо О.С. ЗАДАЧИ БАЛАНСИРОВКИ СБОРОЧНЫХ ЛИНИЙ С НЕОПРЕДЕЛЕННЫМИ ЧИСЛОВЫМИ ПАРАМЕТРАМИ. Информатика. 2013;(4):54-65.
For citation:
Sotskov Yu.N., Zatsiupa A.S. ASSEMBLY LINE BALANCING PROBLEMS WITH UNCERTAIN NUMERICAL PARAMETERS. Informatics. 2013;(4):54-65. (In Russ.)
Просмотров: 914
Послать статью по эл. почте 