Authors:
Kanika Gupta,Deepak Gupta,Sonia Goel,DOI NO:
https://doi.org/10.26782/jmcms.2025.08.00008Keywords:
Idle time,Rental cost,Trapezoidal Fuzzy processing time,Utilization time,Abstract
The paper addresses the classical two-stage FSSP with a single machine in the second stage and equipotential machines in the first. The uniqueness of this problem arises from the fact that the machine at the second stage is rented, with the objective being to minimize the rental cost. Efficient scheduling of jobs is critical in such environments to optimize resource usage and reduce operational costs. A distinguishing feature of this study is the representation of processing times on both stages using trapezoidal fuzzy numbers, which better capture uncertainty and variability in processing times compared to deterministic values. This fuzzy representation aligns well with real-world scenarios where exact processing times are often unavailable or subject to fluctuations. This paper's primary contribution is the creation of an optimization algorithm that uses the branch and bound (B&B) approach to tackle the issue. By breaking the problem space down into smaller subproblems and utilizing bounds to exclude less likely solutions, the B&B technique methodically explores the solution space. This method minimizes the expense of renting the second-stage machine while guaranteeing the identification of the ideal timetable. The fuzzy nature of the problem adds complexity to the scheduling task, as it requires handling the fuzziness in processing times while maintaining optimality. To ensure the robustness of the algorithm, it is implemented in MATLAB and tested against a variety of job sequences and machine configurations, along with the comparison of results with GA.Refference:
I. Alburaikan, Alhanouf, et al. “A Novel Approach for Minimizing Processing Times of Three-Stage Flow Shop Scheduling Problems under Fuzziness.” Symmetry, vol. 15, no. 1, Jan. 2023. 10.3390/sym15010130
II. Alharbi, Majed G., and Hamiden Abd El-Wahed Khalifa. “On a Flow-Shop Scheduling Problem with Fuzzy Pentagonal Processing Time.” Journal of Mathematics, vol. 2021, 2021. 10.1155/2021/6695174
III. Ben-Daya, Mohamed, and M. Al-Fawzan. “A Tabu Search Approach for the Flow Shop Scheduling Problem.” European Journal of Operational Research, vol. 109, no. 1, 1998, pp. 88–95. 10.1016/S0377-2217(97)00136-7
IV. El-Morsy, Salwa, et al. “On Employing Pythagorean Fuzzy Processing Time to Minimize Machine Rental Cost.” AIMS Mathematics, vol. 8, no. 7, 2023, pp. 17259–71. 10.3934/math.2023882.
V. Gupta, Deepak, et al. “3-stage specially structured flow shop scheduling to minimize the rental cost including transportation time, job weightage and job block criteria.” European Journal of Business and Management 7.4 (2015): 1-7. https://www.iiste.org/Journals/index.php/EJBM/article/view/20232
VI. Gupta, Deepak, and Sonia Goel. “Three Stage Flow Shop Scheduling Model with Equipotential Machines.” International Journal on Future Revolution in Computer Science & Communication Engineering IJFRCSCE, 2018. https://www.ijrar.org/papers/IJRAR19J1166.pdf
VII. Gupta, Deepak, and Sonia Goel. “Two Stage Flow Shop Scheduling Model Including Transportation Time with Equipotential Machines at Every Stage.” International Journal of Innovative Technology and Exploring Engineering, vol. 8, no. 12, Oct. 2019, pp. 5090–94. 10.35940/ijitee.L2740.1081219.
VIII. Holland, John H. “Genetic Algorithms.” Scientific American, vol. 267, no. 1, 1992, pp. 66–73. http://www.jstor.org/stable/24939139.
IX. Ignall, Edward, and Linus Schrage. “Application of the Branch and Bound Technique to Some Flow-Shop Scheduling Problems.” Operations Research, vol. 13, no. 3, 1965, pp. 400–12. 10.1287/opre.13.3.400.
X. Johnson, S. M. “With Setup Times Included.” Naval Research Logistics Quarterly, vol. 1, 1954, pp. 61–68. 10.1002/nav.3800010110
XI. Kahraman, Cengiz, et al. “An Application of Effective Genetic Algorithms for Solving Hybrid Flow Shop Scheduling Problems.” International Journal of Computational Intelligence Systems, vol. 1, no. 2, 2008, pp. 134–47. 10.2991/ijcis.2008.1.2.4
XII. Lomnicki, Z. A. “A ‘Branch-and-Bound’ Algorithm for the Exact Solution of the Three-Machine Scheduling Problem.” Or, vol. 16, no. 1, 1965, p. 89, 10.2307/3006687
XIII. Malhotra, Khushboo, and Sonia Goel. Comparison of Bb With Meta-Heuristic Approach in Optimization of Three Stage Fss With Multiple Processors. 2023, https://doi.org/10.21203/rs.3.rs-2822556/v1
XIV. Narain, Laxmi. “Optimize Renting Times of Machines in Flow-Shop Scheduling.” International Journal of Engineering and Applied Sciences, vol. 2, no. 5, 2015, p. 257919. https://www.ijeas.org/download_data/IJEAS0205053.pdf
XV. Nawaz, Muhammad, et al. “A Heuristic Algorithm for the M-Machine, n-Job Flow-Shop Sequencing Problem.” Omega, vol. 11, no. 1, 1983, pp. 91–95. 10.1016/0305-0483(83)90088-9
XVI. Rajkumar, R., and P. Shahabudeen. “An Improved Genetic Algorithm for the Flowshop Scheduling Problem.” International Journal of Production Research, vol. 47, no. 1, Jan. 2009, pp. 233–49, 10.1080/00207540701523041.
XVII. Sathish, Shakeela, and K. Ganesan. “Flow Shop Scheduling Problem to Minimize the Rental Cost under Fuzzy Environment.” Journal of Natural Sciences Research, vol. 2, no. 10, 2012, pp. 62–68. https://www.iiste.org/Journals/index.php/JNSR/article/view/3757/3806.
XVIII. Shahsavari-Pour, Nasser, et al. “A Novel Pareto-Optimal Algorithm for Flow Shop Scheduling Problem.” Mathematics 2024, Vol. 12, Page 2951, vol. 12, no. 18, Sep. 2024, p. 2951. 10.3390/MATH12182951
XIX. Singla, Shakuntala, et al. “No Idle Flow Shop Scheduling Models with Separated Set-up Times and Concept of Job Weightage to Optimize Rental Cost of Machines.” Journal of Project Management (Canada), vol. 9, no. 2, Apr. 2024, pp. 101–08. 10.5267/j.jpm.2024.2.001
XX. Tang, Jianchao, et al. “Hybrid Genetic Algorithm for Flow Shop Scheduling Problem.” 2010 International Conference on Intelligent Computation Technology and Automation, vol. 2, 2010, pp. 449–52. 10.1109/ICICTA.2010.767
XXI. Tomazella, Caio Paziani, and Marcelo Seido Nagano. “A Comprehensive Review of Branch-and-Bound Algorithms: Guidelines and Directions for Further Research on the Flowshop Scheduling Problem.” Expert Systems with Applications, vol. 158, Elsevier Ltd, 15 Nov. 2020. 10.1016/j.eswa.2020.113556
XXII. Umam, Moch Saiful, et al. “A Hybrid Genetic Algorithm and Tabu Search for Minimizing Makespan in Flow Shop Scheduling Problem.” Journal of King Saud University – Computer and Information Sciences, vol. 34, no. 9, Oct. 2022, pp. 7459–67, 10.1016/j.jksuci.2021.08.025
XXIII. Wang, L., et al. “A Class of Hypothesis-Test-Based Genetic Algorithms for Flow Shop Scheduling with Stochastic Processing Time.” International Journal of Advanced Manufacturing Technology, vol. 25, no. 11–12, Jun. 2005, pp. 1157–63. 10.1007/S00170-003-1961-Y/METRICS.