Flexible Job Shop Scheduling Multi-Objective Optimization Based on Improved Strength Pareto Evolutionary Algorithm

Abstract:

Scheduling for the flexible job shop is very important in fields of production management. To solve the multi–objective optimization in flexible job shop scheduling problem (FJSP), the FJSP multi-objective optimization model is constructed. The cost, quality and time are taken as the optimization objectives. An improved strength Pareto evolutionary algorithm (SPEA2+) is put forward to optimize the multi-objective optimization model parallelly. The algorithm uses a new model of a Multi-objective genetic algorithm that includes more effective crossover and could obtain diverse solutions in the objective and variable spaces to archive the Pareto optimal sets for FJSP multi-objective optimization. Then an approach based on fuzzy set theory was developed to extract one of the Pareto-optimal solutions as the best compromise one. The optimization results were compared with those obtained by NSGA-II and POS. At last, an instance of flexible job shop scheduling problem in automotive industry is given to illustrate that the proposed method can solve the multi-objective FJSP effectively.

• Periodical: Advanced Materials Research (Volume 186)
• Pages: 546-551
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.186.546
• Online since: January 2011
• Authors: Wei Wei, Yi Xiong Feng, Jian Rong Tan, Ichiro Hagiwara
• Keywords: Flexible Job-Shop Scheduling, Genetic Algorithm (GA), Multi-Objective Optimization (MOP), SPEA2+

References

[1] Chambers, J.B.: Classical and flexible job shop scheduling by tabu search. PhD thesis, University of Texas at Austin, Austin, U.S.A. (1996).

[2] Yang, J.B.: GA-based discrete dynamic programming approach for scheduling in FMS environments. IEEE Trans. Systems, Man, and Cybernetics Part B, 31(5): 824-835 (2001).

DOI: 10.1109/3477.956045

[3] Brandimarte, P.: Routing and scheduling in a flexible job shop by taboo search. Annals of Operations Research, 22(2): 157-183 (1993).

DOI: 10.1007/bf02023073

[4] Mati, Y., Rezg, N., Xie, X.L.: An integrated greedy heuristic for a flexible job shop scheduling problem. The Proceedings of IEEE International Conference on Systems, Man and Cybernetics, Piscataway, NJ, USA: IEEE, 2534-2539 (2001).

DOI: 10.1109/icsmc.2001.972939

[5] Hapke, M.: Pareto simulated annealing for fuzzy multi-objective combinatorial optimization. Journal of Heuristics, 6(3): 329-345 (2000).

[6] Rigao, C.: Tardiness minimization in a flexible job shop: a tabu search approach. Journal of Intelligent Manufacturing, 15(1): 103-115 (2004).

DOI: 10.1023/b:jims.0000010078.30713.e9

[7] Kacem, I., hammadi, S., Borne, P.: Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problems. IEEE Trans. Systems, Man, and Cybernetics Part C, 32(1): 1-13 (2002).

DOI: 10.1109/tsmcc.2002.1009117

[8] Zhang, C., Mo, R., Shi, S.: Research on manufacturing grid resource scheduling based on genetic algorithm. China Mechanical Engineering, 17(18): 1916-1920 (2006).

[9] Garey, M.R., Johnson, D.S., Ravi, S.I.: The complexity of flow shop and job shop scheduling. Mathematics of Operations Research, 1(2): 117-129 (1976).

[10] Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist Multi-objective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2): 182-197 (2002).

DOI: 10.1109/4235.996017

[11] Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: Improving the performance of the strength pareto evolutionary algorithm. Technical Report 103, Computer Engineering and Communication Networks Lab (TLK), Swiss Federal Institute of Technology (ETH) Zurich (2001).

[12] Rao, S.S.: Optimization theory and application. New Delhi: Wiley Eastern Limited, (1991).

[13] Abido, M.A.: Multi-objective evolutionary algorithms for electric power dispatch problem. IEEE Transactions on Evolutionary Computation, 10(3): 315-329 (2006).

DOI: 10.1109/tevc.2005.857073

[14] Tsai, H.C., Hsiao, S.W.: Evaluation of alternatives for product customization using fuzzy logic. Information Sciences, 158(1): 233-262 (2004).

DOI: 10.1016/j.ins.2003.08.001