International Journal of Mathematical, Engineering and Management Sciences

ISSN: 2455-7749

A Robust Expected Makespan for Permutation Flow Shop Scheduling Depending on Machine Failure Rate

Ghazwan Alsoufi
Department of Operations Research and Intelligent Techniques, College of Computer Sciences and Mathematics, University of Mosul, Mosul, Iraq.

Manal Abdulkareem Zeidan
Department of Operations Research and Intelligent Techniques, College of Computer Sciences and Mathematics, University of Mosul, Mosul, Iraq.

Lamyaa Jasim Mohammed
Department of Operations Research and Intelligent Techniques, College of Computer Sciences and Mathematics, University of Mosul, Mosul, Iraq.

Abdellah Salhi
Department of Mathematical Sciences, University of Essex, Colchester, UK.

DOI https://doi.org/10.33889/IJMEMS.2021.6.5.081

Received on March 15, 2021
  ;
Accepted on August 23, 2021

Abstract

The environment of Flow Shop Scheduling Problems (FSSPs) to minimize the makespan of n jobs that have to be performed on m machines is considered. In real-world manufacturing systems nowadays, the uncertain circumstances to execute these jobs have an essential effect on the final scheduling scheme. This paper puts forward an integrated optimization heuristics that combine two distinct factors in flow shop scheduling. These factors are the variation in the processing times and the machine's reliability (machine failure rate), which must be considered to obtain optimal scheduling under stochastic assumptions. Two new approaches have been proposed in this work to achieve a robust expected makespan in the stochastic environment. The procedure is to add buffer time depending on the machine failure rate. Hence, the first procedure is to add buffer time to each operation in the mission according to the reliability of all machines (system reliability). The second one is to add buffer time to each operation depending on the reliability of each machine (machine reliability). For solving this problem with consideration to minimizing the expected makespan and maximizing the robustness simultaneously, the well-known (NEH) heuristic is implemented to schedule a set of jobs. Computational simulations are carried out with some well-studied problems taken from the OR-Library. Experimental results show that the proposed methods provide robust and efficient solutions. Moreover, the effects of some parameters on the optimization performance are discussed.

Keywords- Flow shop scheduling, Machine failure rate, Uncertainty, Robustness

Citation

Alsoufi, G., Zeidan, M. A. Mohammed, L. J. & Salhi, A. (2021). A Robust Expected Makespan for Permutation Flow Shop Scheduling Depending on Machine Failure Rate. International Journal of Mathematical, Engineering and Management Sciences, 6(5), 1345-1360. https://doi.org/10.33889/IJMEMS.2021.6.5.081.

Conflict of Interest

The authors confirm that there is no conflict of interest to declare for this publication.

Acknowledgements

All authors are very grateful to the University of Mosul-Iraq/College of Computer Sciences and Mathematics and the University of Essex-UK for their support to finish this paper.

References

Akhshabi, M., Haddadnia, J., & Akhshabi, M. (2012). Solving flow shop scheduling problem using a parallel genetic algorithm. Procedia Technology, 1, 351-355.

Al-Behadili, M., Ouelhadj, D., & Jones, D. (2020). Multi-objective biased randomised iterated greedy for robust permutation flow shop scheduling problem under disturbances. Journal of the Operational Research Society, 71(11), 1847-1859.

Allaoui, H., & Artiba, A. (2004). Integrating simulation and optimization to schedule a hybrid flow shop with maintenance constraints. Computers & Industrial Engineering, 47(4), 431-450.

Baker, K.R., & Altheimer, D. (2012). Heuristic solution methods for the stochastic flow shop problem. European Journal of Operational Research, 216(1), 172-177.

Balasubramanian, J., & Grossmann, I.E. (2003). Scheduling optimization under uncertainty-an alternative approach. Computers & Chemical Engineering, 27(4), 469-490.

Carlier, J. (1978). Ordonnancements a contraintes disjonctives. RAIRO-Operations Research, 12(4), 333-350.

Celano, G., Costa, A., & Fichera, S. (2003). An evolutionary algorithm for pure fuzzy flowshop scheduling problems. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 11(06), 655-669.

Chaari, T., Chaabane, S., Loukil, T., & Trentesaux, D. (2011). A genetic algorithm for robust hybrid flow shop scheduling. International Journal of Computer Integrated Manufacturing, 24(9), 821-833.

Conway, R.W., Miller, L.W., & Maxwell, W.L. (2003). Theory of scheduling. Dover.

Framinan, J.M., & Perez-Gonzalez, P. (2015). On heuristic solutions for the stochastic flowshop scheduling problem. European Journal of Operational Research, 246(2), 413-420.

Framinan, J.M., Gupta, J.N., & Leisten, R. (2004). A review and classification of heuristics for permutation flow-shop scheduling with makespan objective. Journal of the Operational Research Society, 55(12), 1243-1255.

Gholami-Zanjani, S.M., Hakimifar, M., Nazemi, N., & Jolai, F. (2017). Robust and fuzzy optimization models for a flow shop scheduling problem with sequence dependent setup times: A real case study on a PCB assembly company. International Journal of Computer Integrated Manufacturing, 30(6), 552-563.

González-Neira, E., Montoya-Torres, J., & Barrera, D. (2017). Flow-shop scheduling problem under uncertainties: Review and trends. International Journal of Industrial Engineering Computations, 8(4), 399-426.

González-Neira, E.M., Urrego-Torres, A.M., Cruz-Riveros, A.M., Henao-Garcia, C., Montoya-Torres, J.R., Molina-Sánchez, L.P., & Jimenez, J.F. (2019). Robust solutions in multi-objective stochastic permutation flow shop problem. Computers & Industrial Engineering, 137, 106026.

Gourgand, M., Grangeon, N., & Norre, S. (2000). A review of the static stochastic flow-shop scheduling problem. Journal of Decision Systems, 9(2), 1-31.

Gourgand, M., Grangeon, N., & Norre, S. (2003). A contribution to the stochastic flow shop scheduling problem. European Journal of Operational Research, 151(2), 415-433.

Gourgand, M., Grangeon, N., & Norre, S. (2005). Markovian analysis for performance evaluation and scheduling in m machine stochastic flow-shop with buffers of any capacity. European Journal of Operational Research, 161(1), 126-147.

Huang, C.S., Huang, Y.C., & Lai, P.J. (2012). Modified genetic algorithms for solving fuzzy flow-shop scheduling problems and their implementation with CUDA. Expert Systems with Applications, 39(5), 4999-5005.

Ignall, E., & Schrage, L. (1965). Application of the branch and bound technique to some flow-shop scheduling problems. Operations Research, 13(3), 400-412.

Jensen, M.T. (2003). Generating robust and flexible job shop schedules using genetic algorithms. IEEE Transactions on Evolutionary Computation, 7(3), 275-288.

Juan, A.A., Barrios, B.B., Vallada, E., Riera, D., & Jorba, J. (2014). A simheuristic algorithm for solving the permutation flow shop problem with stochastic processing times. Simulation Modelling Practice and Theory, 46, 101-117.

Katragjini, K., Vallada, E., & Ruiz, R. (2013). Flow shop rescheduling under different types of disruption. International Journal of Production Research, 51(3), 780-797.

Li, X., & Yin, M. (2013). A hybrid cuckoo search via Lévy flights for the permutation flow shop scheduling problem. International Journal of Production Research, 51(16), 4732-4754.

Liu, Q., Ullah, S., & Zhang, C. (2011). An improved genetic algorithm for robust permutation flow-shop scheduling. The International Journal of Advanced Manufacturing Technology, 56(1), 345-354.

Michael, L.P. (2018). Scheduling: theory, algorithms, and systems. Springer-Verlag, New York.

Nakhaeinejad, M., & Nahavandi, N. (2013). An interactive algorithm for multi-objective flow shop scheduling with fuzzy processing time through resolution method and TOPSIS. The International Journal of Advanced Manufacturing Technology, 66(5), 1047-1064.

Nawaz, M., Enscore Jr, E.E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91-95.

Policella, N., Oddi, A., Smith, S.F., & Cesta, A. (2004, September). Generating robust partial order schedules. In 2006 International Conference on Principles and Practice of Constraint Programming (pp. 496-511). Springer. Berlin, Heidelberg.

Rahmani, D., & Heydari, M. (2014). Robust and stable flow shop scheduling with unexpected arrivals of new jobs and uncertain processing times. Journal of Manufacturing Systems, 33(1), 84-92.

Rahmani, D., Ramezanian, R., & Saidi-Mehrabad, M. (2014). Multi-objective flow shop scheduling problem with stochastic parameters: fuzzy goal programming approach. International Journal of Operational Research, 21(3), 322-340.

Reeves, C.R. (1995). A genetic algorithm for flowshop sequencing. Computers & Operations Research, 22(1), 5-13.

Rinnooy Kan, A.H.G. (1976). Machine scheduling problem: classification, complexity and computation. Springer US, Nijhoff, The Hague.

Swaminathan, R., Pfund, M.E., Fowler, J.W., Mason, S.J., & Keha, A. (2007). Impact of permutation enforcement when minimizing total weighted tardiness in dynamic flowshops with uncertain processing times. Computers & Operations Research, 34(10), 3055-3068.

Temİz, İ., & Erol, S. (2004). Fuzzy branch-and-bound algorithm for flow shop scheduling. Journal of Intelligent Manufacturing, 15(4), 449-454.

Wang, L., Zhang, L., & Zheng, D.Z. (2005a). A class of hypothesis-test-based genetic algorithms for flow shop scheduling with stochastic processing time. The International Journal of Advanced Manufacturing Technology, 25(11), 1157-1163.

Wang, L., Zhang, L., & Zheng, D.Z. (2005b). Genetic ordinal optimisation for stochastic flow shop scheduling. The International Journal of Advanced Manufacturing Technology, 27(1-2), 166-173.

Xu, W.J., He, L.J., & Zhu, G.Y. (2021). Many-objective flow shop scheduling optimization with genetic algorithm based on fuzzy sets. International Journal of Production Research, 59(3), 702-726.

Zanjani, B., Amiri, M., Hanafizadeh, P., & Salahi, M. (2021). Robust multi-objective hybrid flow shop scheduling. Journal of Applied Research on Industrial Engineering, 8(1), 40-55.

Privacy Policy| Terms & Conditions