A Branch-and-Bound Based Heuristic Algorithm for Minimizing Makespan in Machining-Assembly Flowshop Scheduling

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

Share and Cite:

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.

Conflicts of Interest

The authors declare no conflicts of interest.

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

Copyright © 2022 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.