Featured Research

from universities, journals, and other organizations

Solving the problem of school timetabling

January 11, 2010
Inderscience Publishers
A new approach to solving the problem of school timetabling, known as a GRASP, has been developing by researchers in Brazil.

A new approach to solving the problem of school timetabling, known as a GRASP, has been developing by researchers in Brazil. They report details in a forthcoming issue of the International Journal of Operational Research.

Related Articles

Educational administrators everywhere will attest to just how difficult it is to solve the perennial problem of school timetabling: How to ensure adequate teaching resources and teachers are available in the appropriate classrooms with the appropriate students. Indeed, mathematicians have proved the school timetabling problem to be "NP-hard," which means it is the kind of problem that ranks alongside the classic logistics problem known as the traveling salesman problem and the crystal packing problems (akin to the game Tetris). As there seems to be no shortcut or easy solution to NP-hard problems, finding a single, simple answer, even with a supercomputer, is probably impossible when the input instances are realistically large. Hence the educators' perennial headache.

Now, Arnaldo Vieira Moura and Rafael Augusto Scaraficci of the Institute of Computing, at the University of Campinas, in Brazil, have developed a GRASP (i.e., Greedy Randomized Adaptive Search Procedure) heuristic for the school timetabling problem. This approach, like any other heuristic method, is not guaranteed to find a best answer for each school timetable, but it does help solve the problem for Brazilian high school timetables efficiently and quickly, given their specific requirements.

Educational timetabling problems involve scheduling a number of "meetings" among different resources without them overlapping, so that a suitable teacher is available for a particular subject class at a given time. Until now, solving the school timetabling problem was done manually, or at best with the help of a spreadsheet program. Typically, a manual solution requires expert attention and can take many weeks for large educational establishments. Moreover, because of the problem complexity, planners are not always able to take the best decisions, building schedules that are inconsistent with teaching requirements and do not satisfy all teachers' needs.

"An optimization tool could assist these planners in order to reduce the time they need to build the timetables and to improve the quality of the solutions," the researchers explain. The timetabling problem is defined in terms of a set of "m" disjoint classes of students, "n" teachers, "s" subjects and "p" weekly time periods. The latter are prefixed for each class. The tool must then find a slot for each teacher and ensure that all students receive the requisite lectures each week while simultaneously satisfying a complex set of constraints, like with teachers' preferences and availability, adequate daily balancing of class subjects and collective sport classes. Besides, time grids for different grades might also conflict.

Problems arise because teachers often teach several subjects to students in different classes, students must generally not receive more than 2 or 3 same subject lectures in the same day and they must be back to back, teachers must fulfill their workload requirements and waiting times between lectures must be minimized for both teacher and student. These and other criteria are assigned a degree of importance and the team applies their algorithm, embedded in computer software, by allowing it to pick a given lecture and seeing how well it fits with the "hard" criteria and endeavors to fit it to the "soft" criteria.

GRASP repeats a basic three-step cycle. First, it selects a random lecture and assigns it resources, then adds the next lecture and ranks the options and so on. The growing list of assigned lectures is sorted with those that score the highest in terms of the different criteria moving up the priority list, this is the "greedy" part. The addition of each subsequent lecture must then adapt to fit unless it scores more highly than the others in which case it moves up the list. The second phase improve the list using a "local search procedure" that compares neighboring lectures and re-ranks them in pairs. This phase continues until no further improvements are possible. Finally,a so-called "path-relinking strategy" is used to spot the almost optimum solutions, which are then used to guide the final solution. "The basic cycle is repeated a number of times and the overall champion solution is returned as the final answer of the algorithm," explains Moura.

The team successfully tested their GRASP algorithm on the timetabling problem at three Brazilian high schools. The same algorithm should be adaptable to other educational establishments and other timetabling problems.

Story Source:

The above story is based on materials provided by Inderscience Publishers. Note: Materials may be edited for content and length.

Journal Reference:

  1. A GRASP strategy for a more constrained School Timetabling Problem. Int. J. Operational Research, 2010, 7, 152-170

Cite This Page:

Inderscience Publishers. "Solving the problem of school timetabling." ScienceDaily. ScienceDaily, 11 January 2010. <www.sciencedaily.com/releases/2010/01/100106093631.htm>.
Inderscience Publishers. (2010, January 11). Solving the problem of school timetabling. ScienceDaily. Retrieved March 29, 2015 from www.sciencedaily.com/releases/2010/01/100106093631.htm
Inderscience Publishers. "Solving the problem of school timetabling." ScienceDaily. www.sciencedaily.com/releases/2010/01/100106093631.htm (accessed March 29, 2015).

Share This

More From ScienceDaily

More Science & Society News

Sunday, March 29, 2015

Featured Research

from universities, journals, and other organizations

Featured Videos

from AP, Reuters, AFP, and other news services

Why So Many People Think NASA's Asteroid Mission Is A Waste

Why So Many People Think NASA's Asteroid Mission Is A Waste

Newsy (Mar. 27, 2015) The Asteroid Retrieval Mission announced this week bears little resemblance to its grand beginnings. Even NASA scientists are asking, "Why bother?" Video provided by Newsy
Powered by NewsLook.com
WH Plan to Fight Antibiotic-Resistant Germs

WH Plan to Fight Antibiotic-Resistant Germs

AP (Mar. 27, 2015) The White House on Friday announced a five-year plan to fight the threat posed by antibiotic-resistant bacteria amid fears that once-treatable germs could become deadly. (March 27) Video provided by AP
Powered by NewsLook.com
Indiana Permits Needle Exchange as HIV Cases Skyrocket

Indiana Permits Needle Exchange as HIV Cases Skyrocket

Reuters - US Online Video (Mar. 26, 2015) Governor Mike Pence declares the recent HIV outbreak in rural Indiana a "public health emergency" and authorizes a short-term needle-exchange program. Rough Cut (no reporter narration) Video provided by Reuters
Powered by NewsLook.com
AAA: Distracted Driving a Serious Teen Problem

AAA: Distracted Driving a Serious Teen Problem

AP (Mar. 25, 2015) While distracted driving is not a new problem for teens, new research from the AAA Foundation for Traffic Safety says it&apos;s much more serious than previously thought. (March 25) Video provided by AP
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.


Breaking News:

Strange & Offbeat Stories

Science & Society

Business & Industry

Education & Learning

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News


Free Subscriptions

Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile

Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?

Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile: iPhone Android Web
Follow: Facebook Twitter Google+
Subscribe: RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins