×

A simulation-optimization model for solving flexible flow shop scheduling problems with rework and transportation. (English) Zbl 1524.90143

Summary: We propose an enhanced multi-objective harmony search (EMOHS) algorithm and a Gaussian mutation to solve the flexible flow shop scheduling problems with sequence-based setup time, transportation time, and probable rework. A constructive heuristic is used to generate the initial solution, and clustering is applied to improve the solution. The proposed algorithm uses response surface methodology to minimize both maximum completion time and mean tardiness, concurrently. We evaluate the efficacy of the proposed algorithm using computational experiments based on five measures of diversity metric, simultaneous rate of achievement for two objectives, mean ideal distance, quality metric, and coverage. The experimental results demonstrate the effectiveness of the proposed EMOHS compared with the existing algorithms for solving multi-objective problems.

MSC:

90B35 Deterministic scheduling theory in operations research
90-10 Mathematical modeling or simulation for problems pertaining to operations research and mathematical programming
90C29 Multi-objective and goal programming
90C59 Approximation methods and heuristics in mathematical programming

Software:

BPSS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adler, L.; Fraiman, N.; Kobacker, E.; Pinedo, M.; Plotnicoff, J. C.; Wu, T. P., BPSS: a scheduling support system for the packaging industry, Oper. Res., 41, 4, 641-648 (1993)
[2] de Almida, F. S., Optimization of laminated composite structures using harmony search Dalgorithm, Compos. Struct., 221, Article 110852 pp. (2019)
[3] Bargaoui, H.; Driss, O. B., Multi-agent model based on tabu search for the permutation flow shop scheduling problem, (Distributed Computing and Artificial Intelligence, 11th International Conference (2014), Springer: Springer Cham), 519-527
[4] Behnamian, J.; Fatemi Ghomi, S. M.T.; Zandieh, M., Development of a hybrid metaheuristic to minimise earliness and tardiness in a hybrid flowshop with sequence-dependent setup times, Int. J. Prod. Res., 48, 5, 1415-1438 (2010) · Zbl 1197.90195
[5] Behnamian, J.; Ghomi, S. F., Hybrid flowshop scheduling with machine and resource-dependent processing times, Appl. Math. Model., 35, 3, 1107-1123 (2011) · Zbl 1211.90077
[6] Behnamian, J.; Ghomi, S. F.; Zandieh, M., A multi-phase covering pareto-optimal front method to multi-objective scheduling in a realistic hybrid flowshop using a hybrid metaheuristic, Expert Syst. Appl., 36, 8, 11057-11069 (2009)
[7] Box, G. E.; Wilson, K. B., On the experimental attainment of optimum conditions, J. R. Stat. Soc. Ser. B Stat. Methodol., 13, 1, 1-45 (1951) · Zbl 0043.34402
[8] Chang, S. C.; Liao, D. Y., Scheduling flexible flow shops with no setup effects, IEEE Trans. Robot. Autom., 10, 2, 112-122 (1994)
[9] Chen, C. L., Iterated population-based VND algorithms for single-machine scheduling with sequence-dependent setup times, Soft Comput., 1-15 (2018)
[10] Chen, J.; Pan, Q. K.; Li, J. Q., Harmony search algorithm with dynamic control parameters, Appl. Math. Comput., 219, 2, 592-604 (2012) · Zbl 1290.90087
[11] Chen, J.; Pan, Q. K.; Wang, L.; Li, J. Q., A hybrid dynamic harmony search algorithm for identical parallel machines scheduling, Eng. Optim., 44, 2, 209-224 (2012)
[12] Cheng, C. Y.; Ying, K. C.; Li, S. F.; Hsieh, Y. C., Minimizing makespan in mixed no-wait flowshops with sequence-dependent setup times, Comput. Ind. Eng., 130, 338-347 (2019)
[13] D.W. Corne, N.R. Jerram, J.D. Knowles, M.J. Oates, PESA-II: Region-based selection in evolutionary multiobjective optimization, in: Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation, 2001, pp. 283-290.
[14] Da Silva, N. C.O.; Scarpin, C. T.; Pécora, J. E.; Ruiz, A., Online single machine scheduling with setup times depending on the jobs sequence, Comput. Ind. Eng., 129, 251-258 (2019)
[15] Dai, X.; Yuan, X.; Wu, L., A novel harmony search algorithm with Gaussian mutation for multi-objective optimization, Soft Comput., 1-19 (2015)
[16] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T. A.M. T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., 6, 2, 182-197 (2002)
[17] Dios, M.; Fernandez-Viagas, V.; Framinan, J. M., Efficient heuristics for the hybrid flow shop scheduling problem with missing operations, Comput. Ind. Eng., 115, 88-99 (2018)
[18] Dugardin, F.; Yalaoui, F.; Amodeo, L., New multi-objective method to solve reentrant hybrid flow shop scheduling problem, European J. Oper. Res., 203, 1, 22-31 (2010) · Zbl 1176.90205
[19] Ebrahimi, M.; Ghomi, S. F.; Karimi, B., Hybrid flow shop scheduling with sequence dependent family setup time and uncertain due dates, Appl. Math. Model., 38, 9, 2490-2504 (2014) · Zbl 1427.90169
[20] Fernandez-Viagas, V.; Molina-Pariente, J. M.; Framinan, J. M., New efficient constructive heuristics for the hybrid flowshop to minimise makespan: A computational evaluation of heuristics, Expert Syst. Appl., 114, 345-356 (2018)
[21] Fernandez-Viagas, V.; Perez-Gonzalez, P.; Framinan, J. M., Efficiency of the solution representations for the hybrid flow shop scheduling problem with makespan objective, Comput. Oper. Res., 109, 77-88 (2019) · Zbl 1458.90291
[22] Garcia, S.; Trinh, C. T., Comparison of multi-objective evolutionary algorithms to solve the modular cell design problem for novel biocatalysis, Processes, 7, 6, 361 (2019)
[23] Geem, Z. W.; Kim, J. H.; Loganathan, G. V., A new heuristic optimization algorithm: harmony search, Simulation, 76, 2, 60-68 (2001)
[24] Gholami-Zanjani, S. M.; Hakimifar, M.; Nazemi, N.; Jolai, F., Robust and fuzzy optimisation models for a flow shop scheduling problem with sequence dependent setup times: A real case study on a PCB assembly company, Int. J. Comput. Integr. Manuf., 30, 6, 552-563 (2017)
[25] Guinet, A. G.P.; Solomon, M. M., Scheduling hybrid flow shops to minimize maximum tardiness or maximum completion time, Int. J. Prod. Res., 34, 6, 1643-1654 (1996) · Zbl 0927.90033
[26] He, D.; He, C.; Jiang, L. G.; Zhu, H. W.; Hu, G. R., Chaotic characteristics of a one-dimensional iterative map with infinite collapses, IEEE Trans. Circuits Syst. I, 48, 7, 900-906 (2001) · Zbl 0993.37033
[27] Hwang, F. J.; Lin, B. M., Two-stage flexible flow shop scheduling subject to fixed job sequences, J. Oper. Res. Soc., 67, 3, 506-515 (2016)
[28] Jabbarizadeh, F.; Zandieh, M.; Talebi, D., Hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints, Comput. Ind. Eng., 57, 3, 949-957 (2009)
[29] Karimi, N.; Zandieh, M.; Karamooz, H. R., Bi-objective group scheduling in hybrid flexible flowshop: a multi-phase approach, Expert Syst. Appl., 37, 6, 4024-4032 (2010)
[30] Kennedy, J.; Eberhart, R., Particle swarm optimization, (Proceedings of ICNN’95-International Conference on Neural Networks, Vol. 4 (1995), IEEE), 1942-1948
[31] Khare, A.; Agrawal, S., Scheduling hybrid flowshop with sequence-dependent setup times and due windows to minimize total weighted earliness and tardiness, Comput. Ind. Eng., 135, 780-792 (2019)
[32] Kulluk, S.; Ozbakir, L.; Baykasoglu, A., Training neural networks with harmony search algorithms for classification problems, Eng. Appl. Artif. Intell., 25, 1, 11-19 (2012)
[33] Kundu, D.; Suresh, K.; Ghosh, S.; Das, S.; Panigrahi, B. K.; Das, S., Multi-objective optimization with artificial weed colonies, Inform. Sci., 181, 12, 2441-2454 (2011)
[34] Kurz, M. E.; Askin, R. G., Scheduling flexible flow lines with sequence-dependent setup times, European J. Oper. Res., 159, 1, 66-82 (2004) · Zbl 1067.90045
[35] Lee, K. S.; Geem, Z. W., A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice, Comput. Methods Appl. Mech. Engrg., 194, 36, 3902-3933 (2005) · Zbl 1096.74042
[36] Li, D.; Meng, X.; Liang, Q.; Zhao, J., A heuristic-search genetic algorithm for multi-stage hybrid flow shop scheduling with single processing machines and batch processing machines, J. Intell. Manuf., 26, 5, 873-890 (2015)
[37] Lin, S. W.; Gupta, J. N.; Ying, K. C.; Lee, Z. J., Using simulated annealing to schedule a flowshop manufacturing cell with sequence-dependent family setup times, Int. J. Prod. Res., 47, 12, 3205-3217 (2009) · Zbl 1198.90191
[38] Lu, C.; Gao, L.; Li, X.; Pan, Q.; Wang, Q., Energy-efficient permutation flow shop scheduling problem using a hybrid multi-objective backtracking search algorithm, J. Cleaner Prod., 144, 228-238 (2017)
[39] Luo, Q.; Yang, X.; Zhou, Y., Nature-inspired approach: An enhanced moth swarm algorithm for global optimization, Math. Comput. Simulation, 159, 57-92 (2019) · Zbl 07316639
[40] Mahdavi, M.; Fesanghary, M.; Damangir, E., An improved harmony search algorithm for solving optimization problems, Appl. Math. Comput., 188, 2, 1567-1579 (2007) · Zbl 1119.65053
[41] Marichelvam, M. K.; Geetha, M., Application of novel harmony search algorithm for solving hybrid flow shop scheduling problems to minimise makespan, Int. J. Ind. Syst. Eng., 23, 4, 467-481 (2016)
[42] Marichelvam, M. K.; Tosun, Ö.; Geetha, M., Hybrid monkey search algorithm for flow shop scheduling problem under makespan and total flow time, Appl. Soft Comput., 55, 82-92 (2017)
[43] Mazdeh, M. M.; Rostami, M., A branch-and-bound algorithm for two-machine flow-shop scheduling problems with batch delivery costs, Int. J. Syst. Sci. Oper. Logist., 1, 2, 94-104 (2014)
[44] Meena, R. K.; Jain, M.; Sanga, S. S.; Assad, A., Fuzzy modeling and harmony search optimization for machining system with general repair, standby support and vacation, Appl. Math. Comput., 361, 858-873 (2019) · Zbl 1428.90043
[45] Meng, T.; Pan, Q. K.; Li, J. Q.; Sang, H. Y., An improved migrating birds optimization for an integrated lot-streaming flow shop scheduling problem, Swarm Evol. Comput., 38, 64-78 (2018)
[46] Mirhosseini, H.; Tan, C. P.; Hamid, N. S.; Yusof, S.; Chern, B. H., Characterization of the influence of main emulsion components on the physicochemical properties of orange beverage emulsion using response surface methodology, Food Hydrocolloids, 23, 2, 271-280 (2009)
[47] Naderi, B.; Ruiz, R.; Zandieh, M., Algorithms for a realistic variant of flowshop scheduling, Comput. Oper. Res., 37, 2, 236-246 (2010) · Zbl 1175.90186
[48] Naderi, B.; Zandieh, M.; Roshanaei, V., Scheduling hybrid flowshops with sequence dependent setup times to minimize makespan and maximum tardiness, Int. J. Adv. Manuf. Technol., 41, 11-12, 1186-1198 (2009)
[49] Nouri, H. E.; Driss, O. B.; Ghédira, K., A classification schema for the job shop scheduling problem with transportation resources: state-of-the-art review, (Artificial Intelligence Perspectives in Intelligent Systems (2016), Springer: Springer Cham), 1-11
[50] Nouri, H. E.; Driss, O. B.; Ghédira, K., Hybrid metaheuristics for scheduling of machines and transport robots in job shop environment, Appl. Intell., 45, 3, 808-828 (2016)
[51] Nouri, H. E.; Driss, O. B.; Ghédira, K., Simultaneous scheduling of machines and transport robots in flexible job shop environment using hybrid metaheuristics based on clustered holonic multiagent model, Comput. Ind. Eng., 102, 488-501 (2016)
[52] Nouri, H. E.; Driss, O. B.; Ghédira, K., Controlling a single transport robot in a flexible job shop environment by hybrid metaheuristics, (Transactions on Computational Collective Intelligence XXVIII (2018), Springer: Springer Cham), 93-115
[53] Pinedo, M., Scheduling: Theory, Algorithms, and Systems (2002) · Zbl 1145.90394
[54] Rabiee, M.; Zandieh, M.; Ramezani, P., Bi-objective partial flexible job shop scheduling problem: NSGA-II, NRGA, MOGA and PAES approaches, Int. J. Prod. Res., 50, 24, 7327-7342 (2012)
[55] Rani, M.; Garg, H.; Sharma, S. P., Cost minimization of butter-oil processing plant using artificial bee colony technique, Math. Comput. Simulation, 97, 94-107 (2014) · Zbl 07312558
[56] Ribas, I.; Leisten, R.; Framiñan, J. M., Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective, Comput. Oper. Res., 37, 8, 1439-1454 (2010) · Zbl 1183.90189
[57] Ruiz, R.; Vázquez-Rodríguez, J. A., The hybrid flow shop scheduling problem, European J. Oper. Res., 205, 1, 1-18 (2010) · Zbl 1188.90110
[58] Saad, I.; Hammadi, S.; Benrejeb, M.; Borne, P., Choquet integral for criteria aggregation in the flexible job-shop scheduling problems, Math. Comput. Simulation, 76, 5-6, 447-462 (2008) · Zbl 1163.90510
[59] Sioud, A.; Gagné, C., Enhanced migrating birds optimization algorithm for the permutation flow shop problem with sequence dependent setup times, European J. Oper. Res., 264, 1, 66-73 (2018) · Zbl 1380.90129
[60] Sivasubramani, S.; Swarup, K. S., Multi-objective harmony search algorithm for optimal power flow problem, Int. J. Electr. Power Energy Syst., 33, 3, 745-752 (2011)
[61] Sokolov, B.; Ivanov, D.; Potryasaev, S. A., Flexible flow shop scheduling for continuous production, Int. J. Serv. Comput. Oriented Manuf., 2, 2, 189-203 (2016)
[62] Tran, T. H.; Ng, K. M., A hybrid water flow algorithm for multi-objective flexible flow shop scheduling problems, Eng. Optim., 45, 4, 483-502 (2013)
[63] Wang, H., Flexible flow shop scheduling: optimum, heuristics and artificial intelligence solutions, Expert Syst., 22, 2, 78-85 (2005)
[64] Yagmahan, B.; Yenisey, M. M., Ant colony optimization for multi-objective flow shop scheduling problem, Comput. Ind. Eng., 54, 3, 411-420 (2008)
[65] Yagmahan, B.; Yenisey, M. M., A multi-objective ant colony system algorithm for flow shop scheduling problem, Expert Syst. Appl., 37, 2, 1361-1368 (2010)
[66] Yu, A. J.; Seif, J., Minimizing tardiness and maintenance costs in flow shop scheduling by a lower-bound-based GA, Comput. Ind. Eng., 97, 26-40 (2016)
[67] Yuan, X.; Yuan, Y.; Zhang, Y., A hybrid chaotic genetic algorithm for short-term hydro system scheduling, Math. Comput. Simulation, 59, 4, 319-327 (2002) · Zbl 1030.90040
[68] M. Zandieh, N. Karimi, An adaptive multi-population genetic algorithm to solve the multi-objective group scheduling problem in hybrid flexible flowshop with sequence-dependent setup times, 22 (6) (2011) 979-989.
[69] Zhang, B.; Pan, Q. K.; Gao, L.; Li, X. Y.; Meng, L. L.; Peng, K. K., A multiobjective evolutionary algorithm based on decomposition for hybrid flowshop green scheduling problem, Comput. Ind. Eng. (2019)
[70] Zhu, Q.; Tang, X.; Li, Y.; Yeboah, M. O., An improved differential-based harmony search algorithm with linear dynamic domain, Knowl.-Based Syst. (2019)
[71] Zou, D.; Gao, L.; Wu, J.; Li, S., Novel global harmony search algorithm for unconstrained problems, Neuro Comput., 73, 16, 3308-3318 (2010)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.