Back to results list
Please use this identifier to cite or link to this item:
|Title:||Single machine scheduling with release dates and due dates||Authors:||Tian, Zhongjun||Keywords:||Production scheduling
Hong Kong Polytechnic University -- Dissertations
|Issue Date:||2003||Publisher:||The Hong Kong Polytechnic University||Abstract:||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 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 non-simultaneously 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 the former class, 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, and a due date. All the data are integers. Preemption is allowed. The objective is to schedule the jobs so as to minimize the total tardiness. We study two special cases of this NP-hard problem with the following restrictions, separately: (1) All processing times are equal, while the release dates and due dates are arbitrary. (2) The processing times are arbitrary, while the release dates and due dates are agreeable, namely, all release dates and due dates are similarly ordered. For the second case, we consider two subcases where identical release dates correspond to identical and arbitrary due dates, respectively. For each of the specified problems, we investigate the optimality properties and develop an appropriate algorithm. Some of the results are extended to the single machine scheduling problem without release dates. In the latter class, a set of jobs has to be processed on a single machine that can process no more than 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. The processing times and release dates are arbitrary, while the weights are either arbitrary or identical. The due dates are assigned by three different methods: (1) Constant (CON): all jobs are given exactly the same flow allowance. (2) Slack (SLK): jobs are given flow allowances that reflect equal slacks. (3) Total-work-content (TWK): due dates are based on total work content. 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-haid problems, we provide an NP-hardness proof: and for each of the solvable problems, we introduce a polynomial or pseudo-polynomial algorithm.||Description:||ix, 94 leaves : ill. ; 30 cm.
PolyU Library Call No.: [THS] LG51 .H577P MGT 2003 Tian
|URI:||http://hdl.handle.net/10397/3984||Rights:||All rights reserved.|
|Appears in Collections:||Thesis|
Show full item record
Files in This Item:
|b16974438_link.htm||For PolyU Users||162 B||HTML||View/Open|
|b16974438_ir.pdf||For All Users (Non-printable)||3.98 MB||Adobe PDF||View/Open|
Citations as of Dec 17, 2018
Citations as of Dec 17, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.