AN EMPIRICAL-COMPARISON OF HEURISTIC AND GRAPH-THEORETIC METHODS FOR CREATING MAXIMALLY DIVERSE GROUPS, VLSI DESIGN, AND EXAM SCHEDULING

Creating groups of maximum diversity, VLSI design (where the objective is to group highly connected modules onto the same circuit), and the final exam scheduling task of assigning exam blocks to exam days, are all mathematically equivalent. VLSI design and exam scheduling are cle arly important problems. Forming maximally diverse groups, based upon multiple criteria, has immediate application in academic or training s ettings where it may be desired to create class sections, or project g roups within classes, such that students are immersed in a diverse env ironment. This research empirically contrasts graph theoretic approach es drawn from VLSI design with heuristics originating from final exam scheduling and the maximum diversity group problem. The methods are te sted on a 'real-world' data set and evaluated on the criteria of solut ion quality and computational resources required. A principal conclusi on of this work is that an adaptation of a pair-wise exchange procedur e drawn from the final exam scheduling literature outperforms a more s ophisticated graph theoretic approach which has previously been shown to be a top performer for VLSI design. (C) 1997 Elsevier Science Ltd.