Bicriteria optimization of schedules on one and two machines

The practical applications of scheduling generally involve the optimization of more than one criterion. This thesis focuses on the bicriteria optimization problem of scheduling jobs on single and two machines. The optimization criteria that are considered are those of minimization of maximum tardiness and minimization of the total number of tardy jobs in the schedule. The former is considered as the primary criterion while the latter is considered as the secondary criterion. For the single machine problem, a search tree method is presented which is based on the implementation of some new dominance rules. Computational results presented show that the performance of this algorithm is better than that of an earlier work reported in the literature.

For the two machine problem, a heuristic algorithm is developed to minimize maximum tardiness. Computational results are presented regarding the performance of this heuristic. A search tree method is developed for the optimization of the secondary criterion. This search tree method is similar to that for the single machine problem except that it does not use the dominance rules that were developed for the single machine case. Computational experience is presented for this algorithm.