Applying Branch-and-Bound and Petri Net Methods in Solving the Two-Sided Assembly Line Balancing Problem
This paper combines the branch-and-bound method and the petri net to solve the two-sided assembly line balancing problem, thus facilitating effective branching and pruning of tasks. By integrating features of the petri net, such as reachability graph and incidence matrix, the propose method can support the branch-and-bound to effectively reduce poor branches with systematic graphs. Test results suggest that using petri net in the branching process can effectively guide the system trigger process, and thus, lead to consistent results.
[1] Kim Y.K., Song W.S., and Kim J.H. (2009), A mathematical model and a genetic algorithm for two-sided assembly line balancing, Computers & Operations Research, vol. 36, pp.853–865.
[2] Ugur O., and Bilal T. (2009),Multiple-criteria decision-making in two-sided assembly line balancing a goal programming and a fuzzy goal programming models, Computers & Operations Research, vol. 36, pp. 1955–1965.
[3] Hu X. F., Wu E. F., Bao J. S., and Jin Y. A. (2010), A branch-and-bound algorithm to minimize the line length of a two-sided assembly line, European Journal of Operational Research, vol. 206, pp. 703–707.
[4] Bartholdi J.J.(1993),Balancing two-sided assembly lines – A case study, International Journal of Production Research, vol. 31,pp. 2447–2461.
[5] Lee T. K., Kim Y., and Kim Y. K.(2001), Two-sided assembly line balancing to maximize work relatedness and slackness, Computers & Industrial Engineering, vol. 40, pp. 273–292.
[6] Scholl A., and Becker C. (2006), State-of-the-art exact and heuristic solution procedures for simple assembly line balancing, European Journal of Operational Research, vol. 168, pp. 666–693.
[7] Baykasoglu A. and Dereli T. (2008), Two-sided assembly line balancing using an ant colony-based heuristic, International Journal of Advanced Manufacturing Technology, vol. 36, pp. 582–588.
[8] Klein R., and Scholl A.(1996), Maximizing the production rate in simple assembly line balancing – A branch-and-bound procedure, European Journal of Operational Research, vol. 91, pp. 367–385.
[9] Wu E.F., Jin Y., Bao J. S., and Hu X.F.(2008), A branch-and-bound algorithm for two sided assembly line balancing, International Journal of Advanced Manufacturing Technology, vol. 39, pp. 1009–1015.
[10] Ozcan K. (2011), Firing sequences backward algorithm for simple assembly line balancing problem of type 1, Computers & Industrial Engineering, vol. 60, pp.830–839.
[11] Ozcan U., and Toklu B.(2009), Multiple-criteria decision-making in two-sided assembly line balancing: A goal programming and a fuzzy goal programming models, Computers & Operations Research, vol. 36, pp. 1955–1965.
[12] Simaria A. S., and Vilarinho P. M. (2009), 2-ANTBAL – An ant colony optimization algorithm for balancing two-sided assembly lines, Computers & Industrial Engineering, vol. 56, pp. 489–506.
[1] Kim Y.K., Song W.S., and Kim J.H. (2009), A mathematical model and a genetic algorithm for two-sided assembly line balancing, Computers & Operations Research, vol. 36, pp.853–865.
[2] Ugur O., and Bilal T. (2009),Multiple-criteria decision-making in two-sided assembly line balancing a goal programming and a fuzzy goal programming models, Computers & Operations Research, vol. 36, pp. 1955–1965.
[3] Hu X. F., Wu E. F., Bao J. S., and Jin Y. A. (2010), A branch-and-bound algorithm to minimize the line length of a two-sided assembly line, European Journal of Operational Research, vol. 206, pp. 703–707.
[4] Bartholdi J.J.(1993),Balancing two-sided assembly lines – A case study, International Journal of Production Research, vol. 31,pp. 2447–2461.
[5] Lee T. K., Kim Y., and Kim Y. K.(2001), Two-sided assembly line balancing to maximize work relatedness and slackness, Computers & Industrial Engineering, vol. 40, pp. 273–292.
[6] Scholl A., and Becker C. (2006), State-of-the-art exact and heuristic solution procedures for simple assembly line balancing, European Journal of Operational Research, vol. 168, pp. 666–693.
[7] Baykasoglu A. and Dereli T. (2008), Two-sided assembly line balancing using an ant colony-based heuristic, International Journal of Advanced Manufacturing Technology, vol. 36, pp. 582–588.
[8] Klein R., and Scholl A.(1996), Maximizing the production rate in simple assembly line balancing – A branch-and-bound procedure, European Journal of Operational Research, vol. 91, pp. 367–385.
[9] Wu E.F., Jin Y., Bao J. S., and Hu X.F.(2008), A branch-and-bound algorithm for two sided assembly line balancing, International Journal of Advanced Manufacturing Technology, vol. 39, pp. 1009–1015.
[10] Ozcan K. (2011), Firing sequences backward algorithm for simple assembly line balancing problem of type 1, Computers & Industrial Engineering, vol. 60, pp.830–839.
[11] Ozcan U., and Toklu B.(2009), Multiple-criteria decision-making in two-sided assembly line balancing: A goal programming and a fuzzy goal programming models, Computers & Operations Research, vol. 36, pp. 1955–1965.
[12] Simaria A. S., and Vilarinho P. M. (2009), 2-ANTBAL – An ant colony optimization algorithm for balancing two-sided assembly lines, Computers & Industrial Engineering, vol. 56, pp. 489–506.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:66456", author = "Nai-Chieh Wei and I-Ming Chao and Chin-Jung Liuand and Hong Long Chen", title = "Applying Branch-and-Bound and Petri Net Methods in Solving the Two-Sided Assembly Line Balancing Problem", abstract = "This paper combines the branch-and-bound method and the petri net to solve the two-sided assembly line balancing problem, thus facilitating effective branching and pruning of tasks. By integrating features of the petri net, such as reachability graph and incidence matrix, the propose method can support the branch-and-bound to effectively reduce poor branches with systematic graphs. Test results suggest that using petri net in the branching process can effectively guide the system trigger process, and thus, lead to consistent results.
", keywords = "Branch-and-Bound Method, Petri Net, Two-Sided Assembly Line Balancing Problem.", volume = "8", number = "1", pages = "158-6", }
