Scheduling a Flexible Flow Shops Problem using DEA

Authors: Fatemeh Dadkhah, Hossein Ali Akbarpour

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

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

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.