A new hybrid meta-heuristic algorithm for solving single machine scheduling problems
| dc.contributor.author | Zlobinsky, Natasha | |
| dc.date.accessioned | 2017-12-05T11:27:14Z | |
| dc.date.available | 2017-12-05T11:27:14Z | |
| dc.date.issued | 2017 | |
| dc.description | A dissertation submitted in partial ful lment of the degree of Master of Science in Engineering (Electrical) (50/50) in the Faculty of Engineering and the Built Environment Department of Electrical and Information Engineering May 2017 | en_ZA |
| dc.description.abstract | Numerous applications in a wide variety of elds has resulted in a rich history of research into optimisation for scheduling. Although it is a fundamental form of the problem, the single machine scheduling problem with two or more objectives is known to be NP-hard. For this reason we consider the single machine problem a good test bed for solution algorithms. While there is a plethora of research into various aspects of scheduling problems, little has been done in evaluating the performance of the Simulated Annealing algorithm for the fundamental problem, or using it in combination with other techniques. Speci cally, this has not been done for minimising total weighted earliness and tardiness, which is the optimisation objective of this work. If we consider a mere ten jobs for scheduling, this results in over 3.6 million possible solution schedules. It is thus of de nite practical necessity to reduce the search space in order to nd an optimal or acceptable suboptimal solution in a shorter time, especially when scaling up the problem size. This is of particular importance in the application area of packet scheduling in wireless communications networks where the tolerance for computational delays is very low. The main contribution of this work is to investigate the hypothesis that inserting a step of pre-sampling by Markov Chain Monte Carlo methods before running the Simulated Annealing algorithm on the pruned search space can result in overall reduced running times. The search space is divided into a number of sections and Metropolis-Hastings Markov Chain Monte Carlo is performed over the sections in order to reduce the search space for Simulated Annealing by a factor of 20 to 100. Trade-o s are found between the run time and number of sections of the pre-sampling algorithm, and the run time of Simulated Annealing for minimising the percentage deviation of the nal result from the optimal solution cost. Algorithm performance is determined both by computational complexity and the quality of the solution (i.e. the percentage deviation from the optimal). We nd that the running time can be reduced by a factor of 4.5 to ensure a 2% deviation from the optimal, as compared to the basic Simulated Annealing algorithm on the full search space. More importantly, we are able to reduce the complexity of nding the optimal from O(n:n!) for a complete search to O(nNS) for Simulated Annealing to O(n(NMr +NS)+m) for the input variables n jobs, NS SA iterations, NM Metropolis- Hastings iterations, r inner samples and m sections. | en_ZA |
| dc.description.librarian | MT 2017 | en_ZA |
| dc.format.extent | Online resource (xiv, 141 leaves) | |
| dc.identifier.citation | Zlobinsky, Natasha (2017) A new hybrid meta-heuristic algorithm for solving single machine scheduling problems, University of the Witwatersrand, <http://hdl.handle.net/10539/23456> | |
| dc.identifier.uri | http://hdl.handle.net/10539/23456 | |
| dc.language.iso | en | en_ZA |
| dc.subject.lcsh | Simulated annealing (Mathematics) | |
| dc.subject.lcsh | Combinatorial optimization | |
| dc.subject.lcsh | Heuristic programming | |
| dc.subject.lcsh | Monte Carlo method | |
| dc.subject.lcsh | Markov processes | |
| dc.title | A new hybrid meta-heuristic algorithm for solving single machine scheduling problems | en_ZA |
| dc.type | Thesis | en_ZA |