Citation :

Choi Seong-Woo, "B&B Algorithms for Minimization of Total Weighted Flowtime in Two-Machine Flowshop with Re-Entrant Flow," International Journal of Engineering Trends and Technology (IJETT), vol. 73, no. 12, pp. 297-305, 2025. Crossref, https://doi.org/10.14445/22315381/IJETT-V73I12P124

Abstract

This research investigates the two-machine re-entrant permutation flowshop scheduling problem in which every job undergoes two consecutive processing cycles through the same pair of machines following the sequence M₁ → M₂ → M₁ → M₂. The aim of this problem is the minimization of the total weighted flowtime, and branch and bound algorithms are developed that integrate newly formulated dominance rules, a lower-bounding procedure, and an effective heuristic to generate high-quality initial schedules. The algorithm’s efficiency is evaluated using extensive computational experiments on randomly generated instances. The experiments confirm that the suggested branch and bound algorithm can identify optimal schedules while significantly reducing computation time by integrating some dominance rules, a lower-bounding procedure, and an effective heuristic.

Keywords

Branch-and-Bound, Dominance Rule, Lower Bound, Heuristic, Re-entrant Flowshop, Weighted Flowtime.

References

[1] BongJoo Jeong, and Yeong-Dae Kim, “Minimizing Total Tardiness in a Two-Machine Re-Entrant Flowshop with Sequence-Dependent Setup Times,” Computers & Operations Research, vol. 47, pp. 72-80, 2014.
[CrossRef] [Google Scholar] [Publisher Link]

[2] JC-H Pan, and J-S.Chen, “Minimizing Makespan in Re-Entrant Permutation Flow-Shops,” Journal of the Operational Research Society, vol. 54, no. 6, pp. 642-653, 2003.
[CrossRef] [Google Scholar] [Publisher Link]

[3] Maximilian von Aspern et al., “Flow Shops with Reentry: The Total Weighted Completion Time Objective,” arXiv Preprint, pp. 1-19, 2024.
[CrossRef] [Google Scholar] [Publisher Link]

[4] Jingwen Yuan et al., “Scheduling Reentrant Flow Shops: Reinforcement Learning Guided Meta-Heuristics,” IET Collaborative Intelligent Manufacturing, vol. 7, no. 1, 2025.
[CrossRef] [Google Scholar] [Publisher Link]

[5] Hongtao Tang et al., “Hybrid Flowshop Scheduling Problems with Missing and Reentrant Operations Considering Process Scheduling and Energy Consumption,” Sustainability, vol. 15, no. 10, pp. 1-19, 2023.
[CrossRef] [Google Scholar] [Publisher Link]

[6] Stephen C. Graves et al., “Scheduling of Re-Entrant Flow Shops,” Journal of Operations Management, vol. 3, no. 4, pp. 197-207, 1983.
[CrossRef] [Google Scholar] [Publisher Link]

[7] F. Della Croce, V. Narayan, and R. Tadei, “The Two-Machine Total Completion Time Flow Shop Problem,” European Journal of Operational Research, vol. 90, no. 2, pp. 227-237, 1996.
[CrossRef] [Google Scholar] [Publisher Link]

[8] J.A. Hoogeveen, and S.L. van de Velde, “Stronger Lagrangean Bounds by Use of Slack Variables: Application to Machine Scheduling Problems,” Mathematical Programming, vol. 70, no. 1-3, pp. 173-190, 1995.
[CrossRef] [Google Scholar] [Publisher Link]

[9] Edward Ignall, and Linus Schrage, “Application of the Branch-and-Bound Technique to Some Flow Shop Problems,” Operations Research, vol.  13, no. 3, pp. 400-412, 1965.
[CrossRef] [Google Scholar] [Publisher Link]

[10] Ebru Demirkol, and Reha Uzsoy, “Decomposition Methods for Reentrant Flow Shops with Sequence Dependent Setup Times,” Journal of Scheduling, vol. 3, no. 3, pp. 115-177, 2000.
[CrossRef] [Google Scholar] [Publisher Link]

[11] Michael R. Garey, and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completenessv San Francisco, W.H. Freeman and Company, 1979.
[Google Scholar]

[12] Jeffrey Schaller, “Note on Minimizing Total Tardiness in a Two-Machine Flowshop,” Computers & Operations Research, vol. 32, no. 12, pp. 3273-3281, 2005.
[CrossRef] [Google Scholar] [Publisher Link]

[13] Kenneth R. Baker, Introduction to Sequencing and Scheduling, New York: John Wiley & Sons, 1974.
[Google Scholar]

[14] Dragoslav S. Mitrinović, Analytic Inequalities, Berlin: Springer, 1970.
[Google Scholar] [Publisher Link]

[15] Muhammad Nawaz, E Emory Enscore Jr, and Inyong Ham, “A Heuristic Algorithm for the M-Machine, N-Job Flow-Shop Scheduling Problem,” Omega, vol.  11, no. 1, pp. 91-95, 1983.
[CrossRef] [Google Scholar] [Publisher Link]