Job shop scheduling: which solutions should I consider?

Question

Given a software company, where developers work in teams on a number of different projects. Projects require a certain skill from assigned developers. For my purposes, I want to keep it simple and limit this to one skill, i.e. programming language. So some projects require Java, others require C etc. Projects have a fixed duration, and each project should have two developers assigned to it.

At any point in time, some projects are in progress and new projects come in and need to be planned at some point in the future. I want to calculate a schedule of which developers should work on what project and when.

I'm not looking for the optimal solution (if that's even possible). I'm content with a schedule a human manager could create.

I've read articles about Resource Constrained Scheduling Problems and Assignment Problems, but I have very little formal CS training, and I'm often lost in all the nuances in different variations of these problems.

I think my problem is a simpler variation of job shop scheduling where jobs are projects, and developers are machines, so jobs require multiple machines at the same time. There is only one precedent constraint, in that running projects can't be aborted and so must be finished first.

From all the possible solutions I have read about, I'm inclined to use a Genetic Algorithm, mainly because I've read people getting good results with them and because I have used one a while ago for another project. I've also read about good results with Linear Programming, but I know very little about that.

Is a genetic algorithm a feasible solution for this type of problem? Or are there better solutions?

Answer 1

Create a bipartite graph with developers on one side and needed project members on the other. By "needed project members", I mean that if a project P needs 3 developers, you would add 3 nodes, perhaps named P0, P1 and P2.

Draw an edge between a developer and a needed project member if that developer has all the skills required by that project. Your problem then reduces to finding a matching within this graph; there are standard algorithms you could use to do this.

Answer 2

Using a genetic algorithm is a feasible approach, but it is very ambitious.

Start with a greedy algorithm.