Generating efficient schedules for identical parallel machines involving flow-time and tardy jobs

This paper considers the problem of generating a set of efficient (non-dominated) schedules on identical parallel machines involving total flow-time and total number of tardy jobs. In view of the NP-hard nature of this problem, heuristic algorithms are proposed for its solution. Two evaluation methods that provide a scheme by which multiple non-dominated sets can be compared are described and used to compare the performance of the proposed algorithms. Results of several experiments demonstrate the capability of the proposed algorithms and evaluation methodologies to address the problem at hand. (C) 2004 Elsevier B.V. All rights reserved.