8

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.

Jonas
  • 121,568
  • 97
  • 310
  • 388
Smooth Operator
  • 268
  • 3
  • 13
  • 2
    I'm voting to close because, while arguably interesting, there doesn't seem to be a *programming* problem here. – Noon Silk Jun 05 '10 at 02:17
  • 4
    sure there is, he said he wants to do it in SQL. sounds like a programming problem to me. – Muad'Dib Jun 05 '10 at 02:19
  • 1
    @Muad'Dib The language doesn't seem to be meaningful to me. Once you define the actual criteria, it can be implemented pretty easily in any language. Sounds like the problem is *what criteria*. – Noon Silk Jun 05 '10 at 02:25
  • I agree. I'm not sure where silky is coming from. I want to write code, to use databases and sql to generate a list that I can output. :) Appreciate the support. It's not meant to be a subjective question at all. If you know how to solve scheduling problems with assets, or key things to look out for in terms of coding, with examples, or not, I'd like it all, instead of learning the longer way on my own. – Smooth Operator Jun 05 '10 at 02:25
  • 2
    Silky, with great respect, algorithm problems are programming problems the last time I checked. Sometimes you need a blueprint with some engineering and thought in addition to the hammer and nails of banging out the code if you're building more than a shed. ;) And specifically asking to write it in sql, like I have modified the question to clarify, should be enough. I'm not that much of a newb here, just don't want to advertise the radio station's business in public. I appreciate your help to clarify the question to get the attention it needs from someone with sql/scheduling.. Thanks! – Smooth Operator Jun 05 '10 at 02:28
  • 2
    @Grembo: There is no algorithmic complexity here. The only issue is the *criteria is not known*. Only industry can determine the criteria, and once you have it, it's trivial to implement. – Noon Silk Jun 05 '10 at 02:31
  • 1
    @Smooth Cheers; what I'm suggesting to you is that you sit down with pencil and paper and come up with criteria for ad-showing of your own choosing. Once you invent it, it will be easy to implement in some psuedo language, then you can adapt that to a combination of SQL + Some code or purely SQL, or whatever is appropriate. If you find *that* difficult, then I think this forum would be useful. – Noon Silk Jun 05 '10 at 02:34
  • @Silky, Ah, I think I see what you're saying. I'm looking for input before I spend more time with a pen and pencil. I already have appointment scheduling code that works. The concept of doing rules based scheduling though, is a bit more sophisticated, as it may/may not go into dynamic sql queries, or some other path. The some other path is all i'm trying to save myself wandering in the desert on. Since I'm a volunteer, it's neither a pet project or paid work so I want to deliver something of value as quickly as I can. – Smooth Operator Jun 05 '10 at 02:42
  • 1
    @Smooth: Yes, I understand. As I've tried to imply (not very clearly) once you have the criteria, you can just adust your data so that the items that meet the criteria are marked as such, and then just select those. I.e. perhaps have a background task that updates the data to match the criteria you want (PlayCount, myriad of other properties). That's probably how I'd do it (but I couldn't be sure until I mapped out all the criteria I'd want to consider, now and in the future). – Noon Silk Jun 05 '10 at 02:48

2 Answers2

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.

Grembo
  • 1,223
  • 7
  • 6
  • Cheers, I think this might be a good path to go down... there's a bit of upfront work in getting familiar with the concepts and I think I found a good Java library that seems straight forward enough. I'm considering trying to intentionally fail and write it with sql the first time to learn the pain points... what do you think? Thanks! – Smooth Operator Jun 05 '10 at 22:46
  • Great idea - SQL can behave like a CP in the sense that you can enumerate a set of feasible options then sort. If the feasible options start to become unwieldy, then you might explore ways of cutting back the feasible space. I've run across problems where optimization would be effective, sometimes complete enumeration is feasible AND fast. – Grembo Jun 07 '10 at 15:18
  • @Grembo -- I was thinking the same thing. Based on what you've shared, it seems in a basic sense Dynamic SQL can be set to add or remove constraints as part of a larger business logic loop, or maybe all in SQL itself. A friend pointed out that a Greedy Algorithm might be enough to get me going as I know deep down I'll probably write from scratch again anyways. – Smooth Operator Jun 07 '10 at 19:37
  • Cool - check out references that contain the phrase "constraint satisfaction" and "SQL". Others are doing research in this area and their observations might help you formulate your approach. http://portal.acm.org/citation.cfm?id=1458552 – Grembo Jun 07 '10 at 21:07
0

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.

Community
  • 1
  • 1
Ian Mercer
  • 38,490
  • 8
  • 97
  • 133
  • It's a sledgehammer in terms of CPU utilization, but a small hammer in terms of how much code it takes to produce a 'good enough' answer. It's also a solution that's *very* flexible in terms of new business rules (which will surely come, e.g. advertiser Y prefers mornings, ...). It also has the ability to find a good-enough solution even when no perfect solution exists (e.g. too many advertisers in one particular category today). – Ian Mercer Jun 05 '10 at 05:49