Advanced Engineering Forum Vol. 35

Abstract: This paper considers the bicriteria scheduling problem of minimizing the total completion time and maximum lateness with zero release dates. The problem is NP hard, though Early Due Date (EDD) and Shortest Processing Time (SPT) rules yielded optimal solutions for maximum lateness and total completion time, respectively if each criterion were to be considered singly. Thus, the values of each of the criteria for the two proposed heuristics; SII and PI were compared to the optimal solution of the sub problems. Results of computational experiment on job sizes varies from 5-100 jobs showed that the two proposed solution methods yielded results not significantly different from the optimal. This is because the two heuristic yielded results not significantly from the optimal sub-problems for the two performance measures at 95% significant level.