Graduate Thesis Or Dissertation
 

Development and experimental evaluation of branch-and-bound algorithms for determining optimum static job-shop production schedules

Public Deposited

Contenu téléchargeable

Télécharger le fichier PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/41687k66r

Descriptions

Attribute NameValues
Creator
Abstract
  • Branch-and-Bound algorithms are developed to optimally schedule static single- and multi-stage job-shop productions. The 'corollary' of the study is to experimentally verify the effectiveness of branch-and-bound algorithms to overcome the "curse of dimensionality" due to the combinatorial nature of job-shop scheduling problems. The static scheduling problem contemplated in this dissertation assumes that for the given set of n jobs, their deterministic processing times, relative due dates and monotonically decreasing bonus and penalty functions are known. The effectiveness of the selected schedule is evaluated from the total revenue obtained from the bonus and penalty. Based on the branch-and-bound algorithms, two computer programs have been written in FORTRAN IV and their processing times on CDC-3300 recorded. Thirty single- and thirty three-stage problems ranging in size from five to ten jobs were solved. Their CPU times were from a few seconds to four minutes. Regression models were developed to predict both the CPU time and the number of nodes computed by the basic branch-and-bound method. It is predicted that in an eight-hour CDC-3300 CPU time, one single-stage problem with up to 21 jobs can be solved. In this same time duration, the exhaustive search program will not have processed a single-stage problem with more than eight jobs. Two variations of the basic algorithm have been considered: the heuristic near-optimum method and the dominance-tested computational procedure. The heuristic method requires the least computational effort and is a practical scheduling tool for large-size problems, but does not guarantee the optimality of its solution. By applying the dominance-tested variation, the optimum solution can be assured. It requires the generation of a fewer number of nodes than the basic branch-and-bound technique, yet it needs a significantly larger computational time. The basic branch-and-bound algorithm's application to non-job- shop scheduling situations has been illustrated by two examples: the determination of the optimum distribution policy in a marketing study, and of the optimum routing schedule for a fishing vessel harvesting operation. The experimental data verified that branch-and-bound algorithm has been only partially successful in overcoming the "curse of dimensionality." The inherent combinatorial difficulty is still present in the branch-and-bound algorithm though to a lesser degree than in dynamic programming--and a more powerful optimization method must be developed to limit the size of the solution space at an early stage of analysis.
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Déclaration de droits
Publisher
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using ScandAll PRO 1.8.1 on a Fi-6770A in PDF format. CVista PdfCompressor 5.0 was used for pdf compression and textual OCR.
Replaces

Des relations

Parents:

This work has no parents.

Dans Collection:

Articles

La vignette Titre Date de téléchargement Visibilité actes
file details RamalingamPanchatcharam1973.pdf 2017-08-07 Public Télécharger