Files in this item



application/pdf8108574.pdf (3MB)Restricted to U of Illinois
(no description provided)PDF


Title:The Single Machine Problem to Minimize Maximum Lateness
Author(s):Larson, Raymond Edward
Department / Program:Mechanical Engineering
Discipline:Mechanical Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Engineering, Industrial
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.
Issue Date:1980
Description:77 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1980.
Other Identifier(s):(UMI)AAI8108574
Date Available in IDEALS:2014-12-13
Date Deposited:1980

This item appears in the following Collection(s)

Item Statistics