A Hybrid Multi Objective Algorithm for Flexible Job Shop Scheduling

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.

Authors:

• Parviz Fattahi

Keywords:

• Flexible job shop
• Scheduling
• Hierarchical approach
• simulated annealing
• tabu search
• multi objective.

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