Track: Operations Management and Operations Research

Abstract

This paper considers the bicriteria scheduling problem of minimizing the average flowtime and maximum earliness on a single machine with zero release dates. The problem is NP hard, though the Minimum Slack Time (MST) and Shortest Processing Time (SPT) rules yield optimal solutions for the maximum earliness (E_max) and average flowtime (F_avg) problems, respectively if each criterion were to be applied singly. Thus, in evaluating two proposed heuristics (SAE and EAO), the values of each of the criteria for the two proposed heuristics were compared against the optimal solution of the sub problems. Computational experimental results with job sizes varying from 5 to 200 jobs show that SAE  is not significantly different from the optimal F_avg. The results also show that for problem sizes, 5 n  30, SAE is not significantly different from the optimal E_max. However, the results of EAO heuristic is significantly different from the optimal for the two criteria except for F_avg for problem sizes, 40 n  200. Therefore, the SAE heuristic is recommended for simultaneously minimizing average flowtime and maximum earliness on a single machine with zero release dates.

Keywords: Average flowtime, maximum earliness, optimal, heuristics, bicriteria