×

Coevolutionary makespan optimisation through different ranking methods for the fuzzy flexible job shop. (English) Zbl 1373.90061

Summary: In this paper, we tackle a variant of the flexible job shop scheduling problem with uncertain task durations modelled as fuzzy numbers, the fuzzy flexible job shop scheduling problem or FfJSP in short. To minimise the schedule’s fuzzy makespan, we consider different ranking methods for fuzzy numbers. We then propose a cooperative coevolutionary algorithm with two different populations evolving the two components of a solution: machine assignment and task relative order. Additionally, we incorporate a specific local search method for each population. The resulting hybrid algorithm is then evaluated on existing benchmark instances, comparing favourably with the state-of-the-art methods. The experimental results also serve to analyse the influence in the robustness of the resulting schedules of the chosen ranking method.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Pinedo, M. L., Scheduling. Theory, Algorithms, and Systems (2008), Springer · Zbl 1155.90008
[2] Herrera, F.; Verdegay, J. L., Fuzzy sets and operations research: perspectives, Fuzzy Sets Syst., 90, 207-218 (1997) · Zbl 0921.90147
[3] Dubois, D.; Fargier, H.; Fortemps, P., Fuzzy scheduling: modelling flexible constraints vs. coping with incomplete knowledge, Eur. J. Oper. Res., 147, 231-252 (2003) · Zbl 1037.90028
[4] Fortemps, P., Editorial. Fuzzy sets in scheduling and planning, Eur. J. Oper. Res., 147, 229-230 (2003)
[5] Wong, B. K.; Lai, V. S., A survey of the application of fuzzy set theory in production and operations management: 1998-2009, Int. J. Prod. Econ., 129, 157-168 (2011)
[6] Wang, J., A fuzzy robust scheduling approach for product development projects, Eur. J. Oper. Res., 152, 180-194 (2004) · Zbl 1044.90038
[7] Kasperski, A.; Kule, M., Choosing robust solutions in discrete optimization problems with fuzzy costs, Fuzzy Sets Syst., 160, 667-682 (2009) · Zbl 1173.90596
[8] Palacios, J. J.; González-Rodríguez, I.; Vela, C. R.; Puente, J., Robust swarm optimisation for fuzzy open shop scheduling, Nat. Comput., 13, 2, 145-156 (2014)
[9] Bortolan, G.; Degani, R., A review of some methods for ranking fuzzy subsets, (Dubois, D.; Prade, H.; Yager, R., Readings in Fuzzy Sets for Intelligence Systems (1993), Morgan Kaufmann: Morgan Kaufmann Amsterdam (NL)), 149-158
[10] Brunelli, M.; Mezei, J., How different are ranking methods for fuzzy numbers? A numerical study, Int. J. Approx. Reason., 54, 627-639 (2013) · Zbl 1316.91012
[11] Talbi, E.-G., Metaheuristics. From Design to Implementation (2009), Wiley · Zbl 1190.90293
[12] Lei, D., A genetic algorithm for flexible job shop scheduling with fuzzy processing time, Int. J. Prod. Res., 48, 10, 2995-3013 (2010) · Zbl 1197.90216
[13] Wang, L.; Zhou, G.; Xu, Y.; Min, L., A hybrid artificial bee colony algorithm for the fuzzy flexible job-shop scheduling problem, Int. J. Prod. Res., 51, 12, 3593-3608 (2013)
[14] Wang, S.; Wang, L.; Xu, Y.; Min, L., An effective estimation of distribution algorithm for the flexible job-shop scheduling problem with fuzzy processing time, Int. J. Prod. Res., 51, 12, 3779-3793 (2013)
[15] Lei, D.; Guo, X., Swarm-based neighbourhood search algorithm for fuzzy flexible job shop scheduling, Int. J. Prod. Res., 50, 6, 1639-1649 (2012)
[16] Lei, D., Co-evolutionary genetic algorithm for fuzzy flexible job shop scheduling, Appl. Soft Comput., 12, 2237-2245 (2012)
[17] Potter, M. A.; De Jong, K. A., Cooperative coevolution: an architecture for evolving coadapted subcomponents, Evol. Comput., 8, 1, 1-29 (2000)
[18] Popovici, E.; Bucci, A.; Wiegand, R. P.; de Jong, E. D., Coevolutionary principles, (Handbook of Natural Computing (2012), Springer), 987-1033 · Zbl 1248.68001
[19] Antonio, L.; Coello Coello, C., Use of cooperative coevolution for solving large scale multiobjective optimization problems, (2013 IEEE Congress on Evolutionary Computation (CEC) (2013)), 2758-2765
[20] Derrac, J.; García, S.; Herrera, F., IFS-CoCo: instance and feature selection based on cooperative coevolution with nearest neighbor rule, Pattern Recognit., 43, 2015-2082 (2010) · Zbl 1191.68563
[21] Goh, C.-K.; Tan, K. C., A competitive-cooperative coevolutionary paradigm for dynamic multiobjective optimization, IEEE Trans. Evol. Comput., 13, 1, 103-127 (2009)
[22] Kim, Y. K.; Park, K.; Ko, J., A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling, Comput. Oper. Res., 30, 8, 1151-1171 (2003) · Zbl 1049.90026
[23] Hong, Z.; Jian, W., A cooperative coevolutionary algorithm with application to job shop scheduling problem, (IEEE International Conference on Service Operations and Logistics, and Informatics 2006. IEEE International Conference on Service Operations and Logistics, and Informatics 2006, SOLI’06 (2006), IEEE), 746-751
[24] Gu, J.; Gu, M.; Cao, C.; Gu, X., A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem, Comput. Oper. Res., 37, 5, 927-937 (2010) · Zbl 1177.90199
[25] Nguyen, S.; Zhang, M.; Johnston, M.; Tan, K. C., Automatic design of scheduling policies for dynamic multi-objective job shop scheduling via cooperative coevolution genetic programming, IEEE Trans. Evol. Comput., 18, 2, 193-208 (2014)
[26] Xiang, Z.; Zhenqiang, B.; Guijun, W.; Quanke, P., Optimization of fuzzy job-shop scheduling with multi-process routes and its co-evolutionary algorithm, (2011 International Conference on Intelligent Computation Technology and Automation (ICICTA), vol. 1 (2011), IEEE), 866-870
[27] Kuroda, M.; Wang, Z., Fuzzy job shop scheduling, Int. J. Prod. Econ., 44, 45-51 (1996)
[28] Fortemps, P., Jobshop scheduling with imprecise durations: a fuzzy approach, IEEE Trans. Fuzzy Syst., 7, 557-569 (1997)
[29] Sakawa, M.; Kubota, R., Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms, Eur. J. Oper. Res., 120, 393-407 (2000) · Zbl 0954.90071
[30] González Rodríguez, I.; Puente, J.; Vela, C. R.; Varela, R., Semantics of schedules for the fuzzy job shop problem, IEEE Trans. Syst. Man Cybern., Part A, Syst. Hum., 38, 3, 655-666 (2008)
[31] Lei, D., Pareto archive particle swarm optimization for multi-objective fuzzy job shop scheduling problems, Int. J. Adv. Manuf. Technol., 37, 157-165 (2008)
[32] Niu, Q.; Jiao, B.; Gu, X., Particle swarm optimization combined with genetic operators for job shop scheduling problem with fuzzy processing time, Appl. Comput. Math., 205, 148-158 (2008) · Zbl 1175.90187
[33] Van Leekwijck, W.; Kerre, E. E., Defuzzification: criteria and classification, Fuzzy Sets Syst., 108, 159-178 (1999) · Zbl 0962.93057
[34] Wang, W.; Wang, Z., Total orderings defined on the set of all fuzzy numbers, Fuzzy Sets Syst., 243, 131-141 (2014) · Zbl 1315.03104
[35] Campos Ibañez, L. M.; González Muñoz, A., A subjective approach for ranking fuzzy numbers, Fuzzy Sets Syst., 29, 145-153 (1989) · Zbl 0672.90001
[36] Liou, T. L.; Wang, M. J., Ranking fuzzy numbers with integral value, Fuzzy Sets Syst., 50, 247-255 (1992) · Zbl 1229.03043
[37] Yager, R. R., A procedure for ordering fuzzy subsets of the unit interval, Inf. Sci., 24, 143-161 (1981) · Zbl 0459.04004
[38] Heilpern, S., The expected value of a fuzzy number, Fuzzy Sets Syst., 47, 81-86 (1992) · Zbl 0755.60004
[39] Fortemps, P.; Roubens, M., Ranking and defuzzification methods based on area compensation, Fuzzy Sets Syst., 82, 319-330 (1996) · Zbl 0886.94025
[40] Chanas, S.; Nowakowski, M., Single value simulation of fuzzy variable, Fuzzy Sets Syst., 25, 43-57 (1988) · Zbl 0633.65144
[41] Liu, B.; Liu, Y. K., Expected value of fuzzy variable and fuzzy expected value models, IEEE Trans. Fuzzy Syst., 10, 445-450 (2002)
[42] Asady, B.; Zendehman, A., Ranking fuzzy numbers by distance minimization, Appl. Math. Model., 31, 2589-2598 (2007) · Zbl 1211.03069
[43] Dubois, D.; Prade, H., The mean value of a fuzzy number, Fuzzy Sets Syst., 24, 279-300 (1987) · Zbl 0634.94026
[44] Dubois, D., Possibility theory an statistical reasoning, Comput. Stat. Data Anal., 51, 47-69 (2006) · Zbl 1157.62309
[45] Adamo, J. M., Fuzzy decision trees, Fuzzy Sets Syst., 4, 3, 207-219 (1980) · Zbl 0444.90004
[46] Wang, X.; Kerre, E. E., Reasonable properties for the ordering of fuzzy quantities (I), Fuzzy Sets Syst., 118, 375-385 (2001) · Zbl 0971.03054
[47] Wang, X.; Kerre, E. E., Reasonable properties for the ordering of fuzzy quantities (II), Fuzzy Sets Syst., 118, 387-405 (2001) · Zbl 0971.03055
[48] Couso, I.; Destercke, S., Ranking of fuzzy numbers seen through the imprecise probabilistic lense, (De Baets, B.; Fodor, J.; Montes, S., Proceedings of EUROFUSE 2013 (2013), University of Oviedo), 73-82
[49] Dubois, D., The role of fuzzy sets in decision sciences: old techniques and new directions, Fuzzy Sets Syst., 184, 3-28 (2011) · Zbl 1242.91043
[50] Nakamura, K., Preference relation on a set of fuzzy utilities as a basis for decision making, Fuzzy Sets Syst., 20, 2, 147-162 (1986) · Zbl 0618.90001
[51] Carlsson, C.; Fullér, R., On possibilistic mean value and variance of fuzzy variables, Fuzzy Sets Syst., 122, 2, 315-326 (2001) · Zbl 1016.94047
[52] Chen, S.-H., Ranking fuzzy numbers with maximizing set and minimizing set, Fuzzy Sets Syst., 17, 2, 113-129 (1985) · Zbl 0618.90047
[53] Bodjanova, S., Median value and median interval of a fuzzy number, Inf. Sci., 172, 1, 73-89 (2005) · Zbl 1074.03018
[54] Dubois, D.; Prade, H., Unfair coins and necessity measures: towards a possibilistic interpretations of histograms, Fuzzy Sets Syst., 10, 15-20 (1983) · Zbl 0515.60005
[55] Herroelen, W.; Leus, R., Project scheduling under uncertainty: survey and research potentials, Eur. J. Oper. Res., 165, 289-306 (2005) · Zbl 1066.90050
[56] Kalaï, R.; Lamboray, C.; Vanderpooten, D., Lexicographic \(α\)-robustness: an alternative to min-max criteria, Eur. J. Oper. Res., 220, 722-728 (2012) · Zbl 1253.91052
[57] Bidot, J.; Vidal, T.; Laboire, P., A theoretic and practical framework for scheduling in stochastic environment, J. Sched., 12, 315-344 (2009) · Zbl 1185.90109
[58] Dubois, D.; Prade, H.; Sandri, S., On possibility/probability transformations, (Fuzzy Logic. Fuzzy Logic, Theory and Decision Library, vol. 12 (1993), Kluwer Academic), 103-112
[59] Aissi, H.; Bazgan, C.; Vanderpooten, D., Min-max and min-max regret versions of combinatorial optimization problems: a survey, Eur. J. Oper. Res., 197, 427-438 (2009) · Zbl 1159.90472
[60] Danoy, G.; Dorronsoro, B.; Bouvry, P., Multi-objective cooperative coevolutionary algorithms for robust scheduling, (Proc. of EVOLVE-A Bridge Between Probability, Set Oriented Numerics and Evolutionary Computation (2011))
[61] Ren, J.; Harman, M.; Di Penta, M., Cooperative co-evolutionary optimization of software project staff assignments and job scheduling, (Search Based Software Engineering. Search Based Software Engineering, Lecture Notes in Computer Science, vol. 6956 (2011), Springer), 127-141
[62] Su, S.; Yu, H.; Wu, Z.; Tian, W., A distributed coevolutionary algorithm for multiobjective hybrid flowshop scheduling problems, Int. J. Adv. Manuf. Technol., 70, 1-4, 477-494 (2014)
[63] Bierwirth, C., A generalized permutation approach to jobshop scheduling with genetic algorithms, OR Spektrum, 17, 87-92 (1995) · Zbl 0843.90056
[64] Ono, I.; Yamamura, M.; Kobayashi, S., A genetic algorithm for job-shop scheduling problems using job-based order crossover, (Proceedings of IEEE International Conference on Evolutionary Computation, 1996 (1996), IEEE), 547-552
[65] González Rodríguez, I.; Vela, C. R.; Puente, J.; Varela, R., A new local search for the job shop problem with uncertain durations, (Proceedings of the Eighteenth International Conference on Automated Planning and Scheduling (ICAPS-2008) (2008), AAAI Press: AAAI Press Sidney), 124-131
[66] Mastrolilli, M.; Gambardella, L., Effective neighborhood functions for the flexible job shop problem, J. Sched., 3, 1, 3-20 (2000) · Zbl 1028.90018
[67] González, M.; Vela, C. R.; Varela, R., An efficient memetic algorithm for the flexible job shop with setup times, (Proceedings of the 23th International Conference on Automated Planning and Scheduling (ICAPS-2013) (2013)), 91-99
[68] González Rodríguez, I.; Vela, C. R.; Hernández-Arauzo, A.; Puente, J., Improved local search for job shop scheduling with uncertain durations, (Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling (ICAPS-2009) (2009), AAAI Press: AAAI Press Thesaloniki), 154-161
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.