<p>WARDONO, BAGAS. Algorithms for the multi-stage parallel machine problem with buffer constraints. (Under the direction of Yahya Fathi).We study two problems in the context of scheduling N jobs on parallel machines in L successive stages with the primary objective of minimizing the makespan. In the first problem we assume that there are unlimited buffer capacities between successive stages. We refer to this problem as the FSPM problem. In the second problem, we assume that the buffer capacities are finite and given, and we refer to it as FSPM/b problem. Both problems are shown to be NP-hard.We focus our attention in developing heuristic search procedures for solving both problems. These procedures include the local improvement, the genetic algorithm, and the tabu search. In this context, we use two different solution representations, namely the matrix representation and the vector representation. To evaluate these procedures on an empirical basis, we carry out an extensive computational experiment consisting of two different types of data sets. The problem instances in one data set are constructed in such a manner that the corresponding optimal makespan can be easily determined. The optimal makespan of the instances in the second data set are not known. We also develop a set of lower bounds for the optimal makespan of the problem. The experimental results with the procedures that we propose show that the search procedures which are based on vector representation perform reasonably well. Among the various procedures based on this representation, our tabu search implementation was the most effective.In the context of FSPM/b problem, we also conduct an experiment with a third set of data which is available in the open literature. From the experimental results, we demonstrate the characteristic of the proposed algorithms with various buffer configurations.<P>
| Identifer | oai:union.ndltd.org:NCSU/oai:NCSU:etd-20010507-122017 |
| Date | 07 May 2001 |
| Creators | Wardono, Bagas |
| Contributors | Dr. Yahya Fathi, Dr. Salah E. Elmaghraby, Dr. Henry L. Nuttle, Dr. Russell E. King |
| Publisher | NCSU |
| Source Sets | North Carolina State University |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://www.lib.ncsu.edu/theses/available/etd-20010507-122017 |
| Rights | unrestricted, I hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to NC State University or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report. |
Page generated in 0.0019 seconds