ASSEMBLY LINE BALANCING PROBLEMS WITH UNCERTAIN NUMERICAL PARAMETERS
Abstract
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.
About the Authors
Yu. N. Sotskov
Объединенный институт проблем информатики НАН Беларуси
Russian Federation
Russian Federation
A. S. Zatsiupa
Объединенный институт проблем информатики НАН Беларуси
Russian Federation
Russian Federation
References
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. Sotskov, Yu.N. Teoriya raspisanii. Sistemy s neopredelennymi chislovymi parametrami / Yu.N. Sotskov, N.Yu. Sotskova. - Minsk : OIPI NAN Belarusi, 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, A. 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. - R. 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. - R 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. - R. 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. - R. 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. - R. 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. - R. 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. - R. 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.
Review
For citations:
Sotskov Yu.N., Zatsiupa A.S. ASSEMBLY LINE BALANCING PROBLEMS WITH UNCERTAIN NUMERICAL PARAMETERS. Informatics. 2013;(4):54-65. (In Russ.)
Views: 951
ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)
ISSN 2617-6963 (Online)
Email this article 