Parallel machine scheduling for minimizing the makespan and the average flow-time

Scheduling problems with multiple criteria represent the reality of decision making in today's competitive environment. Single criteria optimal solutions may be far from optimal in relation to other important criteria. A solution producing a compromise across multiple criteria could be a `better' answer. This paper analyzes a multi-criteria identical parallel machine problem without preemption where the objective is to generate non-dominated bi-criteria solutions for problems with the minimization of Makespan and the Average Flow-time as criteria. This paper presents a simple heuristic based on list ordering techniques to generate multiple tradeoff solutions. The quality of the heuristic's solutions is determined by comparison with solutions produced by full enumeration for a small problem and by a pseudo-random schedule generator for more complex problems. Simulation experiments showed that the heuristic generates 76% of the optimal solutions, and that in all cases, it outperformed the pseudo-random solutions by a large margin in equal or less computation time. The experiments also showed that the number of efficient solutions is relatively small (<4) even for problems with a large number of jobs (80). A small set of efficient solutions is relevant in industrial settings as users need only consider among few choices.