A Hybrid Multi Objective Algorithm for Flexible Job Shop Scheduling

Authors: Parviz Fattahi

Abstract:

Scheduling for the flexible job shop is very important in both fields of production management and combinatorial optimization. However, it quit difficult to achieve an optimal solution to this problem with traditional optimization approaches owing to the high computational complexity. The combining of several optimization criteria induces additional complexity and new problems. In this paper, a Pareto approach to solve the multi objective flexible job shop scheduling problems is proposed. The objectives considered are to minimize the overall completion time (makespan) and total weighted tardiness (TWT). An effective simulated annealing algorithm based on the proposed approach is presented to solve multi objective flexible job shop scheduling problem. An external memory of non-dominated solutions is considered to save and update the non-dominated solutions during the solution process. Numerical examples are used to evaluate and study the performance of the proposed algorithm. The proposed algorithm can be applied easily in real factory conditions and for large size problems. It should thus be useful to both practitioners and researchers.

Keywords: Flexible job shop, Scheduling, Hierarchical approach, simulated annealing, tabu search, multi objective.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1332696

References:

[1] Garey MR, Johnson, DS, Sethi R (1976). The complexity of flow shop and job shop scheduling. Mathematics of Operations Research 1:117- 129.
[2] Xia W., Wu Z. (2005). An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering. 48: 409-425.
[3] Fattahi P., Saidi Mehrabad M., and Jolai F., (2007). Mathematical modeling and heuristic approaches to flexible job shop scheduling problems", Journal of Intelligent Manufacturing, Vol.18:331-342.
[4] Fattahi, P., Saidi Mehrabad, M., Arynezhad M.B. (2006). An algorithm for multi objective job shop scheduling problem. Journal of Industrial International, 2, 2.
[5] Hoogeveen, H., (2005). Multi criteria scheduling. European journal of operational research, 167, 592-623.
[6] Loukil, T., Teghem J. and Tuyttens D., (2005). Solving multi-objective production scheduling problems using meta heuristics. European journal of operational research. 161, 42-61.
[7] Gawiejnowicz, S., Kurc, W. and Pankowska, L., (2006). Pareto and scalar bicriterion optimization in scheduling deteriorating jobs. Computers & Operations Research, 33, 746-767.
[8] Varadharajan, T.K. and Rajendran, C., (2005). A multi-objective simulated-annealing algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs. European Journal of Operational Research, 167, 772-795.
[9] Cochran, J.K., Horng, S.M., and Fowler, J.W., (2003). A multipopulation genetic algorithm to solve multi-objective scheduling problems for parallel machines. Computers & Operations Research, 30, 1087-1102.
[10] Fred Choobineh, F., Mohebbi, E. and Khoo, H., (2005). A multiobjective tabu search for a single-machine scheduling problem with sequence-dependent setup times. European Journal of Operational Research.
[11] Xia, W. and Wu, Z., (2005). An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering. 48, 409-425.
[12] Drobouchevitch, I.G. and Strusevich, V.A., (2000). Heuristics for the two-stage job shop scheduling problem with a bottleneck machine. European Journal of Operational Research, 123, 229-240.
[13] Wenqia, H., and Aihuaa, Y., (2004). An improved shifting bottleneck procedure for the job shop scheduling problem. Computers & Operations Research, 31, 2093-2110.
[14] Mosheiov, G., and Oron, D., (2005). A note on flow-shop and job-shop batch scheduling with identical processing-time jobs. European Journal of Operational Research, 161, 285-291.
[15] Mattfeld, D.C. and Bierwirth, C., (2004). An efficient genetic algorithm for job shop scheduling with tardiness objectives. European Journal of Operational Research, 155, 616-630.
[16] Asano, M., and Ohta, H., (2002). A heuristic for job shop scheduling to minimize total weighted tardiness. Computer and industrial engineering, 42, 137-147.
[17] Golenko Ginzburg, D., and Gonik, A., (2002). Optimal job-shop scheduling with random operations and cost objectives. International Journal of Production Economics, 76, 147-157.
[18] Thiagarajan, S., and Rajendran, C., (2005). Scheduling in dynamic assembly job-shops to minimize the sum of weighted earliness, weighted tardiness and weighted flow time of jobs. Computers & Industrial Engineering, 49, 463-503.
[19] Bruker, P., & Schlie, R. (1990). Job shop scheduling with multi-purpose machines. Computing, 45, 369-375.
[20] Ehrgott, M., and Gandibleux, X., (2000). A survey and annotated bibliography of multi objective combinatorial optimization. OR Spektrum, 22, 425-460.
[21] Ulungu, E.L., Teghem, J., Fortemps, Ph., and Tuyttens, D., (1999). MOSA method: A tool for solving MOCO problems. Journal of Multi- Criteria Decision Analysis, 8, 221-236.
[22] Miettinen, K., (1999). Nonlinear multi objective optimization. Dordrecht: Kluwer Academic Publishers.
[23] Kacem, I., Hammadi, S. and Borne, P., (2002). Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic. Mathematics and Computers in Simulation, 60, 245-276.
[24] Ghoseiri, K., Szidarovszky, F., Asgharpour M.J., (2004). A multiobjective train scheduling model and solution. Transportation Research Part B 38: 927-952