CODEWITHSUNDEEP
javaoptimizationschedulinggenetic-algorithmtimetable
Whizzil
Whizzil

Reputation: 1364

Project scheduling basic example: chromosome for the Genetic Algorithm

I am writing a Project Scheduling Optimization library, a special kind of a Job Shop scheduling problem. To keep it simple, so far my algorithm will only work with workers being the only resource for the project, and there are only 2 types of constraints so far:

1) Every worker has a constraint on what projects he can work on. Only some workers are skilled to work on the same project (for example: W1, W3, W7 worker can work on project P2; W2, W3, W5 can work on project P3; etc), but same worker can be skilled to work on multiple projects, and is allowed to work on multiple projects at different times (for example: W1 works on P1 5 days in a row, then he switches to P2 for 4 days, then he comes back to P1, etc)

2) Every worker has a constraint on how many hours he can work each day -- this should represent a worker's efficiency

To start with, I created a simple timetable consisting of only 4 projects and 4 workers.

PROJECTS:

WORKERS:

With a problem being setup like this, how should a chromosome for the Genetic Algorithm look like, in other words - how to convert this data into a GA chromosome that a GA will know how to work with (calculate the numerical fitness upon it)? An example in Java would be perfect.

Upvotes: 1

Views: 686

Answers (2)

maaartinus
maaartinus

Reputation: 46422

The direct solution like in the flup's answer will most probably lead to mutations producing hardly any valid schedule. And crossover will work even worse.

The problem is that it's too easy to do something wrong. From an optimally scheduled worker there's a single step to over-schedule them. As the optimum typically is a vertex of some n-dimensional polyhedron, it borders on invalid states.

So I'd suggest some indirect representation with chromosome parts like like "assign W2 to P3 if possible". For every hour of your schedule you go through the chromosome parts and apply its rule if possible.

This can be rather trivially optimized so that you don't really have to deal with every hour (the outcome for the next hour is usually the same).

Actually, the problem as stated above can most probably be solved exactly by observing that there are only a few relevant time points, namely the starts and deadlines of projects. Between them, all hours are equivalent in the following sense: When you swap the schedule for the 1st of May and the schedule for the 2nd of May, you'll get exactly the same outcome. Using this equivalence, the problem can probably be sort of brute-forced.

Upvotes: 1

flup
flup

Reputation: 27104

I think I'd take the workers and the projects they work on on each day. So for each day scheduled, write down for each worker what project they'll be working on.

Then you can compute the fitness as the percentage of work finished before the deadline on each project given that allocation.

Mutation can change a worker's allocation to a different project on a certain day. Crossing over can swap a worker's allocation for one or more days with a different genome or it might be more effective to swap the complete allocation of all workers for one or more days with that of a different chromosome

Upvotes: 1

Related Questions