Minimizing the Total Waiting Time for Fuzzy Two-Machine Flow Shop Scheduling Problem with Uncertain Processing Time

Authors

  • Ranjith K. Department of Mathematics, School of Advanced Sciences, Vellore Institute of Technology, Vellore, India. https://orcid.org/0009-0006-0635-2949
  • Karthikeyan K. Department of Mathematics, School of Advanced Sciences, Vellore Institute of Technology, Vellore, India. https://orcid.org/0000-0003-3321-8092

DOI:

https://doi.org/10.21123/bsj.2024.10784

Keywords:

Fuzzy flow shop scheduling problem, Fuzzy Logic, Heuristic algorithm, Optimal sequence, Trapezoidal membership function(TrFN), Total waiting time

Abstract

Scheduling involves assigning resources to jobs within specified constraints over time. Traditionally, the processing time for each job was considered a constant value. However, in practical scenarios, job processing times can dynamically fluctuate based on prevailing circumstances. In this article, a novel approach is presented for the two-machine fuzzy Flow-Shop Scheduling Problem (FSSP) in a fuzzy environment, where job processing times are represented by trapezoidal fuzzy numbers. Additionally, a novel algorithm based on Goyal's approach for the two-machine FSSP with fuzzy processing times has been proposed and developed. Simultaneously, an existing algorithm has been enhanced to improve its performance in this specific context. The study aims to minimize the total waiting time for jobs. A defuzzification function is employed to rank fuzzy numbers, with the ultimate goal of minimizing the total waiting time. Furthermore, the article evaluates the performance of these methods in terms of solution quality, using test problems with 10, 20, 30, 40, 50, 60, 80, 90, 100, 120, 200, 250, 300, and 500 jobs, along with 2 machines. The mean total waiting time is compared to existing algorithms, including the NEH algorithm, Palmer’s method, Johnson’s method, B. Goyal and B. Kaur, and the proposed algorithm. Additionally, the obtained results, along with a well-structured ANOVA test, highlight the effectiveness of the proposed method in addressing the scheduling problem under investigation. The experimental results showcase that the proposed algorithm can effectively minimize the waiting time in fuzzy two-machine FSSP and achieve superior results when compared to various existing algorithms.

References

Johnson SM. Optimal Two- and Three-Stage Production Schedules with Setup Times Included. Nav Res Logist Q. 1954 Mar; 1(1): 61–68. https://doi.org/10.1002/nav.3800010110

Palmer DS. Sequencing Jobs Through a Multi-Stage Process in the Minimum Total Time—A Quick Method of Obtaining a Near Optimum. J Oper Res Soc. 1965 Mar; 16(1): 101-107. https://doi.org/10.1057/jors.1965.8

Gupta JND. A Functional Heuristic Algorithm for the Flowshop Scheduling Problem. J Oper Res Soc. 1971; 22(1): 39–47. https://doi.org/10.1057/jors.1971.18

Campbell HG, Dudek RA, Smith ML. A Heuristic Algorithm for the n Job, m Machine Sequencing Problem. Manag Sci. Jun 1970; 16(10): B630-B637. https://www.jstor.org/stable/2628231

Lee ES, Li R-J. Comparison of Fuzzy Numbers Based on the Probability Measure of Fuzzy Events. Comput Math Appl. 1988 Jan 1; 15(10): 887-896. https://doi.org/10.1016/0898-1221(88)90124-1

Liu GS, Tu M, Tang YS, Ding TX. Energy-Aware Optimization for the Two-Agent Scheduling Problem with Fuzzy Processing Times. Int J Interact Des Manuf. 2023 Feb 1; 17(1): 237–248. https://doi.org/10.1007/s12008-022-00927-9

Amat S, Ortiz P, Ruiz J, Trillo JC, Yanez DF. Geometric Representation of the Weighted Harmonic Mean of n Positive Values and Potential Applications. Indian J Pure Appl Math. 2023 Apr 30; 55(2): 794–804. https://doi.org/10.1007/s13226-023-00409-y

Abduljabbar IA, Abdullah SM. An Evolutionary Algorithm for Solving Academic Courses Timetable Scheduling Problem. Baghdad Sci J. 2022 Apr 1; 19(2): 399–408. https://doi.org/10.21123/bsj.2022.19.2.0399

Shen J, Shi Y, Shi J, Dai Y, Li W. An Uncertain Permutation Flow Shop Predictive Scheduling Problem with Processing Interruption. Phys. A: Stat Mech Appl. 2023 Feb 1; 611: 1-15. https://doi.org/10.1016/j.physa.2023.128457

Allahverdi M, Allahverdi A. Minimizing Total Completion Time for Flowshop Scheduling Problem with Uncertain Processing Times. RAIRO–Oper Res. 2021; 55: S929 - S946. https://doi.org/10.1051/ro/2020022

Mehdizadeh E, Soleimaninia F. A Vibration Damping Optimization Algorithm to Solve Flexible Job Shop Scheduling Problems with Reverse Flows. Int J Res Ind Eng. 2023 Dec 1; 12(4): 431-449. https://doi.org/10.22105/riej.2023.383451.1363

Bagheri M, Meybodi NB, Enzebati AH. Modeling and Optimizing a Multi-Objective Flow Shop Scheduling Problem to Minimize Energy Consumption, Completion Time and Tardiness. J Oper Res Decis. 2018 Nov 22; 3(3): 204-222. https://doi.org/10.22105/dmor.2018.81214

Allahverdi M. An Improved Algorithm to Minimize the Total Completion Time in a Two-Machine No-Wait Flow-Shop with Uncertain Setup Times. J Proj Manag. 2022; 7(1): 1-12. https://doi.org/10.5267/j.jpm.2021.9.001

AL-jabr M, Diab A, AL-Diab J. Distributed Heuristic Algorithm for Migration and Replication of Self-Organized Services in Future Networks. Baghdad Sci J. 2022 Dec 1; 19(6): 1335-1345. https://doi.org/10.21123/bsj.2022.6338

Asif MK, Alam ST, Jahan S, Arefin MR. An Empirical Analysis of Exact Algorithms for Solving Non-Preemptive Flow Shop Scheduling Problem. Int J Res Ind Eng. 2022 Sep 1; 11(3): 306-321. http://dx.doi.org/10.22105/riej.2022.350120.1324

McCahon CS, Lee ES. Job Sequencing with Fuzzy Processing Times. Computers Math Applic. 1990 Jan 1; 19(7): 31–41. https://doi.org/10.1016/0898-1221(90)90191-L

Abdullah S, Abdolrazzagh-Nezhad M. Fuzzy Job-Shop Scheduling Problems: A review. Inf Sci. 2014 Sep 10; 278: 380–407. https://doi.org/10.1016/j.ins.2014.03.060

Dubois D, Prade H. Ranking Fuzzy Numbers in the Setting of Possibility Theory. Inf Sci. 1983 Sep 1; 30(3): 183–224. DOI: https://doi.org/10.1016/0020-0255(83)90025-7

Mahfouf M, Abbod MF, Linkens DA. A Survey of Fuzzy Logic Monitoring and Control Utilisation in Medicine. Artif Intell Med. 2001 Jan 1; 21(1-3): 27-42. https://doi.org/10.1016/S0933-3657(00)00072-5

Kiptum CK, Bouraima MB, Badi I, Zonon BIP, Ndiema KM, Qiu Y. Assessment of the Challenges to Urban Sustainable Development Using an Interval-Valued Fermatean Fuzzy Approach. Syst Anal. 2023 Aug 29; 1(1): 11-26. https://doi.org/10.31181/sa1120233

Alburaikan A, Garg H, Khalifa HA. A Novel Approach for Minimizing Processing Times of Three-Stage Flow Shop Scheduling Problems Under Fuzziness. Symmetry. 2023 Jan 2; 15(1): 1-13. https://doi.org/10.3390/sym15010130

Zhou W, Chen F, Ji X, Li H, Zhou J. A Pareto-Based Discrete Particle Swarm Optimization for Parallel Casting Workshop Scheduling Problem with Fuzzy Processing Time. Knowl.-Based Syst. 2022 Nov 28; 256: 1-13. https://doi.org/10.1016/j.knosys.2022.109872

Zubair SAM. Single-Valued Neutrosophic Uncertain Linguistic Set Based on Multi-Input Relationship and Semantic Transformation. J Fuzzy Ext Appl. 2023 Oct 1; 4(4): 257–270. https://doi.org/10.22105/jfea.2023.423474.1319

Akram M, Ullah I, Allahviranloo T, Edalatpanah SA. LR-Type Fully Pythagorean Fuzzy Linear Programming Problems with Equality Constraints. J Intell Fuzzy Syst. 2021; 41(1): 1975–1992. https://doi.org/10.3233/JIFS-210655

Zanjani B, Amiri M, Hanafizadeh P, Salahi M. Robust Multi-Objective Hybrid Flow Shop Scheduling. J Appl Res. Ind Eng. 2021 Mar 1; 8(1): 40-55. https://doi.org/10.22105/jarie.2021. 252651.1202

Edalatpanah SA, Khalifa HA, Keyser RS. A New Approach for Solving Fuzzy Cooperative Continuous Static Games. Soft Comput Fusion Appl. 2024 Jan 15; 1(1): 19-26.

Gupta D, Goyal B. Specially Structured Flow Shop Scheduling in Two Stage with Concept of Job Block and Transportation Time to Optimize Total Waiting Time of Jobs. Int J Eng Technol. 2018 Oct-Nov; 10(5): 1273–1284. https://doi.org/10.21817/ijet/2018/v10i5/181005022

Engin O, Isler M. An Efficient Parallel Greedy Algorithm for Fuzzy Hybrid Flow Shop Scheduling with Setup Time and Lot Size: A Case Study in Apparel Process. J Fuzzy Ext Appl. 2022 Jul 1; 3(3): 249–262. https://doi.org/10.22105/jfea.2021.314312.1169

Bahmani V, Adibi MA, Mehdizadeh E. Integration of Two-Stage Assembly Flow Shop Scheduling and Vehicle Routing Using Improved Whale Optimization Algorithm. J Appl Res Ind Eng. 2023 Mar 1; 10(1): 56–83. https://doi.org/10.22105/jarie.2022.329251.1450

Rouhbakhsh R, Mehdizadeh E, Adibi MA. Presenting a Model for Solving Lot-Streaming Hybrid Flow Shop Scheduling Problem by Considering Independent Setup Time and Transportation Time. J Decis Oper Res. 2023; 8(2): 307–332. https://doi.org/10.22105/dmor.2022.296154.1450

Jain C, Saini RK, Sangal A. Application of Trapezoidal Fuzzy Numbers in the Inventory Problem of Decision Science. Multicriteria Algo Appl. 2024 Mar 12; 3: 1–14. https://doi.org/10.61356/j.mawa.2024.311461

Goyal B, Kaur S. Flow Shop Scheduling-Especially Structured Models Under Fuzzy Environment with Optimal Waiting Time of Jobs. Int J Design Engineering. 2022 Nov; 11(1): 47–60. https://doi.org/10.1504/IJDE.2022.127075

Goyal B, Kaur S. Comparative Performance Analysis of Heuristics with Bicriterion Optimization for Flow Shop Scheduling. In: Das S, Saha S, Coello Coello CA, Bansal JC, editors. Advances in Data-Driven Computing and Intelligent Systems. ADCIS 2022. Lecture Notes in Networks and Systems. Singapore: Springer. 2023; 698: p.653–669. https://doi.org/10.1007/978-981-99-3250-4_50.

Goyal B, Kaur S. Specially Structured Flow Shop Scheduling Models with Processing Times as Trapezoidal Fuzzy Numbers to Optimize Waiting Time of Jobs. In: Tiwari A, Ahuja K, Yadav A, Bansal JC, Deep K, Nagar AK, editors. Soft Computing for Problem Solving. Advances in Intelligent Systems and Computing. Singapore: Springer; 2021; 1393: p. 27-42. https://doi.org/10.1007/978-981-16-2712-5_3

Zhang W, Li C, Gen M, Yang W, Zhang G. A Multiobjective Memetic Algorithm with Particle Swarm Optimization and Q-Learning-Based Local Search for Energy-Efficient Distributed Heterogeneous Hybrid Flow-Shop Scheduling Problem. Expert Syst Appl. 2023 Mar; 237(Part C): 1-20. https://doi.org/10.1016/j.eswa.2023.121570

Behnamian J. Survey on Fuzzy Shop Scheduling. Fuzzy Optim Decis Making. 2016 Sep; 15: 331-366. https://doi.org/10.1007/s10700-015-9225-5

Zimmerman H-J. Fuzzy Set Theory and its Applications. 4th edition. New York: Springer Seience+Business Media; 2001. Chapter 1, Introduction to Fuzzy Sets; p.1-8. https://doi.org/10.1007/978-94-010-0646-0_1

Zadeh LA. Fuzzy Sets Inf Control. 1965; 8(3): 338-353. https://doi.org/10.1016/S0019-9958(65)90241-X

Elizabeth S, Sujatha L. Project Scheduling Method Using Triangular Intuitionistic Fuzzy Numbers and Triangular Fuzzy Numbers. Appl Math Sci. 2015; 9(4): 185–198. http://dx.doi.org/10.12988/ams.2015.410852

Ranjith K, Karthikeyan K. New Algorithm for Two-Machine Fuzzy Flow Shop Scheduling Problem with Trapezoidal Fuzzy Processing Time. J Intell Fuzzy Syst. 2024; 46: 1-14. https://doi.org/10.3233/JIFS-235526

Nawaz M, Enscore EE, Ham I. A Heuristic Algorithm for the m-Machine, n-Job Flow-Shop Sequencing Problem. Omega. 1983; 11(1): 91-95. https://doi.org/10.1016/0305-0483(83)90088-9

Paraveen R, Khurana MK. A Comparative Analysis of SAMP-Jaya and Simple Jaya Algorithms for PFSSP. Soft Comput. 2023 Aug 1; 27(15): 10759–10776. https://doi.org/10.1007/s00500-023-08261-2

Downloads

Issue

Section

article

How to Cite

1.
Minimizing the Total Waiting Time for Fuzzy Two-Machine Flow Shop Scheduling Problem with Uncertain Processing Time. Baghdad Sci.J [Internet]. [cited 2024 Nov. 21];22(5). Available from: https://bsj.uobaghdad.edu.iq/index.php/BSJ/article/view/10784