Citation
A complexity analysis and an algorithmic approach to student sectioning in existing timetables. Journal of Scheduling, 19 (3): 285-293, 2016.
Selected
Abstract
We show that the following fundamental question in student sectioning can be efficiently decided in polynomial time: Is it possible to assign students to sectioned courses with respect to a given timetable with timeslots such that the individual capacities of all sections are not exceeded and no student has more than one appointment per timeslot? Our result opens the possibility of efficiently checking the feasibility of candidate timetables with respect to this question as part of timetabling algorithms. Based on a succinct representation of solutions, we also provide an algorithm to compute optimal assignments in , where is the sum of all specified section capacities. On the other hand, we prove that adding any single of the following constraints turns the above question into an NP-complete problem:Course-selection constraint: Student's course-selections must be respected. Timeslot constraint: Students have individual timeslot restrictions. Multiple-event constraint: Sections may have multiple events in the timetable, and there must be no timeslot clashes between all section-events for each student.
There is no pdf available for this paper. You might like to try to obtain the original source (see the doi, for example)
doi
The doi for this publication is 10.1007/s10951-015-0424-2 You can link directly to the original paper, via the doi, from here
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@ARTICLE{2016-285-293-SI, author = {Dostert, M. and Politz, A. and Schmitz, H.},
title = {{A complexity analysis and an algorithmic approach to student sectioning in existing timetables}},
journal = {Journal of Scheduling},
year = {2016},
volume = {{19}},
pages = {285--293},
number = {3},
note = {Selected},
abstract = {{We show that the following fundamental question in student sectioning can be efficiently decided in polynomial time: Is it possible to assign students to sectioned courses with respect to a given timetable with timeslots such that the individual capacities of all sections are not exceeded and no student has more than one appointment per timeslot? Our result opens the possibility of efficiently checking the feasibility of candidate timetables with respect to this question as part of timetabling algorithms. Based on a succinct representation of solutions, we also provide an algorithm to compute optimal assignments in , where is the sum of all specified section capacities. On the other hand, we prove that adding any single of the following constraints turns the above question into an NP-complete problem:Course-selection constraint: Student's course-selections must be respected. Timeslot constraint: Students have individual timeslot restrictions. Multiple-event constraint: Sections may have multiple events in the timetable, and there must be no timeslot clashes between all section-events for each student.}},
doi = {{10.1007/s10951-015-0424-2}},
eissn = {{1099-1425}},
issn = {{1094-6136}},
owner = {Graham},
timestamp = {2017.01.18},
unique-id = {{ISI:000377606100007}} }