A Mathematical Model for Lot-streaming Hybrid Flow Shop Scheduling Problem by Considering Learning Effect and Buffer Capacity

Document Type : Article


Department of Industrial Engineering, Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran


Lot streaming, is an effective technique to increase production efficiency in a productive system by splitting a job into several smaller parts to overlap operations between successive machines in a multi-stage production system. In this paper, a hybrid flow shop scheduling problem with lot streaming, learning effect and buffer's limitation is considered. A bi-objective mathematical model is presented for minimizing the total tardiness and the makespan. To validate the proposed model, the bi-objective model converted to single objective model by weighting method and an example is solved using GAMS software. Since the problem is NP-hard, NSGA-II and NRGA algorithms are used to solve the large scale of the problems and the first available machine (FAM) rule is used to assign the jobs to the machines from the first stage onwards in solution representation. Also, Taguchi method is used to tune the algorithms parameters. For evaluating the performance of the algorithms, the results obtained from GAMS software compared with outputs of the GA algorithms. Also, 30 instance problems are randomly generated and six indicators are used to compare the algorithms together. After performing the experiments and comparing the algorithms with each other, the results show NRGA algorithm performs better than NSGAII.


  • References

    • Jin, Z. H., Ohno, K., Ito, T., et al. “Scheduling hybrid flowshops in printed circuit board assembly lines”. Production and Operations Management, 11 (2) 216–230 (2002).
    • Grabowski, J., Pempera, J. “Sequencing of jobs in some production system”. European Journal of Operational Research, 125, 535–550 (2000).
    • Sherali, H. D., Sarin, S. C., Kodialam, M. S. “Models and algorithms for a two-stage production process”. Production Planning & Control, 1 (1) 27–39 (1990).
    • Guinet, A. G. P. “Textile production systems: a succession of non-identical parallel processor shops”. Journal of the Operational Research Society, 42 (8) 655–671 (1991).
    • Guinet, A., Solomon, M. “Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time”. International Journal of Production Research, 34, 1643–1654 (1996).
    • Aghezzaf, E. H., Landeghem, H. V. “An integrated model for inventory and production planning in a two-stage hybrid production system”. International Journal of Production Research, 40, 4323-4333 (2002).
    • Dror, M., Mullaserif, P.A. “Three stage generalized flowshop: scheduling civil engineering projects”. Journal of Global Optimization, 9, 321–344 (1996).
    • Chen, L., Bostel, N., Dejax, P., et al. “A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal”. European Journal of Operational Research, 181, 40–58 (2007).
    • Allahverdi, A., Al-Anzi, F. S. “Scheduling multi-stage parallel-processor services to minimize average response time”. Journal of the Operational Research Society, 57, 101–110 (2006).
    • Biskup, D. “Single-machine scheduling with learning considerations”. European Journal of Operational Research, 115, 173-178 (1999).
    • Gupta, J.N. “Two-stage hybrid flowshop scheduling problem”. Journal of the Operational Research Society, 39, 359–364 (1988).
    • Wang, S., Kurz, M., Mason, S. J., et al. “Two-stage hybrid flow shop batching and lot streaming with variable sub-lots and sequence-dependent setups”. International Journal of Production Research, https://doi.org/10.1080/00207543.2019.1571251, (2019).
    • Li, J. Q., Tao, B. X., Han, Y. Y., et al. “Efficient multi-objective algorithm for the lot-streaming hybrid flowshop with variable sub-lots”. Swarm Evolutionary Computation, 52, (2020).
    • Cheng, M., Sarin, S. C. “Two-stage, Multiple-lot, Lot Streaming Problem for a 1+2 Hybrid Flow Shop”. International Federation of Automatic Control, 448-453 (2013).
    • Nejati, M., Mahdavi, I., Hassanzadeh, R., et al. “Lot streaming in a two-stage assembly hybrid flow shop scheduling problem with a work shift constraint”. Journal of Industrial and Production Engineering, http://dx.doi.org/10.1080/21681015.2015.1126653, (2016).
    • Zhang, B., Pan, Q. K., Gao, L., et al. “An Effective Modified Migrating Birds Optimization for Hybrid Flowshop Scheduling Problem with Lot Streaming”. Applied Soft Computing Journal, http://dx.doi.org/10.1016/j.asoc.2016.12.021, (2016).
    • Lalitha, J., Mohan, N., Pillai, V. “Lot streaming in [N-1](1)+N(m) hybrid flow shop”. Journal of Manufacturing System, 44, 12–21 (2017).
    • Gong, D., Han, Y., Sun, J. “A Novel Hybrid Multi-Objective Artificial Bee Colony Algorithm for Blocking Lot-Streaming Flow Shop Scheduling Problems”. Knowledge-Based Systems, 1-37 (2018).
    • Chen, T. L., Cheng, C. Y., Chou, Y. H. “Multi-objective genetic algorithm for energy-efficient hybrid flow shop scheduling with lot streaming”. Annals of Operations Research, https://doi.org/10.1007/s10479-018-2969-x, (2018).
    • Qin, W., Zhuang, Z., Liu, Y., et al. “A two-stage ant colony algorithm for hybrid flow shop scheduling with lot sizing and calendar constraints in printed circuit board assembly”. Computers &Industrial Engineering, doi: https://doi.org/10.1016/j.cie.2019.106115, (2019).
    • Cheng, T. C. E., Wang, G. “Single machine scheduling with learning effect considerations”. Annals of Operations Research, 98, (1-4), 273-290 (2000).
    • Eren, T., Güner, E. “A bicriteria parallel machine scheduling with a learning effect”. International Journal of Advanced Manufacturing Technology, 40, 1202-1205 (2009).
    • Cheng, T. C. E., Kuo, W.H., Yang, D. L. “Scheduling with a position-weighted learning effect”. Optimization Letters, 293-306 (2014).
    • Gao, F., Liu, M., Wang, J., Lu, Y. “No-wait two-machine permutation flow shop scheduling problem with learning effect, common due date and controllable job processing times”. International Journal of Production Research, 2361-2369.https://doi.org/10.1080/00207543.2017.1371353, (2017).
    • Sun, X., Geng, X., Liu, F. “Flow shop scheduling with general position weighted learning effects to minimize total weighted completion time”. Journal of the Operational Research Society. 2674-2689, https://doi.org/10.1080/01605682.2020.1806746, (2020).
    • Xin, X., Jiang, Q., Li, C., et al. “Permutation flow shop energy-efficient scheduling with a position-based learning effect”. International Journal of Production Research, https://doi.org/10.1080/00207543.2021.2008041, (2021).
    • Bai, D., Bai, X., Yang, J., et al. “Minimization of maximum lateness in a flow shop learning effect scheduling with release dates”. Computers & Industrial Engineering, 158, August 2021, 107309, (2021).
    • Pargar, F., Zandieh, M. “Bi-criteria SDST hybrid flow shop scheduling with learning effect of setup times: water flow-like algorithm approach”. International Journal of Production Research, 2609-2623, http://dx.doi.org/10.1080/00207543.2010.546380, (2012).
    • Mousavi, S. M., Mahdavi, I., Rezaeian, J., et al. “An efficient bi-objective algorithm to solve re-entrant hybrid flow shop scheduling with learning effect and setup times”. Operational Research, 16, 1-36 (2016).
    • Lei, D., Gao, L., Zheng, Y. “A Novel Teaching-Learning-Based Optimization Algorithm for Energy-Efficient Scheduling in Hybrid Flow Shop”. IEEE Transactions on Engineering Management, 99, 1-11 (2017).
    • Shahvari, O., Logendran, R. “A comparison of two stage-based hybrid algorithms for a batch scheduling problem in hybrid flow shop with learning effect”. International Journal of Production Economics, 195, 227–248 (2018).
    • Fu, Q., Sivakumar, A. I., Li, K. “Optimisation of flow-shop scheduling with batch processor and limited buffer”. International Journal of Production Research, 50, 8, 2267–2285 (2012).
    • Zhao, F., Tanga, J., Wang, J., et al. “An improved particle swarm optimisation with a linearly decreasing disturbance term for flowshop scheduling with limited buffers”. International Journal of Computer Integrated Manufacturing, 27, 5, 488–499 (2014).
    • Zhang, C., Shi, Z., Huang, Z., et al. “Flow shop scheduling with a batch processor and limited buffer”. International Journal of Production Research, DOI:1080/00207543.2016.1268730. (2016).
    • Gu, H., Kononov, A., Memar, J., et al. “Efficient Lagrangian heuristics for the two-stage flow shop with job dependent buffer requirements”. Journal of Discrete Algorithms, doi.org/10.1016/j.jda.2018.11.011. (2018).
    • Zohali, H., Naderi, B., Mohammadi, M. “The economic lot scheduling problem in limited-buffer flexible flow shops: Mathematical models and a discrete fruit fly algorithm”. Applied Soft Computing Journal, https://doi.org/10.1016/j.asoc.2019.03.054, (2019).
    • Yaurima-Basaldua, V. H., Burtseva, L., Tchernykh, A. “Hybrid flowshop with unrelated machines, sequence-dependent setup time availability constraints and limited buffers”. Computers & Industrial Engineering, 56, 1452–1463 (2009).
    • Hakimzadeh, A. S., Zandieh, M. “Bi-objective hybrid flow shop scheduling with sequence-dependent setup times and limited”. International Journal of Advanced Manufacturing Technology, 58, 309–325 (2012).
    • Safari, G., Hafezalkotob, A., Khalilzadeh, M. “Hybrid genetic algorithm. A novel mathematical model for a hybrid flow shop scheduling problem under buffer and resource limitations-A case study”. Journal of Industrial and Systems Engineering. 10, 58- 77 (2018).
    • Yaurima-Basaldua, V. H., Tchernykh, A., Villalobos, F. V., et al. “Hybrid Flow Shop with Unrelated Machines, Setup Time, and Work in Progress Buffers for Bi-Objective Optimization of Tortilla Manufacturing”. Algorithm, 11, 68, 1-23 (2018).
    • Jiang, S. L., Zhang, L. “Energy-Oriented scheduling for hybrid flow shop with limited buffers through efficient multi-objective optimization”. IEEE, 7, 34477-34487 (2019).
    • Lin, C. C., Liu, W. Y., Chen, Y. H. “Considering stockers in reentrant hybrid flow shop scheduling with limited buffer capacity”. Computers and Industrial Engineering, 139, 106-154 (2020).
    • Al Jadaan, O., Rao, C. R., Rajamani, L. “Parametric study to enhance genetic algorithm performance using ranked based roulette wheel selection method”. Proceedings of the Genetic and Evolutionary Computation Conference, 274-278 (2008).
    • Deb, K. “Multi-objective Evolutionary Optimization: Past, Present and Future”. In Proceeding of the Fourth International Conference on Adaptive Computing in Design and Manufacture, edited by I. C. Parmee, 225–236 (2000).
    • Taguchi, G. “Introduction to quality engineering (White Plains, NY: Asian Productivity Organization, Unipub/Kraus International Publications), (1986).