Evaluation of grouping methods for solving one-mode blockmodeling problems

Abstract

Allocating resources to a group, subject to restrictions, is a scheduling problem in manufacturing and service industries. One such problem is the scheduling of timetables for industrial training, schools, colleges and universities. A method is proposed in this study for solving one-mode block modelling problems. The question this study attempts to answer is: How does the proposed method compare to methods from the literature designed to solve similar problems and how can the method be improved upon. This was done by creating the method, studying the literature and implementing methods found therein. The proposed method was then improved empirically by implementing and comparing all these methods. The improved Proposed Method combined the Hill Climbing method’s speed, the Grouping Genetic Algorithm’s nature-inspired improvements and used some random number generation and combinatorics. This created a method that is time efficient and finds good solutions for grouping problems which have one type of object but with values relative to each other. Results from this study may benefit the North West University where it might be implemented in order to program the assessment week and examination timetables. At a later date, this method can be used to optimize class timetables for universities or related application areas. skeduleringsprobleem in die vervaardiging- en diensnywerhede. Een probleem van die aard is die skedulering van roosters vir industri¨ele opleiding, skole en universiteite. In hierdie studie word ’n metode vir die oplossing van een-modus blokmodelleringsprobleme voorgestel. Die vraag wat hierdie studie poog om te beantwoord is: Hoe vergelyk die voorgestelde metode met metodes uit vorige navorsing wat ontwerp is om soortgelyke probleme op te los en hoe kan die voorgestelde metode verbeter word. Dit is gedoen deur die metode te ontwerp en kodeer, die literatuur te bestudeer en ander metodes wat daarin gevind is te implementeer. Die voorgestelde metode is dan empiries verbeter deur al hierdie metodes te implementeer en te vergelyk. Die verbeterde voorgestelde metode kombineer die spoed van die Hill Climbing metode, die verbeterings van die Grouping Genetic Algoritme soos deur die natuur ge¨ınspireer en die gebruik van kansgetalle en kombinatorika. Dit het in ’n metode onwikkel wat vinnig en doeltreffende is en wat goeie oplossings vir groeperingsprobleme vind wat ’n objek het met waardes relatief tot mekaar. Resultate van hierdie studie kan tot voordeel wees vir die Noordwes-Universiteit, waar dit ge¨ımplementeer kan word om die assesseringsweek en eksamenroostersprogram te verbeter. Op ’n later stadium, kan hierdie metode gebruik word om klasroosters vir universiteite of verwante velde te optimaliseer.