Browsing by Author "Mkandawile, Mashaka James"

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    Development of algorithms for list colouring problems using random graphs
    (University of Dar es Salaam, 2015) Mkandawile, Mashaka James
    The Thesis was concerned with scheduling problems where a schedule was a Latin rectangle and each cell in the Latin rectangle was filled by an allowed symbol from the list of symbols available in that cell. It was observed from literature that list colouring problems using small list size have not been explored to date. Therefore this research used random graphs to develop heuristics algorithms for scheduling purposes. Findings indicated the existence of heuristic algorithms for estimating the list size and for computing the asymptotic probabilities in random (depleted) graph. Findings also indicated that when a constant p>0 was selected and given n vertices and Latin row r such that r<121-2pn then the Latin rectangle was produced with a probability of at least 1-2n+2e-pn16. Lastly findings provided a recursive procedure for building Latin rectangles row by row in an n×n array of randomly assigned sets chosen such that for all cells, the independent probability of any of the n symbols occurring in the cell is exactly p>0.
  • No Thumbnail Available
    Item
    Development of algorithms for timetabling problem: case study of the University of Dar es Salaam.
    (University of Dar es Salaam, 2004) Mkandawile, Mashaka James
    Timetabling problems consist of scheduling certain number of resources such as classes, teachers, courses and classrooms to a number of time slots on daily basis. The feasible combinations for these resources are the ones that avoid the conflicts between teachers, classes and rooms. Many combinatorial optimization problems arising in real life situations are large and hard (NP-hard). Timetabling problem is a class of NP-hard optimization problem whereby no optimal solution procedure is known to solve the problem in a reasonable time scale. However, some methods have been sought which efficiently produce a feasible solution in a reasonable time. However, these algorithms can not guarantee an optimal solution but give a good approximate solution. For a long time, initial course schedules at the University of Dar-Es-Salaam have been constructed manually depending on the experience of the timetabler, which has resulted into considerable wastage of time and resources. In this study, we have developed global heuristic algorithms for approximate solution to timetabling problem using two global heuristics, Tabu search and Simulated annealing. Both algorithms have been described and implemented using real data from the . The results were tested and comparative analysis done based on the solutions produced.