Using the FDH formulation of DEA to evaluate a multi-criteria problem in parallel machine scheduling

We consider the problem of scheduling jobs on parallel machines when there are two criteria to optimize, namely, minimizing both the makespan and the number of tardy jobs. We propose four heuristics to find solutions to this problem, which we evaluate and compare using the Free Disposal Hull (FDH) formulation of Data Envelopment Analysis (DEA). Our approach illustrates how DEA can be used to compare the performance of heuristics in a multi-criteria environment. We also analyze the impact that some scheduling elements, like the number of machines, the ratio jobs/machines, the congestion, etc. have on the heuristics. (C) 2004 Elsevier Ltd. All rights reserved.