This dissertation addresses the problem of scheduling a set of jobs under two different measures of performance: total tardiness and weighted number of tardy jobs. A new solution approach is presented for the single-machine tardiness problem. This views the problem as one of determining an optimal partition of the job set into early and tardy subsets. The scheme is validated by the development of necessary conditions for optimality. It is shown that if an optimal partition of the jobs into early and tardy subsets is given, the conditions are not only necessary but also sufficient. These results are used to derive a polynomial algorithm to generate a sequence that satisfies these conditions for any arbitrary partition. The implications of these results with respect to solving the tardiness problem, as well as some other related problems, are examined. Particular emphasis is placed on the impact of the partition approach as a device to enhance the performance of existing branch-and-bound procedures. The use of this approach to generate valid inequalities is also discussed. The problem of scheduling a single machine to minimize the weighted number of tardy jobs is examined in detail. A new branch-and-bound procedure is presented as well as the first extensive computational study of the problem. The proposed algorithm relies on lower bounds obtained by means of two relaxations of the problem for which efficient solution procedures exist. The merits of both bounding schemes are extensively tested. The computational results indicate that exact solutions for large problems can be obtained in just a few seconds of computer time. The efficacy of the approach as a heuristic method is also verified. Further, the computational experience provides insight into how various problem parameters affect the solution difficulty of particular problem instances. The multiple-processor version of the weighted number of tardy jobs model is also considered. The basic algorithmic framework for the single-machine problem is extended to obtain optimal preemptive schedules for parallel machines, which may be identical, uniform, or unrelated.
| Identifer | oai:union.ndltd.org:arizona.edu/oai:arizona.openrepository.com:10150/186646 |
| Date | January 1983 |
| Creators | VILLARREAL CAREAGA, FRANCISCO JAVIER. |
| Publisher | The University of Arizona. |
| Source Sets | University of Arizona |
| Language | English |
| Detected Language | English |
| Type | text, Dissertation-Reproduction (electronic) |
| Rights | Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author. |
Page generated in 0.0018 seconds