Applying Branch-and-Bound and Petri Net Methods in Solving the Two-Sided Assembly Line Balancing Problem

Authors: Nai-Chieh Wei, I-Ming Chao, Chin-Jung Liuand, Hong Long Chen

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.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1090727

References:

[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.