Scheduling a Flexible Flow Shops Problem using DEA

This paper considers a scheduling problem in flexible flow shops environment with the aim of minimizing two important criteria including makespan and cumulative tardiness of jobs. Since the proposed problem is known as an Np-hard problem in literature, we have to develop a meta-heuristic to solve it. We considered general structure of Genetic Algorithm (GA) and developed a new version of that based on Data Envelopment Analysis (DEA). Two objective functions assumed as two different inputs for each Decision Making Unit (DMU). In this paper we focused on efficiency score of DMUs and efficient frontier concept in DEA technique. After introducing the method we defined two different scenarios with considering two types of mutation operator. Also we provided an experimental design with some computational results to show the performance of algorithm. The results show that the algorithm implements in a reasonable time.

Authors:

• Fatemeh Dadkhah
• Hossein Ali Akbarpour

Keywords:

• Data envelopment analysis
• Efficiency
• Flexible flow shops
• Genetic algorithm

References:

[1] M. E. Kurz, and R.G. Askin, "Comparing scheduling rules for flexible
flow lines," International Journal of Production Economics, 2003, 85,
371-388.
[2] M. E. Kurz, and R.G. Askin, "Scheduling flexible flow lines with
sequence-dependent setup times," European Journal of Operational
Research, 2004, 159(1), 66-82.
[3] K. Deb, A. Pratap,S. Agarwal, and T. Meyarivan, "A Fast and Elitist
Multiobjective Genetic Algorithm: NSGA-II," IEEE Transactions on
Evolutionary Computation, 2002, 6(2), 182-197.
[4] A. J. Ruiz-Torres, and F. J. Lo'pez, "Using the FDH formulation of
DEA to evaluate a multi-criteria problem in parallel machine
scheduling," Computers & Industrial Engineering, 2004, 47, 107-121.
[5] R. Tavakkoli-Moghaddam, A. Rahimi-Vahed, A. H. Mirzaei, "A hybrid
multi-objective immune algorithm for a flow shop scheduling problem
with bi-objectives: Weighted mean completion time and weighted mean
tardiness," Information Science, 2007, 177, 5072-5090.
[6] A. Charnes, W.W. Cooper, and E. Rhodes, "Measuring the efficiency of
decision making units," European Journal of Operation Research, 1978,
429-444.
[7] R. D. Banker, A. Charnes, and W.W. Cooper, "Some models for
estimating technical and scale inefficiencies in data envelopment
analysis," Management Science, 1984, 30, 1078-1092.
[8] M. R. Alirezaee and M. Afsharian, "A complete ranking of DMUs using
restrictions in DEA models," Applied Mathematics and Computation,
2007, 189, 1550-1559.
[9] R. Logendran, S. Carson, and E. Hanson, "Group scheduling in flexible
flow shops," International Journal of Production Economics, 2005, 96
(2), 143-155.
[10] R. Logendran, S. Carson, and E. Hanson, P. deSzoeke, and F. Barnard
"Sequence-dependent group scheduling problems in flexible flow
shops," International Journal of Production Economics, 2006, 102, 66-
86.