This thesis studies single machine bicriteria scheduling problems. Besides an introduction and a literature survey, it studies four different but related single machine bicriteria scheduling problems. ²...[ Read more ]

This thesis studies single machine bicriteria scheduling problems. Besides an introduction and a literature survey, it studies four different but related single machine bicriteria scheduling problems.

The first one is a single machine scheduling problem to minimize the total weighted earliness subject to minimal number of tardy jobs. We discuss several properties in analyzing the problem and propose a heuristic algorithm with time complexity O(n²) and an efficient Branch and Bound algorithm. The computational experiments showed that the heuristic algorithm is effective in terms of quality of the solutions in most instances while the branch and bound algorithm is efficient for medium-sized problems. The second one is a single machine scheduling problem with distinct due windows to minimize total weighted earliness and tardiness. First, we present a mathematical formulation and study several important properties of the problem. Then we propose an optimal timing algorithm to decide job completion times for a given job sequence. The Tabu search scheme is employed together with the optimal timing algorithm to generate job sequences and final schedules. Several experiments were designed and carried out to demonstrate the performance of the proposed approach. The third one is a single machine common due window scheduling problem in which job processing times are controllable with linear costs. The objective of the problem is to find a job sequence, a processing time for each job, and a position of the common due window to minimize the total cost of weighted earliness/tardiness and processing time compression. We study several properties of the problem and present a polynomial time algorithm with time complexity O(n³) for solving the problem. The last one is concerned with the computational complexity of a single machine scheduling problem to minimize total processing plus weighted flow cost. The computational complexity status of the problem has been open for some twenty years. We give a positive answer to a conjecture for this problem, showing that it is NP-hard at least in the ordinary sense..

Finally, we give some concluding remarks and future research directions relevant to the thesis research.