Scheduling/Graph Coloring Problem

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Scheduling/Graph Coloring Problem

Postby mike-l » Fri Aug 03, 2012 4:34 pm UTC

I posted this in math, but haven't got much activity in the last week or so.

I'm working on a real world problem. A colleague is currently doing this task by hand and I want to write an algorithm that will do it for us.

We have m groups that need to be scheduled over k time slots into n activities. Certain activities are not available at specified times (on average 1/3 are not available). I want to maximize the length of time between repeating any activity for a fixed group, and I want activities to be balanced in that no group should do one activity twice more than another activity. Only one group can do each activity at a time, and there are 'preferred' slots for certain activities (eg, activity 1 is best done by group 5 or group 6 in slot 1, group 2 in slot 2, etc), but these preferences are sparse (less than 10% of slot/activity combos)

My two ideas are, so far: Treat it like a scheduling problem where the activities are machines, and have a 'cooldown' machine that is required to work on each job between repetitions of events, with prescheduled maintenance jobs representing unavailable activities.

Treat it as a graph coloring/matching problem where my graph is the bipartite graph with one set of vertices being groups, one set being time slots, and the colors being activities. Then putting in loops on each time slots that are precolored for unavailable activities.

Neither of these quite gets me where I want to be, any thoughts? It doesn't need to be super efficient, as n,m and k are relatively small, but large enough that brute force is not really an option.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

D-503
Posts: 75
Joined: Sun Apr 15, 2012 11:35 pm UTC

Re: Scheduling/Graph Coloring Problem

Postby D-503 » Sat Aug 04, 2012 2:51 am UTC

Check out drools planner, your problem sounds exactly like the kind it was designed for. Here's a url: http://www.jboss.org/drools/drools-planner/
IYI the main developer was on FLOSS recently (where I heard about the software):
http://www.youtube.com/watch?v=sL-URSfYduA

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Scheduling/Graph Coloring Problem

Postby mike-l » Sat Aug 04, 2012 2:24 pm UTC

That looks perfect! Thanks
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 5 guests