Unrelated parallel machines are machines that perform the same function but have
different capacity or capability. Thus, the processing time of each job would be different
on machines of different types. The scheduling environment considered is dynamic in
both job release time and machine availability. Additionally, each job considered can
have different weight, and due date. Split jobs are also considered in this research. The
number of jobs that needs to be processed in split-modes is pre-determined and not part
of the scheduling decision. Additional constraints are imposed on split jobs to ensure that
the absolute difference in completion time of the split portions of a job is within a user-specified margin. These constraints are supported by the Just-In-Time manufacturing
concept where inventory has to be maintained at a very low or zero level. The objective
of this research is to minimize the sum of the weighted tardiness of all jobs released
within the planning horizon.
The research problem is modeled as a mixed (binary) integer-linear programming
model and it belongs to the class of NP-hard problems. Thus, one cannot rely on using
an implicit enumeration technique, such as the one based on branch-and-bound, to solve
industry-size problems within a reasonable computation time. Therefore, a higher-level
search heuristic, based on a concept known as tabu search, is developed to solve the
problems. Four different methods based on simple and composite dispatching rules are
used to generate the initial solution that is used by tabu-search as a starting point. Six
different tabu-search based heuristics are developed by incorporating the different
features of tabu search. The heuristics are tested on eight small problems and the quality of their solutions is compared to their optimal solutions, which are obtained by applying
the branch-and-bound technique. The evaluation shows that the tabu-search based
heuristics are capable of obtaining solutions of good quality within a much shorter time.
The best performer among these heuristics recorded a percentage deviation of only
1.18%.
The performance of the tabu-search based heuristics is compared by conducting a
statistical experiment that is based on a split-plot design. Three sizes of problem
structures, ranging from 9 jobs to 60 jobs and from 3 machines to 15 machines are used
in the experiment. The results of the experiment reveal that in comparison to other
initial-generation methods, the composite dispatching rule is capable of obtaining initial
solutions that significantly accelerate the tabu search based heuristic to get to the final
solution. The use of long-term memory function is proven to be advantageous in solving
all problem structures. The long-term memory based on maximum-frequency strategy is
recommended for solving the small problem structure, while the minimum-frequency
strategy is preferred for solving medium and large problem structures. With respect to
the use of tabu-list size as a parameter, the variable tabu-list size is preferred for solving
the smaller problem structure, but the fixed tabu-list size is preferred as the size of the
problems grows from small to medium and then large. / Graduation date: 2000
| Identifer | oai:union.ndltd.org:ORGSU/oai:ir.library.oregonstate.edu:1957/33182 |
| Date | 27 April 2000 |
| Creators | Subur, Fenny |
| Contributors | Logendran, Rasaratnam |
| Source Sets | Oregon State University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis/Dissertation |
Page generated in 0.002 seconds