A simulated annealing approach to the student-project allocation problem

Abigail H. Chown, Christopher J. Cook, Nigel B. Wilding

Research output: Contribution to journalArticle

Abstract

We describe a solution to the student-project allocation problem using simulated annealing. The problem involves assigning students to projects, where each student has ranked a fixed number of projects in order of preference. Each project is offered by a specific supervisor (or supervisors), and the goal is to find an optimal matching of students to projects taking into account the students' preferences, the constraint that only one student can be assigned to a given project, and the constraint that supervisors have a maximum workload. We show that when applied to a real dataset from a university physics department, simulated annealing allows the rapid determination of high quality solutions to this allocation problem. The quality of the solution is quantified by a satisfaction metric derived from empirical student survey data. Our approach provides high quality allocations in a matter of minutes that are as good as those found previously by the course organizer using a laborious trial-and-error approach. We investigate how the quality of the allocation is affected by the ratio of the number of projects offered to the number of students and the number of projects ranked by each student. We briefly discuss how our approach can be generalized to include other types of constraints and discuss its potential applicability to wider allocation problems.

Original languageEnglish
Pages (from-to)701-708
Number of pages8
JournalAmerican Journal of Physics
Volume86
Issue number9
Early online date23 Aug 2018
DOIs
Publication statusPublished - 1 Sep 2018

Fingerprint

simulated annealing
students
physics

ASJC Scopus subject areas

  • Physics and Astronomy(all)

Cite this

A simulated annealing approach to the student-project allocation problem. / Chown, Abigail H.; Cook, Christopher J.; Wilding, Nigel B.

In: American Journal of Physics, Vol. 86, No. 9, 01.09.2018, p. 701-708.

Research output: Contribution to journalArticle

Chown, Abigail H. ; Cook, Christopher J. ; Wilding, Nigel B. / A simulated annealing approach to the student-project allocation problem. In: American Journal of Physics. 2018 ; Vol. 86, No. 9. pp. 701-708.
@article{73e11f444c53441998ca5bb5b2f038b2,
title = "A simulated annealing approach to the student-project allocation problem",
abstract = "We describe a solution to the student-project allocation problem using simulated annealing. The problem involves assigning students to projects, where each student has ranked a fixed number of projects in order of preference. Each project is offered by a specific supervisor (or supervisors), and the goal is to find an optimal matching of students to projects taking into account the students' preferences, the constraint that only one student can be assigned to a given project, and the constraint that supervisors have a maximum workload. We show that when applied to a real dataset from a university physics department, simulated annealing allows the rapid determination of high quality solutions to this allocation problem. The quality of the solution is quantified by a satisfaction metric derived from empirical student survey data. Our approach provides high quality allocations in a matter of minutes that are as good as those found previously by the course organizer using a laborious trial-and-error approach. We investigate how the quality of the allocation is affected by the ratio of the number of projects offered to the number of students and the number of projects ranked by each student. We briefly discuss how our approach can be generalized to include other types of constraints and discuss its potential applicability to wider allocation problems.",
author = "Chown, {Abigail H.} and Cook, {Christopher J.} and Wilding, {Nigel B.}",
year = "2018",
month = "9",
day = "1",
doi = "10.1119/1.5045331",
language = "English",
volume = "86",
pages = "701--708",
journal = "American Journal of Physics",
issn = "0002-9505",
publisher = "American Association of Physics Teachers",
number = "9",

}

TY - JOUR

T1 - A simulated annealing approach to the student-project allocation problem

AU - Chown, Abigail H.

AU - Cook, Christopher J.

AU - Wilding, Nigel B.

PY - 2018/9/1

Y1 - 2018/9/1

N2 - We describe a solution to the student-project allocation problem using simulated annealing. The problem involves assigning students to projects, where each student has ranked a fixed number of projects in order of preference. Each project is offered by a specific supervisor (or supervisors), and the goal is to find an optimal matching of students to projects taking into account the students' preferences, the constraint that only one student can be assigned to a given project, and the constraint that supervisors have a maximum workload. We show that when applied to a real dataset from a university physics department, simulated annealing allows the rapid determination of high quality solutions to this allocation problem. The quality of the solution is quantified by a satisfaction metric derived from empirical student survey data. Our approach provides high quality allocations in a matter of minutes that are as good as those found previously by the course organizer using a laborious trial-and-error approach. We investigate how the quality of the allocation is affected by the ratio of the number of projects offered to the number of students and the number of projects ranked by each student. We briefly discuss how our approach can be generalized to include other types of constraints and discuss its potential applicability to wider allocation problems.

AB - We describe a solution to the student-project allocation problem using simulated annealing. The problem involves assigning students to projects, where each student has ranked a fixed number of projects in order of preference. Each project is offered by a specific supervisor (or supervisors), and the goal is to find an optimal matching of students to projects taking into account the students' preferences, the constraint that only one student can be assigned to a given project, and the constraint that supervisors have a maximum workload. We show that when applied to a real dataset from a university physics department, simulated annealing allows the rapid determination of high quality solutions to this allocation problem. The quality of the solution is quantified by a satisfaction metric derived from empirical student survey data. Our approach provides high quality allocations in a matter of minutes that are as good as those found previously by the course organizer using a laborious trial-and-error approach. We investigate how the quality of the allocation is affected by the ratio of the number of projects offered to the number of students and the number of projects ranked by each student. We briefly discuss how our approach can be generalized to include other types of constraints and discuss its potential applicability to wider allocation problems.

UR - http://www.scopus.com/inward/record.url?scp=85052514935&partnerID=8YFLogxK

U2 - 10.1119/1.5045331

DO - 10.1119/1.5045331

M3 - Article

VL - 86

SP - 701

EP - 708

JO - American Journal of Physics

JF - American Journal of Physics

SN - 0002-9505

IS - 9

ER -