DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
  1. DZone
  2. Data Engineering
  3. AI/ML
  4. The Examination Timetabling Problem

The Examination Timetabling Problem

Geoffrey De Smet user avatar by
Geoffrey De Smet
·
Nov. 11, 09 · Interview
Like (0)
Save
Tweet
Share
9.83K Views

Join the DZone community and get the full member experience.

Join For Free

Next week I 'll give a presentation about the timetabling problem at Devoxx. But what is it exactly? In the examination timetabling problem we need to assign exams to periods (AKA timeslots) and to rooms. Each student takes several exams. This would be easy, except for the 14 distinct constraints that need to be respected as much as possible. For example, a student cannot take 2 exams at the same time. Or, a student does not like to have 2 exams on the same day. This diagram shows a tiny examination problem:

Examination timetabling problem

On the top you can see which students takes which exams. For example, Ann (student A) takes History and Math. But Bobby and Carla also take the History exam. There are only 3 periods (monday morning, friday morning and friday afternoon) and 2 rooms (X with 4 seats and Y with 3 seats) available.

So we need to write an algorithm that assigns each exam to a period and also to a room. In practice for real-world university examinations, brute force (or even branch-and-bound) takes more then a billion years. So we need a faster, maybe less perfect algorithm.

The Example 1 algorithm schedules the biggest exams into the biggest rooms first, but it broke a couple of constraints. Greg (student G) has to take the Geo and Eng exams at the same time. And both Edna and Fred aren't too happy because they each have 2 exams on Friday.

The Drools Solver algorithm does a better job, but still gives Edna 2 exams on Friday, which is actually unavoidable because she has 3 exams and there are only 3 periods.

Wondering how Drools Solver does this? Come to my BOF presentation on Examination timetabling with Drools Solver at Devoxx on monday 16 november at 8PM! Or you can just download the example from the Drools webpage.

 

Drools Algorithm Devoxx History (command) career neural network Diagram Schedule (computer science) GEOS (16-bit operating system) Fred (chatterbot)

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • How To Create and Edit Excel XLSX Documents in Java
  • ChatGPT: The Unexpected API Test Automation Help
  • Top Three Docker Alternatives To Consider
  • Select ChatGPT From SQL? You Bet!

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends: