| In this dissertation a type of scheduling problem found in certain petrochemical production settings is investigated. This setting is a two-stage semicontinuous process with multiple processors at each stage and finite intermediate storage. Product output consists of both blended and nonblended products. The objective is to generate schedules with as small a makespan as possible--that is, to produce schedules with near optimal throughput.;A heuristic, called the Petrochemical Exchange Heuristic (PEH), is presented for solving this type of problem. This heuristic starts with an initial schedule which is then modified by a series of schedule rearrangements. Since the PEH requires an initial schedule for its execution, five dispatching rules are investigated; they are WMTWF, MTWF, LTWF, LMTWF and a modified Johnson's sequence. To establish the quality of the schedules generated by the PEH, makespan lower bounds were developed.;To evaluate the performance of the dispatching rules and PEH, a battery of experimental runs was performed. These runs consisted of randomly generated problems where the number of final products ranged from 50 to 200. A statistical analysis of the results indicated that WMTWF was as good as, or better than, the other dispatching rules when used as the primary scheduling method or to initiate the PEH. An investigation of two different PEH versions indicated that there was no statistically significant difference between the makespans obtained by the two methods. Points at which the PEH can be terminated without significantly degrading the final schedule makespan were determined through an evaluation of the rate of makespan improvement by iteration. The results of this experiment indicate that the PEH is an effective improvement heuristic producing, over the 80 problems investigated, an average final makespan value of 12.33% over the lower bounds. |
