I am looking for a radio advertising scheduling algorithm / example / experience

Question

Tried doing a bit of research on the following with no luck. Thought I'd ask here in case someone has come across it before.

I help a volunteer-run radio station with their technology needs. One of the main things that have come up is they would like to schedule their advertising programmatically.

There are a lot of neat and complex rule engines out there for advertising, but all we need is something pretty simple (along with any experience that's worth thinking about).

I would like to write something in SQL if possible to deal with these entities. Ideally if someone has written something like this for other advertising mediums (web, etc.,) it would be really helpful.

Entities:

• Ads (consisting of a category, # of plays per day, start date, end date or permanent play)
• Ad Category (Restaurant, Health, Food store, etc.)

To over-simplify the problem, this will be a elegant sql statement. Getting there... :)

I would like to be able to generate a playlist per day using the above two entities where:

• No two ads in the same category are played within x number of ads of each other.
• (nice to have) high promotion ads can be pushed

At this time, there are no "ad slots" to fill. There is no "time of day" considerations.

We queue up the ads for the day and go through them between songs/shows, etc. We know how many per hour we have to fill, etc.

Any thoughts/ideas/links/examples? I'm going to keep on looking and hopefully come across something instead of learning it the long way.

Answer 1

Very interesting question, SMO. Right now it looks like a constraint programming problem because you aren't looking for an optimal solution, just one that satisfies all the constraints you have specified. In response to those who wanted to close the question, I'd say they need to check out constraint programming a bit. It's far closer to stackoverflow that any operations research sites.

Look into constraint programming and scheduling - I'll bet you'll find an analogous problem toot sweet !

Keep us posted on your progress, please.

Answer 2

Ignoring the T-SQL request for the moment since that's unlikely to be the best language to write this in ...

One of my favorites approaches to tough 'layout' problems like this is Simulated Annealing. It's a good approach because you don't need to think HOW to solve the actual problem: all you define is a measure of how good the current layout is (a score if you will) and then you allow random changes that either increase or decrease that score. Over many iterations you gradually reduce the probability of moving to a worse score. This 'simulated annealing' approach reduces the probability of getting stuck in a local minimum.

So in your case the scoring function for a given layout might be based on the distance to the next advert in the same category and the distance to another advert of the same series. If you later have time of day considerations you can easily add them to the score function.

Initially you allocate the adverts sequentially, evenly or randomly within their time window (doesn't really matter which). Now you pick two slots and consider what happens to the score when you switch the contents of those two slots. If either advert moves out of its allowed range you can reject the change immediately. If both are still in range, does it move you to a better overall score? Initially you take changes randomly even if they make it worse but over time you reduce the probability of that happening so that by the end you are moving monotonically towards a better score.

Easy to implement, easy to add new 'rules' that affect score, can easily adjust run-time to accept a 'good enough' answer, ...

Another approach would be to use a genetic algorithm, see this similar question: Best Fit Scheduling Algorithm this is likely harder to program but will probably converge more quickly on a good answer.