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.
[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.
[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.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:62354", author = "Fatemeh Dadkhah and Hossein Ali Akbarpour", title = "Scheduling a Flexible Flow Shops Problem using DEA", abstract = "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.", keywords = "Data envelopment analysis, Efficiency, Flexible flow
shops, Genetic algorithm", volume = "6", number = "1", pages = "94-5", }