An empirical comparison of heuristic and graph theoretic methods for creating maximally diverse groups, VLSI design, and exam scheduling

R. R. Weitz and S. Lakshminarayanan

Omega, 1997, vol. 25, issue 4, 473-482

Abstract: 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 clearly important problems. Forming maximally diverse groups, based upon multiple criteria, has immediate application in academic or training settings where it may be desired to create class sections, or project groups within classes, such that students are immersed in a diverse environment. This research empirically contrasts graph theoretic approaches drawn from VLSI design with heuristics originating from final exam scheduling and the maximum diversity group problem. The methods are tested on a 'real-world' data set and evaluated on the criteria of solution quality and computational resources required. A principal conclusion of this work is that an adaptation of a pair-wise exchange procedure drawn from the final exam scheduling literature outperforms a more sophisticated graph theoretic approach which has previously been shown to be a top performer for VLSI design.

Keywords: graph; theory; timetabling; heuristics; education (search for similar items in EconPapers)
Date: 1997
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305-0483(97)00007-8
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:25:y:1997:i:4:p:473-482

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().