5

I'm trying to automate a task and I lack the right vocabulary to look up the correct algorithm. It really feels like a common problem that has likely been solved many times before.

All I'm looking for is for someone to point me in the right direction or help me with the right search terms to look up a solution / algorithm. If you happen to know of an actuall library (javascript), then even better.

Made-up scenario

Say I have 3 'buckets', Bucket A, Bucket B and Bucket C. Each of these can hold a certain number of 'Balls'.

  • Bucket A: Capacity 10 balls.
  • Bucket B: Capacity 15 balls.
  • Bucket C: Capacity 5 balls.

Now, I also have an inventory of balls and each one can only be put into certain 'buckets'. One ball can only go in Bucket 2, The next ball can go into Bucket 1 OR Bucket 3, and so on.

Now.. I need to determine the best way to place the balls in order to try to fill up each 'bucket' to it's capacity (or as close as possible).

Real scenario

My real reason for this is to schedule people (balls) to visit locations (buckets) for a requested number of hours (capacity of the bucket). However, due to the following reasons all the libraries/algorithms I've found while searching for "scheduling" so far do not work in my scenario.

  • I do not care about start/end times at all, only person -> location
  • My people (balls) all have a strict list of locations they can visit. Each one is unique.
  • Each person is available for an arbitrary number of whole (integer) hours that they can spend at exactly one location. Using someone that's available for 8 hours for only 7 of those hours is OK.
  • Each location (bucket) requests a certain number of hours that I try to fulfill to the best of my ability with any combination of people.

I have ~50 locations and ~100 people. It's not a requirement that I get a perfect solution, but 'pretty close'.

I found schedule.js which looks fantastic, but I've been unable to abuse it to fit my needs.

| improve this question | |
3

If the number of hours each person is available is constant (e.g. it's always 1 hour), then your problem can be modeled as a Network Flow, easily solvable in polynomial time with Ford-Fulkerson's algorithm.

To build your flow network, create two layers of nodes; the first layer represents your balls, the second layer represents your buckets. Add an edge from the source to each ball with capacity 1. Add an edge from each ball to each compatible bucket with capacity 1. Add an edge from each bucket to the sink with capacity corresponding to the bucket capacity. Maximum flow represents optimal assignment.

Otherwise, if the number of hours each person can contribute varies, then the above algorithm does not work due to your constraint that each person can only visit one location. (Network flow would solve the problem, but it might split one person's hours across multiple locations.) In this case you have something that's related to a Knapsack or Bin Packing problem.

If the number of hours each person can contribute is an integer, you can solve it via pseudo-polynomial dynamic programming. Otherwise, you have to either:

  1. Implement a brute-force backtracking algorithm. This will give you an exact solution but will not work if the number of people or locations exceeds 50 or so.
  2. Implement a combinatorial heuristic method, as Doc Brown suggested. Hill Climbing or Simulated Annealing will perform very well for this problem and give you optimal or nearly optimal results very quickly.
| improve this answer | |
  • Each person (ball) has an arbitrary but integer capacity. 50 locations, 100 people which rules out a completely brute force approach. You've given me some good links to read up on. I'll take a look and see how they apply, thanks. – Luggage Jul 10 '14 at 14:42
  • Your links have lead me to the Nurse Scheduling problem which is looking very similar to my problem, also. I think that you've gotten me on the right track, which is all I was asking for. Specifically, "Combinatorial Optimization" is the class of problem I have. While none of the specific problems (traveling saleman, knapsack, etc) are an exact match , they have lead me to the types of techniques I will need. Thanks. – Luggage Jul 10 '14 at 17:13
  • No problem man, glad it was helpful. I would start with just a simple hill climbing algorithm: start with a random assignment and have a function that gives a score based on your constraints and goals. Then just make random changes and keep the changes that improve the score. You'd be surprised how well this simple algorithm works. It's also very easy to change this to a simulated annealing algorithm, though often you'll find that it's not necessary as the hill climbing works well enough. – CaptainCodeman Jul 10 '14 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.