Simulated annealing heuristics for the average flow-time and the number of tardy jobs bi-criteria identical parallel machine problem

This paper presents the first part of a study of a scheduling problem where the objective is to minimize both the number of jobs late and the average flow-time. Unlike previous approaches, a weighted function of the two criteria is not utilized. Heuristics based on simulated annealing and neighborhood search are proposed with the objective of generating schedules that produce a compromise across both criteria. Simulation experiments showed that the heuristics perform well when compared to the optimal solution set for a small problem instance.