ENG  Vol.6 No.13 , December 2014
A Branch-and-Bound Based Heuristic Algorithm for Minimizing Makespan in Machining-Assembly Flowshop Scheduling
Author(s) Kazuko Morizawa
Abstract
This paper proposes a heuristic algorithm, called list-based squeezing branch and bound algorithm, for solving a machine-fixed, machining-assembly flowshop scheduling problem to minimize makespan. The machine-fixed, machining-assembly flowshop consists of some parallel two-machine flow lines at a machining stage and one robot at an assembly stage. Since an optimal schedule for this problem is not always a permutation schedule, the proposed algorithm first finds a promising permutation schedule, and then searches better non-permutation schedules near the promising permutation schedule in an enumerative manner by elaborating a branching procedure in a branch and bound algorithm. The results of numerical experiments show that the proposed algorithm can efficiently provide an optimal or a near-optimal schedule with high accuracy such as mean relative error being less than 0.2% and the maximum relative error being at most 3%.

Cite this paper
Morizawa, K. (2014) A Branch-and-Bound Based Heuristic Algorithm for Minimizing Makespan in Machining-Assembly Flowshop Scheduling. Engineering, 6, 877-885. doi: 10.4236/eng.2014.613081.
References

[1]   Sun, X., Morizawa, K. and Nagasawa, H. (2003) Powerful Heuristics to Minimize Makespan in Fixed, 3-Machine, Assembly-Type Flowshop Scheduling. European Journal of Operational Research, 146, 498-516.
http://dx.doi.org/10.1016/S0377-2217(02)00245-X

[2]   Johnson, S.M. (1956) An Optimal Two- and Three-Stage Production Scheduling with Setup Time Included. Naval Research Logistics Quarterly, 1, 61-68.
http://dx.doi.org/10.1002/nav.3800010110

[3]   Lee, C.-Y., Cheng, T.C.E. and Lin, B.M.T. (1993) Minimizing the Makespan in the 3-Machine Assembly-Type Flowshop Scheduling Problem. Management Science, 39, 616-625.
http://dx.doi.org/10.1287/mnsc.39.5.616

[4]   Potts, C.N., Sevast’janov, S.V., Strysevich, V.A., Van Wassenhove, L.N. and Zwaneveld, C.M. (1995) The Two-Stage Assembly Scheduling Problem: Complexity and Approximation. Operations Research, 43, 346-355.
http://dx.doi.org/10.1287/opre.43.2.346

[5]   Miyake, Y., Morizawa, K. and Nagasawa, H. (2002) A Branch-and-Bound Algorithm for Minimizing Makespan in a Machine-Fixed, Machining-Assembly Flowshop with Parallel Flowshop Lines. Journal of Japan Industrial Management Association, 53, 292-301.

[6]   Nagasawa, H. and Morizawa, K. (2002) Heuristic Scheduling in Machining-Assembly Flowshop with Parallel Two-Machine Flow Lines at Machining Stage. Journal of Japan Industrial Management Association, 53, 37-46.

[7]   Morizawa, K., Sun, X. and Nagasawa, H. (1998) Squeezing Branch and Bound Algorithm and Its Application to an N/M/F/F Max Problem. Proceedings of 1998 Japan USA Symposium on Flexible Automation, Otsu, 12-15 July 1998, 913-916.

[8]   Morizawa, K., Sun, X. and Nagasawa, H. (2003) Squeezing Branch and Bound Algorithm for the Machine-Fixed, Machining-Assembly Flowshop Scheduling Problem. International Journal of Manufacturing Technology and Management, 5, 20-27.
http://dx.doi.org/10.1504/IJMTM.2003.002526

[9]   Dannenbring, G.D. (1977) An Evaluation of Flowshop Sequencing Heuristics. Management Science, 23, 1174-1182.
http://dx.doi.org/10.1287/mnsc.23.11.1174

 
 
Top