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

Kazuko Morizawa

Graduate School of Engineering, Osaka Prefecture University, Osaka, Japan.

DOI: 10.4236/eng.2014.613081                

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

Keywords

Scheduling, Heuristic, Branch and Bound Algorithm, Machining-Assembly Flowshop, Makespan

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