Abstract
This thesis considers two different scheduling problems in industrial settings. The first problem consists of minimizing the total completion time of jobs scheduled on a single machine that must undergo periodic maintenance. Additionally, if a job is not processed until completion before the machine is stopped for maintenance, an additional setup is necessary before processing on the job may be resumed. In this thesis, this problem is proved to be NP-complete in the strong sense. Additionally, a special case of the problem is presented where only two production periods and one maintenance period may occur. This special case is proved to be NP-hard, and a pseudopolynomial time dynamic programming algorithm to solve the special case is presented. The second problem considered here is the job shop scheduling problem where the objective is to minimize the makespan. Local search techniques which have been applied to this problem are discussed with the emphasis being on genetic algorithms. A genetic algorithm and a scheduling model for an actual industrial job shop are developed and combined to provide a search algorithm which finds good schedules for the job shop. This algorithm is compared to the scheduling procedure currently in use by the management of the modeled shop, and results are presented.
Graves, Gregory Howard (1998). Application of the genetic algorithm for global scheduling and a single machine scheduling problem with periodic maintenance and semiresumable jobs. Master's thesis, Texas A&M University. Available electronically from
https : / /hdl .handle .net /1969 .1 /ETD -TAMU -1998 -THESIS -G73.