In this dissertation, we study the single machine scheduling problem with an objective of minimizing the total completion time subject to release dates. The problem, denoted 1|rj £UCj ,was known to be strongly NP-hard and both theoretically and practically important. The focus of the research in this dissertation is to develop the efficient algorithms for solving the 1|rj|£UCj problem.
This thesis contains two parts.
In the first part, the theme concerns the approximation approach. We derive a necessary and sufficient condition for local optimality, which can be implemented as a priority rule and be used to construct three heuristic algorithms with running times of O(n log n). By ¡¨local optimality¡¨, we mean the optimality of all candidates whenever a job is selected in a schedule, without considering the other jobs preceding or following. This is the most broadly considered concepts of locally optimal rule. We also identify a dominant subset which is strictly contained in each of all known dominant subsets, where a dominant subset is a set of solutions containing all optimal schedules.
In the second part, we develop our optimality algorithms for the 1|rj |£UCj problem. First, we present a lemma for estimating the sum of delay times of the rest jobs, if the starting time is delayed a period of time in a schedule. Then, using the lemma, partially, we proceed to develop a new partition property and three dominance theorems, that will be used and have improved the branch-and-bound algorithms for our optimization approach. By exploiting the insights gained from our heuristics as a branching scheme and by exploiting our heuristics as an upper bounding procedure, we propose three branch-and-bound algorithms. Our algorithms can optimally solve the problem up to 120 jobs, which is known to be the best till now.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0730103-102253 |
| Date | 30 July 2003 |
| Creators | Yu, Su-Jane |
| Contributors | Din-Horng Yeh, Jen-Chih Yao, Yen-Cherng Lin, Sy-Ming Guu, Tsung-Chyan Lai |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0730103-102253 |
| Rights | withheld, Copyright information available at source archive |
Page generated in 0.0015 seconds