The Single Machine Problem to Minimize Maximum Lateness
Larson, Raymond Edward
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/67029
Description
Title
The Single Machine Problem to Minimize Maximum Lateness
Author(s)
Larson, Raymond Edward
Issue Date
1980
Department of Study
Mechanical Engineering
Discipline
Mechanical Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Engineering, Industrial
Language
eng
Abstract
This thesis addresses the problem of sequencing n jobs on one machine so as to minimize the maximum lateness when the jobs may have unequal ready times, processing times, and due dates and pre-emption is not permitted (the n/l/r(,i) (GREATERTHEQ) O/L(,max)) problem. The objective is to improve the efficiency of solution procedures for problems that have a significant number of jobs.
Some useful properties are developed. These properties include the equivalence among three versions of the problem, the symmetrical nature of the problem, and the additive and multiplicative characteristics of the job set parameters. A strong sufficient optimality condition is developed to obtain tight lower bounds on the optimal solution. Optimal singlepass solutions for special cases of the problem are given. The properties are applied in the design of experiments for evaluating the relative performance of solution procedures.
Eleven heuristic procedures are presented. The performance of seven procedures that are shown to be representative of all eleven are evaluated on sets of sample problems against optimal solutions derived by a branch-and-bound algorithm. The main measures of each procedure's comparative quality are (1) the mean number of time units by which its solution exceeds the optimal solution and (2) the percentage of times that an optimal sequence is attained. The motivation for employing heuristic procedures is to obtain a sequence that will provide a satisfactory practical response to real world scheduling problems with minimum computational effort.
This thesis then presents an optimal procedure that is significantly more efficient for solving difficult problems than the McMahon/Florian algorithm which has achieved the best results in this area to date. The primary measures of computational efficiency for these procedures are the mean computer processing time and the percentage of problems solved optimally within a given time limit. An experiment that employs response surface methodology to locate problems within the most difficult area shows the comparative efficiency of this procedure.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
