3. Electronic Theses and Dissertations (ETDs) - All submissions
Permanent URI for this communityhttps://wiredspace.wits.ac.za/handle/10539/45
Browse
2 results
Search Results
Item A new hybrid meta-heuristic algorithm for solving single machine scheduling problems(2017) Zlobinsky, NatashaNumerous 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.Item Contextualized risk mitigation based on geological proxies in alluvial diamond mining using geostatistical techniques(2016) Jacob, JanaQuantifying risk in the absence of hard data presents a significant challenge. Onshore mining of the diamondiferous linear beach deposit along the south western coast of Namibia has been ongoing for more than 80 years. A historical delineated campaign from the 1930s to 1960s used coast perpendicular trenches spaced 500 m apart, comprising a total of 26 000 individual samples, to identify 6 onshore raised beaches. These linear beaches extend offshore and are successfully mined in water depths deeper than 30 m. There is, however, a roughly 4 km wide submerged coast parallel strip adjacent to the mostly mined out onshore beaches for which no real hard data is available at present. The submerged beaches within the 4 km coast parallel strip hold great potential for being highly diamondiferous. To date hard data is not yet available to quantify or validate this potential. The question is how to obtain sufficient hard data within the techno economic constraints to enable a resource with an acceptable level of confidence to be developed. The work presented in this thesis illustrates how virtual orebodies (VOBs) are created based on geological proxies in order to have a basis to assess and rank different sampling and drilling strategies. Overview of 4 papers Paper I demonstrates the challenge of obtaining a realistic variogram that can be used in variogram-based geostatistical simulations. Simulated annealing is used to unfold the coastline and improve the detectable variography for a number of the beaches. Paper II shows how expert opinion interpretation is used to supplement sparse data that is utilised to create an indicator simulation to study the presence and absence of diamondiferous gravel. When only the sparse data is used the resultant simulation is unsuitable as a VOB upon which drilling strategies can be assessed. Paper III outlines how expert opinion hand sketches are used to create a VOB. The composite probability map based on geological proxies is adjusted using a grade profile based on adjacent onshore data before it is seeded with stones and used as a VOB for strategy testing. Paper IV illustrates how the Nachman model based on a Negative Binomial Distribution (NBD) is used to predict a minimum background grade by considering only the zero proportions (Zp) of the grade data. v Conclusions and future work In the realm of creating spatial simulations that can serve as VOBs it is very difficult to attempt to quantify uncertainty when no hard data is available. In the absence of hard data, geological proxies and expert opinion are the only inputs that can be used to create VOBs. Subsequently these VOBs are used as a base to be analysed in order to evaluate and rank different sampling and drilling strategies based on techno economic constraints. VOBs must be updated and reviewed as hard data becomes available after which sampling strategies should be reassessed. During early stage exploration projects the Zp of sample results can be used to predict a minimum background grade and rank different targets for further sampling and valuation. The research highlights the possibility that multi point statistics (MPS) can be used. Higher order MPS should be further investigated as an additional method for creating VOBs upon which sampling strategies can be assessed.