Two-Stage Chain-Reentrant Hybrid Flow-Shop With Deteriorating Jobs
DOI:
https://doi.org/10.2298/YJOR241215001NKeywords:
Scheduling, deteriorating jobs, bi-objective, NSGA2, AMOSA, TOPSISAbstract
In this paper, we study a two-stage chain-reentrant hybrid flow shop with deteriorating jobs as follows. Each job must initially be scheduled on a primary machine M1 (first stage) which is then scheduled on one of a set of m unrelated parallel machines (second stage) and returns back to M1 for its last operation. The jobs are subjected to a linear deterioration function of their starting times. The aim is to minimize both of the makespan and the total energy consumption. For the resolution of this problem, we have developed a mixed-integer linear programming model. We then implement and compare two metaheuristics: a nondominated sorting-based multiobjective genetic algorithm (NSGA2) and an archived multiobjective simulated annealing algorithm (AMOSA). The experimental study indicates that AMOSA generally outperforms NSGA2 on small instances (for all tested values of m and n ≤ 30), whereas NSGA2 yields better performance on larger instances (for all tested values of m and n ≥ 100), with respect to both quantity and quality measures. For small instances, the comparison with the exact method (i.e., the mathematical model) confirms that the reference fronts generated by both algorithms are close to the true Pareto front. Finally, we have proposed a TOPSIS-based method to select a representative solution from the Pareto set according to the decision-maker’s preferences.
References
A. Pechmann and I. Sch¨oler, “Optimizing energy costs by intelligent production scheduling,” in Glocalized Solutions for Sustainability in Manufacturing. Springer, Berlin, Heidelberg, 2011, p. 293–298. ISBN 978-3-642-19691-1
G. Kant and K. Sangwan, “Predictive modeling for power consumption in machining using artificial intelligence techniques,” Procedia CIRP, vol. 26, p. 403–407, 2015. doi: 10.1016/j.procir.2014.07.072
L. Shu, Y. He, and T. Hu, “An on-line approach for energy efficiency monitoring of machine tools,” Journal of Cleaner Production, vol. 27, p. 133–140, 2012. doi: 10.1016/j.jclepro.2012.01.013
S. Graves, H. Meal, D. Stefek, and A. Hamid, “Scheduling of re-entrant flow shops,” Journal of Operations Management, vol. 3, no. 4, p. 197–207, 1983. doi: 10.1016/02726963(83)90004-9
M. Y. Wang, S. P. Sethi, and S. L. van de Velde, “Minimizing makespan in a class of reentrant shops,” Operations Research, vol. 45, no. 5, p. 702–712, 1997. doi: 10.1287/opre.45.5.702
S.-W. Choi and Y.-D. Kim, “Minimizing total tardiness on a two machine reentrant flowshop,” European Journal of Operational Research, vol. 199, p. 375–384, 2009. doi: 10.1016/j.ejor.2008.11.037
F. Chu, C. Chu, and C. Desprez, “Series production in a basic reentrant shop to minimize makespan or total flow time,” Computers & Industrial Engineering, vol. 58, no. 2, p. 257–268, 2010. doi: 10.1016/j.cie.2009.02.017
H.-M. Cho, S.-J. Bae, J. Kim, and J. I.-J., “Bi-objective scheduling for reentrant hybrid flow shop using pareto genetic algorithm,” Computers & Industrial Engineering, vol. 61, no. 3, p. 529–541, 2011. doi: 10.1016/j.cie.2011.04.008
N. Yalaoui, L. Amodeo, F. Yalaoui, and H. Mahdi, “Efficient method to schedule reentrant f lowshop system,” Journal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology, vol. 26, no. 3, p. 1113–1121, 2014. doi: 10.5555/2596417.2596422
F. Belkaid, F. Yalaoui, and Z. Sari, “An efficient approach for the reentrant parallel machines scheduling problem under consumable resources constraints,” International Journal of Information Systems and Supply Chain Management, vol. 9, no. 3, p. 1–25, 2016. [Online]. Available: https://ideas.repec.org/a/igg/jisscm/v9y2016i3p1-25.html
K. Amrouche, M. Boudhar, M. Bendraouche, and F. Yalaoui, “Chain-reentrant shop with an exact time lag: new results,” International Journal of Production Research, vol. 55, p. 1–11, 2016. doi: 10.1080/00207543.2016.1205235
C. H. Pan and J. S. Chen, “Mixed binary integer programming formulations for the reentrant job shop scheduling problem,” Computers & Operations Research, vol. 32, no. 5, p. 1197–1212, 2005. doi: 10.1016/j.cor.2003.10.004
C. Jing, W. Huang, and G. Tang, “Minimizing total completion time for re-entrant flow shop scheduling problems,” Theoretical Computer Science, vol. 412, no. 48, p. 6712–6719, 2011. doi: 10.1016/j.tcs.2011.08.030
K.-C. Ying, S.-W. Lin, and S.-Y. Wan, “Bi-objective reentrant hybrid flowshop scheduling: an iterated pareto greedy algorithm,” International Journal of Production Research, vol. 52, no. 19, p. 5735–5747, 2014. doi: 10.1080/00207543.2014.910627
J. Shen, L. Wang, J. Deng, and X. Zheng, “A pareto-based discrete harmony search algorithm for bi-objective reentrant hybrid flowshop scheduling problem,” in Harmony Search Algorithm, 2016, vol. 382, p. 435–445. ISBN 978-3-662-47925-4
A. P. Rifai, H. T. Nguyen, and S. Z. M. Dawal, “Multiobjective adaptive large neighborhood search for distributed reentrant permutation flow shop scheduling,” Applied Soft Computing, vol. 40, p. 42–57, 2016. doi: 10.1016/j.asoc.2015.11.034
H. Tang, B. Fang, R. Liu, Y. Li, and S. Guo, “A hybrid teaching and learning-based optimization algorithm for distributed sand casting job-shop scheduling problem,” Applied Soft Computing, vol. 120, p. 108694, 2022. doi: 10.1016/j.asoc.2022.108694
F. Zhao, C. Zhuang, L. Wang, and C. Dong, “An iterative greedy algorithm with q-learning mechanism for the multiobjective distributed no-idle permutation flowshop scheduling,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 54, no. 5, p. 3207–3219, 2024. doi: 10.1109/TSMC.2024.3358383
H. Tang, W. Zhang, X. Li, and S. Wei, “A discrete group teaching optimization algorithm for solving many-objective sand casting whole process production scheduling problem,” Computers & Operations Research, vol. 164, p. 106563, 2024. doi: 10.1016/j.cor.2024.106563
F. Dugardin, F. Yalaoui, and L. Amodeo, “New multi-objective method to solve reentrant hybrid flow shop scheduling problem,” European Journal of Operational Research, vol. 203, no. 1, p. 22–31, 2010. doi: 10.1016/j.ejor.2009.06.031
K.Deb, A.Pratap, S. Agarwal, and T. Meyarivan, “A fast elitist non-dominated sorting genetic algorithm for multi objective optimization: Nsga-ii,” in Proceedings of the Parallel Problem Solving from Nature VI Conference, 2000, p. 849–858.
E. Zitzler, M. Laumanns, and L. Thiele, “Spea2: Improving the strength pareto evolutionary algorithm,” Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Tech. Rep. 103, 2001.
F. Dugardin, F. Yalaoui, and L. Amodeo, “Hybrid multi-objective methods to solve reentrant shops,” International Journal of Applied Logistics, vol. 3, no. 4, p. 15–32, 2012. [Online]. Available: https://ideas.repec.org/a/igg/jal000/v3y2012i4p15-32.html
M. Liu, X. Liu, F. Zheng, and F. Chu, “Bi-objective optimization of a reentrant flow shop scheduling with exact time lag considering energy cost,” in 7th International Conference on Industrial Engineering and Systems Management (IESM 2017), 2017.
Z. Pan, D. Lei, and L. Wang, “A knowledge-based two-population optimization algorithm for distributed energy-efficient parallel machines scheduling,” IEEE Transactions on Cybernetics, vol. 52, no. 6, p. 5051–5063, 2022. doi: 10.1109/TCYB.2020.3026571
F. Zhao, S. Di, and L. Wang, “A hyperheuristic with q-learning for the multiobjective energyefficient distributed blocking flow shop scheduling problem,” IEEE Transactions on Cybernetics, vol. 53, no. 5, p. 3337–3350, 2023. doi: 10.1109/TCYB.2022.3192112
M. Nedjai, K. Amrouche, and M. Boudhar, “The two-stage chain reentrant hybrid flow-shop problem with deteriorating jobs,” in Proceedings of the 50th Annual Conference of the Operations Research Society of South Africa, 2021, p. 85.
S. Browne and U. Yechiali, “Scheduling deteriorating jobs on a single processor,” Operations Research, vol. 38, no. 3, p. 495–498, 1990. doi: 10.1287/opre.38.3.495
B. Alidaee and N. K. Womer, “Scheduling with time-dependent processing times: Review and extensions,” Journal of the Operational Research Society, vol. 50, p. 711–720, 1999. doi: 10.1057/palgrave.jors.2600740
G. Mosheiov, “Scheduling jobs under simple linear deterioration,” Computers & Operations Research, vol. 21, no. 6, p. 653–659, 1994. doi: 10.1016/0305-0548(94)90080-9
M. Ji and T. Cheng, “Parallel-machine scheduling of simple linear deteriorating jobs,” Theoretical Computer Science, vol. 410, no. 38-40, p. 3761–3768, 2009. doi: 10.1016/j.tcs.2009.04.018
L. Wang, X. Huang, P. Ji, and E. Feng, “Unrelated parallel-machine scheduling with deteriorating maintenance activities to minimize the total completion time,” Optimization Letters, vol. 8, p. 129–134, 2014. doi: 10.1007/s11590-012-0472-x
M. Tigane, M. Dahane, and M. Boudhar, “Multiobjective approach for deteriorating jobs scheduling for a sustainable manufacturing system,” The International Journal of Advanced Manufacturing Technology, vol. 101, p. 1939–1957, 2019. doi: 10.1007/s00170-018-3043-1
R. Graham, E. Lawler, J. Lenstra, and A. Kan, “Optimization and approximation in deterministic sequencing and scheduling: a survey,” Annals of Discrete Mathematics, vol. 5, p. 287–326, 1979. doi: 10.1016/S0167-5060(08)70356-X
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: Nsga-ii,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, p. 182–197, 2002. doi: 10.1109/4235.996017
S. Bandyopadhyay, S. Saha, U. Maulik, and K. Deb, “A simulated annealing-based multiobjective optimization algorithm: Amosa,” IEEE Transactions on Evolutionary Computation, vol. 12, no. 3, p. 269–283, 2008. doi: 10.1109/TEVC.2007.900837
C. R. Raquel and P. C. Naval, “An effective use of crowding distance in multiobjective particle swarm optimization,” in GECCO’05: Proceedings of the 7th annual conference on Genetic and evolutionary computation, 2005, p. 257–264.
C. Hwang and A. Masud, Multiple objective decision making — methods and applications: A state-of-the-art survey, ser. Lectures Notes in Economics and Mathematical Systems. Springer Berlin Heidelberg, 1979. ISBN 978-3-540-09111-0
A. Jaszkiewicz, “Evaluation of multiple objective metaheuristics,” in Metaheuristics for Multiobjective Optimisation, ser. Lecture Notes in Economics and Mathematical Systems, X. Gandibleux, M. Sevaux, K. Sorensen, and V. T’kindt, Eds. Springer Berlin Heidelberg, 2004, vol. 535, pp. 65–89. ISBN 978-3-642-17144-4
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Yugoslav Journal of Operations Research
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
