| A major problem for both small and large manufactures is the scheduling of single machines. Due to the fact of only having one machine available to process numerous jobs, manufacturers must make the critical decision of when and what jobs to schedule. The research contained within this thesis attempts to develop methods that find good solutions for single machine problems with varying number of jobs to be scheduled.; The meta-heuristic approach, Meta-RaPS, was used for this study. Meta-RaPS (Meta-heuristic for Randomized Priority Search) includes randomness in the Earliest Due Date (EDD) and Apparent Tardiness Cost (ATC) scheduling algorithms. The inclusion of randomness is thought to produce results better than those found using only the priority rule by allowing the heuristic to avoid local optima. The intent of this research is to develop better solutions as a result of the randomness than those found only using the original algorithms.; Data sets with known optimal solutions were evaluated with the EDD and ATC heuristics as well as with these heuristics included in Meta-RaPS.{09}The data consisted of three sets of 40, 50, and 100 jobs to schedule on a single machine, with each set having 125 different problems (totaling 375 different problems). The results show the inclusion of randomness in a simple priority rule though the use of Meta-RaPS led to solution that where 2.76% to 16% better in terms of EDD and .62% to 2% better in terms of ATC. |
