Proposed a branch and bound algorithm for Assembly flow shop scheduling problem

Document Type : Research Paper

Authors

Abstract

Assembly flow shop production system includes two stages. In the first stage that is usually assumed one station with some parallel machines, the parts are processed. The second stage is an assembly station (or line) to assemble the parts and complete the products. Suppose that a number of products of different kinds are ordered to be produced and each product needs a set of several parts to complete. Some of the parts are common and some others are unique for each product. Therefore it is important to study the setup times and batch production. The aim is to schedule the parts for process and the products for assembly with the minimum complete time objective. Literature review shows that the considered problem is a NP-Hard problem, so the problem characteristics and its parameters are defined and then a branch and bound algorithm is introduced to solve the small and mediocre problems. Some lower bounds and upper bounds are improved to increase the algorithm efficiency. Finally, a variety of problem is designed and performance of the proposed algorithm is evaluated in solving this problems.

Keywords

References

 
[1] Jolai, F.,Moattar Hosseini, S.M., Hosseini, S.M.H., (2004). Flow Shop Scheduling Problem withMinimizing Earliness/Tardiness Criteria, Amirkabir Journal of Science & Technology, 15:452-461.
[2] Yokoyama, M., Santos, D.L. (2005). Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times, European Journal of Operational Research, 161: 754-770.
[3] Lee, C.Y., Cheng, T.C.E., Lin, B.M.T. (1993). Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem, Management Science, 39: 616-625.
[4] Potts, C.N., Sevast'Janov, S.V., Strusevich, V. A., Van Wassenhove, L.N., Zwaneveld, C.M. (1995). The two-stage assembly scheduling problem: Complexity and approximation,  Operations Research, 43: 346-355.
[5] Hariri, A.M.A, Potts, C.N. (1997). A branch and bound algorithm for the two-stage assembly scheduling problem, European Journal of Operational Research 103:547-556.
[6] Haouari, M., Daouas, T. (1999). Optimal scheduling of the 3-machine assembly-type flow shop, RAIRO Recherche Operationnelle, 33: 439–450.
[7] Allahverdi, A., Al-Anzi, F. S. (2009). The two-stage assembly scheduling problem to minimize total completion time with setup times, Computers & Operations Research, 36:2740-2747.
[8] Al-Anzi, F.S., Allahverdi, A., (2007). A self-adaptive differential evolution heuristic for two stage assembly scheduling problem to minimize maximum lateness with setup time, European Journal of Operational Research, 182: 80-94.
[9] Torabzadeh, E., Zandieh M., (2010). Cloud theory-based simulated annealing approach for scheduling in the two-stage assembly flowshop, Advances in Engineering Software, 41: 1238-1243.
[10] Fattahi, P., Hosseini, S.M.H., Jolai, F. (2012). A mathematical model and extension algorithm for assembly flexible flow shop scheduling problem, International Journal of Advance Manufacture Technology, DOI 10.1007/s00170-012-4217-x.
[11] Navaei, J., Fatemi Ghomi, S.M.T., Jolai, F., Mozdgir, A., (2014). Heuristics for an assembly flow-shop with non-identical assembly machines and sequence dependent setup times to minimize sum of holding and delay costs, Computers & Operations Research, 44: 52-65.
[12] ] Fatahi, P., Hosseini, S.M.H., Jolai, F., Tavakkoli-Moghaddam, R., (2014). A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations, Applied Mathematical Modelling, 38: 119:134.
[13] Yokoyama, M., Santos, D.L. (2005). Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times. European Journal of Operational Research, 161:754-770.
[14] Karimi Haghighi, A. (1389). Solving the flow shop scheduling problem in order to minimize the mean job completion time in the 3-stage assembly line by using the meta-heuristic approach, Payam-e-Noor University, Department of Industrial Engineering, MSc thesis.
[15] Hatami, S., Ebrahimnejad, S., Tavakoli-Moghadam, R., Maboudian, Y., (2010). Two meta-heuristics for three-stage assembly flowshop scheduling with sequence-dependent setup time, International Journal of Advanced Manufacturing Technology, 50: 1153-1164.
[16] Maleki-Darounkolaei, A., Modiri, M., Tavakoli-Moghadam, R., Seyyedi, I., (2012). A three-stage assembly flow shop scheduling problem with blocking and sequence-dependent set up times, Journal of Industrial Engineering-International, 1: 8-26.
[17] Brah S. A., and Hunsuchker, J. L., 1991. Branch and bound algorithm for the flow shop with multiple processors. European Journal of Operational Research, 51, 88–o99.
[18] S.O. Shim, Y.D. Kim, A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property, Computers & Operations Research 35 (2008) 863 – 875.
[19] S.O. Shim, Generating sub problems in branch and bound algorithms for parallel machines scheduling problem, Computers & Industrial Engineering 57 (2009) 1150–1153.
Journal of Modeling in Engineering
Volume 15, Issue 51
October 2017
Pages 85-98

Files

History

  • Receive Date: 25 January 2015
  • Accept Date: 23 December 2015

Share

How to cite

Statistics