| In this thesis, we study some classical single machine scheduling problems with release dates and due dates. In a comprehensive review of prior works, we classify the literature into different classes, according to the job characteristics and the optimality criteria. The review reveals that, despite the particular importance of the single machine scheduling models, a few classes of the problems on this topic are rarely or never touched. These classes are worthy of research because of the universality of the scheduling models with unsimultaneously released jobs and the practical significance of due-date-based research. This thesis focuses on two of these classes, which are the preemptive scheduling on a single machine to minimize total tardiness with job restrictions, and the single machine due date assignment with release dates.; In both classes, a set of jobs has to be processed on a single machine that can perform only one job at a time. Each job has a release date, a processing time, a due date and a weight. All the data are integers.; In the former class, preemption is allowed and the weights are identical. The objective is to schedule the jobs so as to minimize the total tardiness. We study two special cases of this NP-hard problem: the cases with equal processing times and agreeable release dates and due dates, separately. For each of the specified problems, we investigate the optimality properties and develop an appropriate algorithm.; In the latter class, the due dates are assigned by three different methods: CON, SLK and TWK. The objective is to schedule the jobs so as to minimize one of the following criteria, the maximum tardiness, the (weighted) number of tardy jobs and the total (weighted) tardiness. We examine the complexity of all the problems with the consideration of the due date assignment methods and the optimality criteria. For each of the NP-hard problems, we provide an NP-hardness proof; and for each of the solvable problems, we introduce a polynomial or pseudo-polynomial algorithm. |
