Department of Logistics

Permanent URI for this community

https://scholar.sun.ac.za/handle/10019.1/71

Browse

Browsing Department of Logistics by Author "Benade, Johannes Gerhardus"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    A distributed system for enumerating main classes of sets of orthogonal Latin squares
    (Stellenbosch : Stellenbosch University, 2014-12) Benade, Johannes Gerhardus; Burger, Alewyn; Van Vuuren, Jan Harm; Stellenbosch University. Faculty of Economic and Management Sciences. Dept. of Logistics.
    ENGLISH ABSTRACT: A Latin square is an n n array containing n copies of each of n distinct symbols in such a way that no symbol is repeated in any row or column. Two Latin squares are orthogonal if, when superimposed, the ordered pairs in the n2 cells are all distinct. This notion of orthogonality extends naturally to sets of k > 2 mutually orthogonal Latin squares (abbreviated in the literature as k-MOLS), which nd application in scheduling problems and coding theory. In these instances it is important to di erentiate between structurally di erent k-MOLS. It is thus useful to classify Latin squares and k-MOLS into equivalence classes according to their structural properties | this thesis is concerned speci cally with main classes of k-MOLS, one of the largest equivalence classes of sets of Latin squares. The number of main classes of k-MOLS of orders 3 n 8 have been enumerated in the literature by recursive backtracking algorithms. All enumeration attempts for k-MOLS of order n > 8 have, however, encountered a computational barrier using current computing technology in traditional computing paradigms. In this thesis, the feasibility of these enumerations of order n > 8 is analysed and a potential way of overcoming this computational barrier is proposed. A backtracking enumeration algorithm from the literature is implemented and validated, after which novel estimates of the sizes of the enumeration search trees for k-MOLS of orders n > 8 produced by this backtracking algorithm are presented. It is also advocated that the above-mentioned computational barrier may be overcome by volunteer computing, a computing paradigm in which large computations are distributed over thousands or even millions of volunteered computing devices, such as desktop computers and Android cellphones. A volunteer computing project is designed for the distributed enumeration of main classes of k-MOLS. Initial test results obtained from this volunteer computing project have called for a novel work unit issuing policy which allows the participating host resources to be utilised e ectively during enumerations of main classes of k-MOLS of arbitrary orders. A local pilot study involving the enumeration of main classes of 3-MOLS of order 8 has con rmed the feasibility of adopting the volunteer computing project as an avenue of approach towards the enumeration of k-MOLS of orders n > 8 and preliminary results of an ongoing enumeration attempt for the main classes of 7-MOLS of order 9 are presented.