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 July 30, 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 July 30, 2014).

Share This




More Science & Society News

Wednesday, July 30, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

Britain Testing Driverless Cars on Roadways

Britain Testing Driverless Cars on Roadways

AP (July 30, 2014) British officials said on Wednesday that driverless cars will be tested on roads in as many as three cities in a trial program set to begin in January. Officials said the tests will last up to three years. (July 30) Video provided by AP
Powered by NewsLook.com
Health Insurers' Profits Slide

Health Insurers' Profits Slide

Reuters - Business Video Online (July 30, 2014) Obamacare-related costs were said to be behind the profit plunge at Wellpoint and Humana, but Wellpoint sees the new exchanges boosting its earnings for the full year. Fred Katayama reports. Video provided by Reuters
Powered by NewsLook.com
China's Drone King Says the Revolution Depends on Regulators

China's Drone King Says the Revolution Depends on Regulators

Reuters - Business Video Online (July 30, 2014) Comparing his current crop of drones to early personal computers, DJI founder Frank Wang says the industry is poised for a growth surge - assuming regulators in more markets clear it for takeoff. Jon Gordon reports. Video provided by Reuters
Powered by NewsLook.com
Climate Change Could Cost Billions, According To White House

Climate Change Could Cost Billions, According To White House

Newsy (July 29, 2014) A report from the White House warns not curbing greenhouse gas emissions could cost the U.S. billions. Video provided by Newsy
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