Academic course scheduling under workload and changeover constraints

Andreas Drexl, Jan Juretzka and Frank Salewski

No 337, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre

Abstract: Two phases can be distinguished in academic course scheduling: In phase one lectures have to be assigned to professors, whereas in phase two the lectures have to be scheduled. Here we assume that the lectures are already assigned to professors, i.e. the first phase has been done. For the second phase we look for a schedule of lectures (for one week) in such a way that several restrictions (availability of professors and students; workloads per day; changeover times; etc.) are observed. The problem under consideration is represented as a binary optimization model, where we make use of a new type of resources, i.e. so-called partially renewable resources. It is shown that even the feasibility version of the problem is NP-complete. We present heuristics which are essentially based on three ideas: First, prevent blocking of lectures, rooms and/or time-slots; second, look at the worst-case consequence of local decisions; third, perform regret based biased random sampling. We provide an instance generator for the generation of a representative set of instances. The generator along with a statistical model are used for a thorough experimental evaluation of the methods. Computational results show that the methods solve medium-sized instances to suboptimality.

Keywords: Academic course scheduling; workload constraints; changeover times; partially renewable resources; regret based biased random sampling (search for similar items in EconPapers)
Date: 1993
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://www.econstor.eu/bitstream/10419/155413/1/manuskript_337.pdf (application/pdf)

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:zbw:cauman:337

Access Statistics for this paper

More papers in Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre Contact information at EDIRC.
Bibliographic data for series maintained by ZBW - Leibniz Information Centre for Economics ().