Managing time-scheduled work

Note, this is a slightly abstract question.

Given the following:

  • A product that requires to notify customers 15, 10, and 5minutes before an scheduled time
  • Scheduled times are very specific, and there maybe large clusters of notifications around a scheduled time (e.g. 6:04pm, 7:31pm)

Whats the best architectural choice? I've not kept up with the latest back-end choices.

Things I've looked at:

  • Amazon Simple Queuing service for storing of the "messages"
    • This doesn't seem to have ability to "Delay" delivery of messages
    • Requires long polling/constant polling, which seems partially in efficient
  • Azure Queues
    • Allows delays of messages up to 7 hrs
    • Still requires long polling
  • setTimeout in Node
    • Seems unreliable for many close related time points, and likely going to just get baffling managing them all
  • Wake up every minute and suck from the queue
    • Seems inefficient

What is the recommended pattern for a problem like this?