DZone
Java Zone
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
  • Refcardz
  • Trend Reports
  • Webinars
  • Zones
  • |
    • Agile
    • AI
    • Big Data
    • Cloud
    • Database
    • DevOps
    • Integration
    • IoT
    • Java
    • Microservices
    • Open Source
    • Performance
    • Security
    • Web Dev
DZone > Java Zone > The Examination Timetabling Problem

The Examination Timetabling Problem

Geoffrey De Smet user avatar by
Geoffrey De Smet
·
Nov. 11, 09 · Java Zone · Interview
Like (0)
Save
Tweet
9.57K 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

  • Suspicious Sortings in Unity, ASP.NET Core, and More
  • An Overview of 3 Java Embedded Databases
  • SDLC Vs STLC: What's the Difference?
  • Modernizing Testing With Data Pipelines

Comments

Java Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • MVB Program
  • 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:

DZone.com is powered by 

AnswerHub logo