Date of Graduation

2004

Document Type

Thesis

Degree Type

MS

Committee Chair

Wafik H. Iskander

Abstract

This research addresses the multiple stage flexible flow shop with buffer limitation in order to maximize the sum of machines free time at the end of the process within the minimum makespan (FFs (Pm1, Pm2, ..., Pms)/block/ FL max ). Various approaches were used to obtain good solutions for the problem and an analysis was preformed to evaluate the quality obtained with each approach. An exact algorithm with two separate phases was developed using mixed integer programming. In the first phase, C max is minimized, then in the second phase, the machines free time is maximized. This model had a very large number of constraints and variables. A second model was hence developed. This model was more efficient and could handle slightly larger problems, as it uses fewer constraints and variables. In both models, the computational effort required to solve the problem increases rapidly with the size of the problem. Therefore a construction algorithm (MGPAFFS) was developed to obtain near-optimal solutions in reasonable time. A second algorithm (SAFFS), which uses the simulated annealing meta-heuristic, was developed and used to improve the solution obtained with the construction algorithm. In order to evaluate the algorithms developed, a lower bound for the objective function was developed. Problems were solved and results were used to compare between the Simulated Annealing results and the lower bounds; and to measure the improvement of simulated annealing over the construction algorithm. Two data sets were generated, each with eight operation environments, and 10 problems for each environment. Problems in the first data set have 30 jobs each, while in data set two they have 60 jobs. The average of the results obtained showed that the simulated annealing results are within 1.6 - 28.3% and 2.2 - 32.7% of the lower bound for data set 1 and 2 respectively. A comparison of the average values shows that the simulated annealing improved the results obtained from the construction algorithm between 1.2 – 4.9% for data set 1 and 0.9 - 8.9% for data set 2.

Download

Share

COinS