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 September 19, 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 September 19, 2014).

Share This



More Science & Society News

Friday, September 19, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

The Cost of Ebola

The Cost of Ebola

Reuters - Business Video Online (Sep. 18, 2014) As Sierra Leone prepares for a three-day "lockdown" in its latest bid to stem the spread of Ebola, Ciara Lee looks at the financial implications of fighting the largest ever outbreak of the disease. Video provided by Reuters
Powered by NewsLook.com
U.S. Food Makers Surpass Calorie-Cutting Pledge

U.S. Food Makers Surpass Calorie-Cutting Pledge

Newsy (Sep. 18, 2014) Sixteen large food and beverage companies in the United States that committed to cut calories in their products far surpassed their target. Video provided by Newsy
Powered by NewsLook.com
Stocks Hit All-Time High as Fed Holds Steady

Stocks Hit All-Time High as Fed Holds Steady

AP (Sep. 17, 2014) The Federal Reserve signaled Wednesday that it plans to keep a key interest rate at a record low because a broad range of U.S. economic measures remain subpar. Stocks hit an all-time high on the news. (Sept. 17) Video provided by AP
Powered by NewsLook.com
Some Tobacco Farmers Thrive Amid Challenges

Some Tobacco Farmers Thrive Amid Challenges

AP (Sep. 16, 2014) The South's tobacco country is surviving, and even thriving in some cases, as demand overseas keeps growers in the fields of one of America's oldest cash crops. (Sept. 16) 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:
from the past week

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