SCHEDULING TO OPTIMIZE FUNCTIONS OF JOB TARDINESS: PROBLEM STRUCTURE AND ALGORITHMS.

Persistent Link:
http://hdl.handle.net/10150/186646
Title:
SCHEDULING TO OPTIMIZE FUNCTIONS OF JOB TARDINESS: PROBLEM STRUCTURE AND ALGORITHMS.
Author:
VILLARREAL CAREAGA, FRANCISCO JAVIER.
Issue Date:
1983
Publisher:
The University of Arizona.
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.
Abstract:
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.
Type:
text; Dissertation-Reproduction (electronic)
Keywords:
Production scheduling -- Data processing.
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Systems and Industrial Engineering; Graduate College
Degree Grantor:
University of Arizona

Full metadata record

DC FieldValue Language
dc.language.isoenen_US
dc.titleSCHEDULING TO OPTIMIZE FUNCTIONS OF JOB TARDINESS: PROBLEM STRUCTURE AND ALGORITHMS.en_US
dc.creatorVILLARREAL CAREAGA, FRANCISCO JAVIER.en_US
dc.contributor.authorVILLARREAL CAREAGA, FRANCISCO JAVIER.en_US
dc.date.issued1983en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © 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.en_US
dc.description.abstractThis 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.en_US
dc.typetexten_US
dc.typeDissertation-Reproduction (electronic)en_US
dc.subjectProduction scheduling -- Data processing.en_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineSystems and Industrial Engineeringen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.identifier.proquest8319737en_US
dc.identifier.oclc689058287en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.