Flexible flow shop scheduling problem to minimize makespan with renewable resources

Document Type : Article


Department of Industrial Engineering, Babol Noshirvani University of Technology, Babol, Iran


This paper deals with a flexible flow shop (FFS) scheduling problem with unrelated parallel machines and renewable resource shared among the stages. The FFS scheduling problem is one of the most common manufacturing environment in which there is more than a machine in at least one production stage. In such a system, to decrease the processing times, additional renewable resources are assigned to the jobs or machines, and it can lead to decrease the total completion time. For this purpose, a mixed integer linear programming (MILP) model is proposed to minimize the maximum completion time (makespan) in an FFS environment. The proposed model is computationally intractable. Therefore, a particle swarm optimization (PSO) algorithm as well as a hybrid PSO and simulated annealing (SA) algorithm named SA-PSO, are developed to solve the model. Through numerical experiments on randomly generated test problems, the authors demonstrate that the hybrid SA-PSO algorithm outperforms the PSO, especially for large size test problems.


Main Subjects

References    1. Su, L. and Lien, C. Scheduling parallel machines with    resource-dependent processing times", Int. J. Prod.    Res. 117, pp. 256{266 (2009).    2. Gholami, H.R., Mehdizadeh E., and Naderi, B. Mathematical    models and an elephant herding optimization    for multiprocessor-task exible ow shop scheduling    problems in the manufacturing resource planning (MRPII)    system", Sci. Iran, 27(3), pp. 1562{1571 (2020).    3. Ebrahimi, M., Fatemi Ghomi, S.M.T., and Karimi, B.    Hybrid ow shop scheduling with sequence dependent    family setup time and uncertain due dates", Appl.    Math. Model, 38, pp. 2490{2540 (2014).    4. Asadi-Gangraj, E. Lagrangian relaxation approach to    minimize makespan for hybrid ow shop scheduling    problem with unrelated parallel machines", Sci. Iran.,    5, pp. 3765{3775 (2018).    5. Zabihzadeh, S.S. and Rezaeian, J. Two meta-heuristic    algorithms for exible ow shop scheduling problem    with robotic transportation and release time", Appl.    Soft. Comput., 30, pp. 319-330 (2016).    6. Karimi, N., Zandieh, M., and Karamooz, H.R. Biobjective    group scheduling in hybrid exible owshop:    a multi-phase approach", Expert. Syst. Appl., 37, pp.    4024{4032 (2010).    7. Shahvari, O. and Logendran, R. A comparison of two    stage-based hybrid algorithms for a batch scheduling    problem in hybrid ow shop with learning e_ect", Int.    J. Prod. Econ., 195, pp. 227{248 (2018).    8. Almeder, C. and Hartl, R.F. A metaheuristic optimization    approach for a real-world stochastic exible    ow shop problem with limited bu_er", Int. J. Prod.    Econ., 145, pp. 88{95 (2013).    9. Besbes, W., Teghem, J., and Loukil, T. Scheduling    hybrid ow shop problem with non-_xed availability    constraints", Eur. J. Ind. Eng., 4, pp. 413{433 (2010).    10. Sangsawang, C., Sethanan, K., Fujimoto, T., and    Gen, M. Metaheuristics optimization approaches for    two-stage reentrant exible ow shop with blocking    constraint", Expert. Syst. Appl., 42, pp. 2395{2410    (2015).    11. Jolai, F., Ase_, H., Rabiee, M., and Ramezani, P. Biobjective    simulated annealing approaches for no-wait    two-stage exible ow shop scheduling problem", Sci.    Iran., 20, pp. 861{872 (2013).    12. Akrami, B., Karimi, B., and Moattar Hosseini, S.M.    Two metaheuristic methods for the common cycle    economic lot sizing and scheduling in exible ow    shops with limited intermediate bu_ers: The _nite    horizon case", Appl. Math. Comp., 183, pp. 634{645    (2006).    13. Marichelvam, M.K., Prabaharan, T., and Yang, X.S.    Improved cuckoo search algorithm for hybrid ow    shop scheduling problems to minimize makespan",    Appl. Soft. Comput., 19, pp. 93{101 (2014).    14. Choong, F., Phon-Amnuaisuk, S., and Alias, M.Y.    Metaheuristic methods in hybrid ow shop scheduling    problem", Expert. Syst. Appl., 38, pp. 10787{10793    (2011).    15. Chung, T. and Liao, C. An immunoglobulin-based    arti_cial immune system for solving the hybrid ow    shop problem", Appl. Soft. Comput., 13, pp. 3729{    3736 (2013).    16. Dios, M., Fernandez-Viagas, V., and Framinan, J.M.    E_cient heuristics for the hybrid ow shop scheduling    problem with missing operations", Comput. Ind. Eng.,    115, pp. 88{99 (2018).    17. Behnamian, J. and Fatemi Ghomi, S.M.T. Hybrid    owshop scheduling with machine and resourcedependent    processing times", Appl. Math. Model., 35,    pp. 1107{1123 (2011).    N. Abbaszadeh et al./Scientia Iranica, Transactions E: Industrial Engineering 28 (2021) 1853{1870 1869    18. Jungwattanakit, J., Reodecha, M., Chaovalitwongse,    P., and Werner, F.A. Comparison of scheduling algorithms    for exible ow shop problems with unrelated    parallel machines, setup times, and dual criteria",    Comput. Oper. Res., 36, pp. 358{378 (2009).    19. Edis, E.B. and Oguz, C. Parallel machine scheduling    with exible resources", Comput. Ind. Eng., 63, pp.    433{447 (2009).    20. Yin, N., Kang, L., Sun, T., Yue, C., and Wang, X.    Unrelated parallel machines scheduling with deteriorating    jobs and resource dependent processing times",    Appl. Math. Model., 38, pp. 4747{4755 (2014).    21. Figielska, E. A new heuristic for scheduling the twostage    owshop with additional resources", Comput.    Ind. Eng., 54, pp. 750{763 (2008).    22. Figielska, E. Heuristic algorithms for preemptive    scheduling in a two-stage hybrid owshop with additional    renewable resources at each stage", Comput.    Ind. Eng., 59, pp. 509{519 (2010).    23. Figielska, E. Linear programming and metaheuristic    approach for scheduling in the hybrid owshop with    resource constraints", Control. Cybern., 4, pp. 1209{    1230 (2011).    24. Li, K., Shi, Y., Yang, S., and Cheng, B. Parallel    machine scheduling problem to minimize the makespan    with resource dependent processing times", Appl. Soft.    Comput., 11, pp. 5551{5557 (2011).    25. Liu, Y. and Feng, Z. Two-machine no-wait owshop    scheduling with learning e_ect and convex resourcedependent    processing times", Comput. Ind. Eng., 75,    pp. 170{175 (2014).    26. Kellerer, H. An approximation algorithm for identical    parallel machine scheduling with resource dependent    processing times", Oper. Res. Lett., 36, pp. 157{159    (2008).    27. Jun, P., Xinbao, L., Baoyu, L., Pardalos, P.M.,    and Min, K. Single-machine scheduling with learning    e_ect and resource-dependent processing times in the    serial-batching production", Appl. Math. Model., 58,    pp. 245{253 (2018).    28. Wang, X. and Wang, J. Single-machine scheduling    with convex resource dependent processing times and    deteriorating jobs", Appl. Math. Model., 37, pp. 2388{    2393 (2013).    29. Wei, C. and Ji, P. Single-machine scheduling with    time-and-resource-dependent processing times", Appl.    Math. Model., 36, pp. 792{798 (2012).    30. Wang, D., Wang, M., and Wang, J. Single-machine    scheduling with learning e_ect and resource-dependent    processing times", Comput. Ind. Eng., 59, pp. 458{462    (2010).    31. Wang, X. and Cheng, T.C.E. Single machine scheduling    with resource dependent release times and processing    times", Eur. J. Oper. Res., 162, pp. 727{739    (2005).    32. Nguyen, S., Thiruvady, D., Ernst, A.T., and Alahakoon,    D. A hybrid di_erential evolution algorithm    with column generation for resource constrained job    scheduling", Comput. Oper. Res., 109, pp. 273{287    (2019). Doi: https://doi.org/10.1016/j.cor.2019.05.009    33. Gupta, J.N.D., Kruger, K., Lau_, V., Werner, F.,    and Sotskov, Y.N. Heuristics for hybrid ow shops    with controllable processing times and assignable due    dates", Comput. Oper. Res., 29, pp. 1417{1439 (2002).    34. Kennedy, J. and Eberhart, R.C. Particle swarm    optimization", Proceedings of the IEEE International    Conference on Neural Networks, 4, pp. 1942{1948    (1995).    35. Poonthalir, G., Nadarajan, R., and Geetha, S. Vehicle    routing problem with limited refueling halts using    particle swarm optimization with greedy mutation    operator", RAIRO-Oper. Res., 49, pp. 689{716 (2015).    36. Nayeri, S., Asadi-Gangraj, E., and Emami, S. Metaheuristic    algorithms to allocate and schedule of the    rescue units in the natural disaster with fatigue e_ect",    Neural Comput. Appl., 31, pp. 7517{7537 (2019). Doi:    https://doi.org/10.1007/s00521-018-3599-6    37. Bean, J.C. Genetics and random keys for sequencing    and optimization", ORSA J. Comput., 6, pp. 154{160    (1994).    38. Poli, R., Kennedy, J., and Blackwell, T. Particle    swarm optimization: an overview", Swarm. Intell., 1,    pp. 33{57 (2007).    39. Tadayon, B. and Salmasi, N. A two-criteria objective    function exible owshop scheduling problem with    machine eligibility constraint", Int. J. Adv. Manuf.    Tech., 64, pp. 1001{1015 (2013).    40. Kirkpatric, S., Gelatt, C.D., and Vecci, M.P. Optimization    by simulated annealing", Sci., 220, pp. 671{    680 (1983).    41. Asadi-Gangraj, E. and Nahavandi, N. A metaheuristic    approach for batch sizing and scheduling problem    in exible ow shop with unrelated parallel machines",    Int. J. Comp. App., 97, pp. 31{36 (2014).