Algorithms / Scheduling Question

Factual Questions
1

Let’s say I have x number of senators. Y number of journalists each want their own private meeting with some number of senators (some will want to talk to all 100, others to only one). Each senator has n slots open in his schedule for these meetings.

What’s the best way to schedule the senator-journalist meetings so that the greatest number of meeting requests are fulfilled?

I’m looking for some kind of an algorithm or process that’s conducive to automation.

So far my best idea is to start scheduling the journalists with the greatest number of requests first, and then use the less demanding journalists to fill in the remaining gaps. But that seems to simple. I’m guessing there’s research and/or papers about this problem floating around, but I can’t find them.

Thanks for your help. And no, this isn’t a homework problem.

2

Model it as a graph, with a vertex for each journalist and each senatorial availability. An edge (j, s[sub]i[/sub]) exists for 1 < n iff journalist j wants to interview with senator s.

In this case, we’re trying to find a subgraph that contains exactly one edge from a journalist to a senator’s availabilities for each senator the journalist wishes to interview.

I’m not sure where to go from here, but I’ll think about it some more. My intuition is that you’re going to have to stick with heuristics, but that’s not easy to show.

3

This appears to be an integer linear programming problem, for which there are many computer programs already in existance. I see it as having three dimensions: senator, journalist and time. If senator x meets journalist y at time z then that variable is 1, otherwise it is 0. Then you have to impose constraints, so that a journalist can’t see more than one senator per day, and other similar things. Then you just have to look for a feasible solution, or if you want a particular kind of solution you can look at the one with the highest value of some objective function.

Sadly I’m still one year away from completing my degree, so I don’t know how to solve this by hand (or by calculator). However there are a bunch of computer programs around that do this.

4

Pretty standard problem - you want to poke around under “bipartite matching”.

5

Im also assuming that you model it like ultrafilter suggests - nodes for journalist and senator availabilities. If you do that, I think you’re just looking for a maximal matching, and there are well known algorithms (which I can’t describe off the top of my head).

6

If you do it as a bipartite matching, I think you’ll end up with each journalist only interviewing one senator, which isn’t right. I just did a quick google on the bipartite matching problem, so I could be wrong, but I feel decently confident.

The problem is difficult to define clearly.

7

Note:

Maximal matching is easily solvable in poly time. (In fact, it characterizes a class below P.)

Maximum matching is NP-Complete.

Note that this problem is obviously a generalization of Maximum matching. (Each Senator has only one time slot.) Since the decision version is obviously in NP, this is an NP-Complete problem.

But…

You can still try looking at generalizing techniques for Maximal Matching. You won’t get a global optimum, but at least it’s a local optimum.

8

Well, you could have a node for each journalist / senator request, as well as each senator availability. Then I think it’s a simple matching problem. The lines of the graph would join journalist A requesting senator 1 to all available slots for senator 1, journalist A requesting senator 2 to all available slots for senator 2, etc.

9

Duh. Sorry about that - that doesn’t assure that a given journalist gets different senators at distinct times.

I know that back when I was a grad assistant, we used some variant of the standard matching algorithms from the literature to assign grad assistants to requested classes, which had sections occurring at given scheduled times. Obviously a similar problem, and I just can’t remember how we modeled it. It was a LONG time ago.

10

Mister V says:

What’s the best way to schedule the senator-journalist meetings so that the greatest number of meeting requests are fulfilled?

So I am assuming you give no preference to journalists relative to their number of meeting requests (or any other conceivable preference). All you want to do is assure the maximum number of meeting requests are fulfilled. I am also assuming each journalist will meet with one, and only one, senator per time-slot and there are no requirements for multiple senators to meet with a single journalist at any time.

Here’s a tedious, but programmable, way to do it:

Let me start by making my own definitions for X and Y. X is the senator’s name and Y is a time-slot. I am making the assumption all time-slots are equal in length, let’s say for clarity, all time-slots are one hour beginning on the hour.

This way you can define a 2-dimensional array (matrix) with the senators names on the X-axis and the time-slots on the Y-axis. For programming purposes, assign each senator a number. Fill in the matrix with zeros where the senator/time-slot is available, -1 where the senator/time-slot is not available to any journalist.

Next, define a matrix for EACH journalist, with senator’s number on the X-axis and time-slot on the Y-axis. Each senator/ time-slot in this case will contain the name of the journalist for each time-slot this journalist requests for each senator, or a zero if no senator/time-slot is requested (for programming purposes, assign each journalist a number).

Now “overlay” each journalist’s matrix onto the senators matrix, one at a time. If the corresponding senator/time-slot is available, assign the current journalist to that time-slot. Do this for all of the senators/time-slots requested by this journalist. Then overlay the next journalist’s matrix on the modified senators/time-slot matrix, assigning this journalist senators/time-slots he has requested that are available.

Keep track of the number of time slots filled. Once you have applied ALL of the journalist’s matrices to the senator’s matrix, permute the order in which you apply the journalist’s matrices and then do the procedure over again. After doing this procedure for every permutation of journalists, choose the permutation that filled the largest number of slots in the senators matrix.

I hope this all makes sense. :dubious:

11

One thing I assumed in my solution was that journalists would “fix” the time-slot they wanted. Now if the real problem is journalist-34 wants to talk to senator-76, and journalist-34 is flexible about which time-slot that is, then the algorithm needs to be modified. But my general approach should still work.

So, assuming each journalist gets one, and only one, time-slot with each senator they want to interview. Also, if a journalist wants a time-slot with a senator, they must take ANY time-slot available for that senator.

In this case, when you create the journalist’s matrix, put the journalist’s number in EVERY time-slot associated with EACH senator the journalist wants to interview. When you overlay this journalist’s matrix onto the senator matrix, as soon as an open slot is found to satisfy the journalist’s request, that slot can be taken by this journalist, then move on to the next senator for this journalist. Each time this journalist secures a time-slot, make sure you erase all his other possible meetings for this time slot in his matrix (clear that time-slot row in his matrix).

Now if a journalist is picky and only wants to talk to a senator if the senator can be available for certain time-slots, then instead of initializing the journalist’s matrix with the journalist’s number in EVERY time-slot for that senator, only put the journalist’s number in the time-slots he is willing to accept.

All the other mumbo-jumbo remains the same as in the original solution.

12

To make this algorithm “fair” for each journalist, some modifications would have to be made. The easiest thing to do would be: along with the maximum number of slots-filled per permutation of journalists, keep track of the number of distinct journalists allowed at least one time-slot. That way, when the algorithm presents a “tie” as to the ultimate permutation of journalist’s matrices, the tie-breaker could be the permutation with the maximum number of journalists getting at least one time-slot.

Now, if you have a bunch of “hog” journalists that fill in their time-slot matrix wanting to talk to many senators at any time-slot, my algorithm will favor these hogs. To get around this problem, after the first open time-slot is assigned to a particular journalist, remember where you were in his senator list and put him at the end of the journalist list to be processed after all the other journalists have had a chance to fill at least one time-slot. This way you will be filtering through the current journalist matrix permutation with a bias towards “fairness”.

13

Thank you for all your replies.

I think I’ll take a crack at ccwaterback’s method: one thing that I forgot to mention is that I need to be able to give certain journalists priority over the others; based on, let’s say, the prestige of the organization they work for.

We don’t want the Weekly World News guy bumping the Wall Street Journal guy off the list. :smiley:

14

Sorry if I went a bit overboard in my analysis, but as you can see, I just love problems like this. :slight_smile:

Hmm, giving priority to specific journalists …

I guess one way to do that would be to order your journalists such that the journalists with higher priority have a higher number assigned to them. That way, if a lower numbered journalist has a time-slot assigned to him, he can be bumped by the higher-priority journalist for that time-slot.

Or, just forget about permuting the journalists, run the high-priority ones through the algorithm first, then the lower priority journalists can pick up the crumbs left behind.

There’s all kinds of tweets that can be made to the original algorithm.

Have fun!!!

15

Ignoring purely mathematical concerns, there’s something to be said for giving extra priority to journalists who only want to meet with a small number of senators. The problem can also be cast as maximizing the proportion of each journalist’s requests that are fulfilled.

16

Unfortunately I’m weak on graph theory, but as a purely computational matter, I’d approach it using dynamic programming. At the moment I couldn’t guess the dimensionality of the problem, but you can use dynamic programming techniques combined with heuristics to improve the quality of the solutions you discover during a fixed time limit.

Could you define your preference function a little more clearly? If I had to take a stab at it, I’d guess that you would prefer a solution with the greatest sum of “respectability points” where a meeting’s respectability points depend only on the respectability of the journalist (and not on the particular senators or number of senators involved). I’d expect that a real scheduling application would need to consider an aspect of fairness.

[note that I possess little knowledge of graph theory or linear programming, but I suspect that dynamic programming will allow you to better adjust your algorithm if you discover different requirements, of course I would select a polytime graph-theoretic solution rather than an exponential time dynamic programming solution, but if the optimization problem is NP-complete, then you’ll need to concentrate on finding an adequate solution quickly (rather than the optimal solution)]

17

Not having much math knowledge, I decided on the following approach. It actually works astonishingly well (astonishing to me, anyway).

In my tests using old and randomized request data, it only drops a request due to a scheduling conflict (as opposed to a lack of available time slots) about .01% of the time.

Here’s the method I used:

  1. Sort the journalists’ requests by the number of senators they wish to talk to. Process the most demanding journalists first.
  2. For each journalist, sort their conference requests by the number of available time slots the requested senator has. Schedule the requests for the senators with the least amount of available slots first. If given a choice of time slots, schedule in the earliest one available.

Anyone see a potential problem with that method? I can’t find any, but it’s so simple I can’t believe that it actually works as well as it does.

18

  1. Sounds good. Worst case scenario, all journalists want to talk to all senators: Your algorithm would basically generate “wrap-around diagonals” for each journalist in the matrix of all senator time-slots. This is good, and coincidentally it’s also optimal.

  2. This way you are applying a bias towards senators with the least number of time-slots available. This is good because journalists will fill the time slots of the “hardest to get” senators first. You may want to apply your “journalist hierarchy” bias somewhere along the line of processing too. That is, if two or more journalists want to talk to the same senator, the journalist with higher-priority gets a time-slot.

Whether your total solution is optimal, I really don’t know. But if you run many test scenarios and you can’t find any problems with the outcome, then you have at least found a practical solution that suits your needs. :slight_smile:

19

I see a potential problem with your algorithm. Suppose that we only have two journalists, Alice and Bob. Alice only wants to meet with Senator Daschle, whereas Bob wants to meet with Senator Daschle and 49 others. If all other senators are sufficiently available and Senator Daschle has only one open time slot, then Bob will have all 50 of his requests filled, whereas Alice will have her one request denied.

Granted, that is an extreme case, but it illustrates a potential shortcoming of your method. Try ranking the journalists by the product of their institution’s prestige and the number of senators they don’t want to see. You’ll have to make up a numerical measure of prestige (higher is better), but that shouldn’t be too hard.