OptaPlanner logo
  • Download
  • Learn
    • Documentation
    • Videos

    • Use cases
    • Compatibility
    • Testimonials and case studies
  • Get help
  • Blog
  • Source
  • Team
  • Services
  • Star
  • T
  • L
  • F
  • YT
Fork me on GitHub

Time scheduling design patterns

Tue 1 December 2015
Avatar Geoffrey De Smet
Geoffrey De Smet

Twitter LinkedIn GitHub

OptaPlanner creator

Designing an efficient domain model for a scheduling problem that involves time (or dates) can seem difficult. Typical use cases are course timetabling, meeting scheduling, vehicle routing with time windows and TV advertisement scheduling. Let’s take a look at design patterns to model such problems in OptaPlanner.

Is starting time a planning variable?

In some cases, the starting time of planning entities doesn’t change during planning. For example in the hospital bed planning example, the arrival date of each patient is already fixed in advance (potentially by another planning stage). Therefore, none of the design patterns below apply, because the starting time is not a planning variable.

However, in many cases it does change and we do need to decide the starting time of each planning entity. In such cases, normally one of these 3 design patterns applies:

assigningTimeToPlanningEntities

Timeslot pattern

In the Timeslot pattern, all entities have the same duration. For example in course timetabling, all lecture take 1 hour. Each lecture is assigned to 1 room and 1 timeslot.

TimeGrain pattern

In the TimeGrain pattern, the entities have different durations, but they start at a course-grained time unit, such as 15 minutes. For most human activities, scheduling on second or subsecond accuracy is pointless: for example in meeting scheduling, expecting people to show up at exactly 3 seconds after 9 o’clock for a meeting is overly optimistic. Therefore scheduling on such a fine-grained accuracy would actually be counter-productive.

Chained Through Time pattern

In the Chained Through Time pattern, a person or machine continuously works on 1 planning entity at time in sequence. For example in vehicle routing with time windows, each vehicle drives from customer to customer, so it handles 1 customer at a time. The starting time of each planning entity is calculated based on the ending time of the previous planning entity.

This pattern also works well for scheduling TV advertisements, because each advertisement starts when the previous ends.

Conclusion

When facing a time scheduling problem, take a look which of the design patterns best fits your requirements. It will improve your development speed as well as solver efficiency and scalability.

For more information about the flexibility, advantages and disadvantages of each design pattern, read the documentation (6.4.0.Beta1 or later).


Permalink
 tagged as design algorithm

Comments

Visit our forum to comment
AtomNews feed
Don’t want to miss a single blog post?
Follow us on
  • T
  • L
  • F
Blog archive
Latest release
  • 8.35.0.Final released
    Fri 3 March 2023
Upcoming events
    Add event / Archive
Latest blog posts
  • OptaPlanner 9 is coming
    Tue 21 February 2023
    Lukáš Petrovický
  • Farewell - a new lead
    Tue 15 November 2022
    Geoffrey De Smet
  • Run OptaPlanner workloads on OpenShift, part II
    Wed 9 November 2022
    Radovan Synek
  • Bavet - A faster score engine for OptaPlanner
    Tue 6 September 2022
    Geoffrey De Smet
  • Run OptaPlanner workloads on OpenShift, part I.
    Thu 9 June 2022
    Radovan Synek
  • OptaPlanner deprecates score DRL
    Thu 26 May 2022
    Lukáš Petrovický
  • Real-time planning meets SolverManager
    Mon 7 March 2022
    Radovan Synek
  • Blog archive
Latest videos
  • The Vehicle Routing Problem
    Fri 23 September 2022
    Geoffrey De Smet
  • Introduction to OptaPlanner AI constraint solver
    Thu 25 August 2022
    Anna Dupliak
  • On schedule: Artificial Intelligence plans that meet expectations
    Sat 23 July 2022
    Geoffrey De Smet
  • Host your OptaPlanner app on OpenShift (Kubernetes)
    Mon 7 February 2022
    Geoffrey De Smet
  • OptaPlanner - A fast, easy-to-use, open source AI constraint solver for software developers
    Mon 31 January 2022
  • Order picking planning with OptaPlanner
    Fri 31 December 2021
    Anna Dupliak
  • AI lesson scheduling on Quarkus with OptaPlanner
    Thu 18 November 2021
    Geoffrey De Smet
  • Video archive

OptaPlanner is open. All dependencies of this project are available under the Apache Software License 2.0 or a compatible license. OptaPlanner is trademarked.

This website was built with JBake and is open source.

Community

  • Blog
  • Get Help
  • Team
  • Governance
  • Academic research

Code

  • Build from source
  • Issue tracker
  • Release notes
  • Upgrade recipes
  • Logo and branding
CC by 3.0 | Privacy Policy
Sponsored by Red Hat