Featured Research

from universities, journals, and other organizations

Solving the problem of school timetabling

Date:
January 11, 2010
Source:
Inderscience Publishers
Summary:
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.

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 October 1, 2014 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 October 1, 2014).

Share This



More Science & Society News

Wednesday, October 1, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

US Police Put Body Cameras to the Test

US Police Put Body Cameras to the Test

AFP (Oct. 1, 2014) Police body cameras are gradually being rolled out across the US, with interest surging after the fatal police shooting in August of an unarmed black teenager. Duration: 02:18 Video provided by AFP
Powered by NewsLook.com
Ebola Cases Keep Coming for Monrovia's Island Hospital

Ebola Cases Keep Coming for Monrovia's Island Hospital

AFP (Oct. 1, 2014) A look inside Monrovia's Island Hospital, a key treatment centre in the fight against Ebola in Liberia's capital city. Duration: 00:34 Video provided by AFP
Powered by NewsLook.com
Ebola Puts Stress on Liberian Health Workers

Ebola Puts Stress on Liberian Health Workers

AP (Oct. 1, 2014) The Ebola outbreak is putting stress on first responders in Liberia. Ambulance drivers say they are struggling with chronic shortages of safety equipment and patients who don't want to go to the hospital. (Oct. 1) Video provided by AP
Powered by NewsLook.com
App Teaches Kindergarteners to Code

App Teaches Kindergarteners to Code

AP (Oct. 1, 2014) They can't all read yet, but soon kindergarteners may be able to create basic computer code. Researchers in Massachusetts developed an app that teaches young kids a simple computer programming language. (Oct. 1) 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.

Save/Print:
Share:

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



Save/Print:
Share:

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