1

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:

  • P1; starting: May, the 1st; deadline: 30 days; work hours needed: 300
  • P2; starting: July, the 1st; deadline: 60 days; work hours needed: 150
  • P3; starting: May, the 15th; deadline: 45 days; work hours needed: 50
  • P4; starting: April, the 20th; deadline: 20 days; work hours needed: 150

WORKERS:

  • W1; efficiency: 10h/day; available for projects: P1, P2, P3, P4
  • W2; efficiency: 5h/day; available for projects: P1, P3
  • W3; efficiency: 8h/day; available for projects: P1, P4
  • W4; efficiency: 6h/day; available for projects: P2, P4

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.

Improve this question
1
  • What options do you see? Commented Apr 7, 2016 at 9:29

2 Answers 2

Reset to default
1

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

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

That should be the result of the algorithm, no? I am asking how should a single chromosome look like, so that the result like you described could be computed. The result of the algorithm is joining the resources to the projects, in a granula of time. In this example, for every day.
Yes! So make the chromosome the proposed allocation and compute its fitness.
Yeah well, how? :D I mean, could you show me an example in code? How should a class chromosome look like?
Are you using a specific library for the implementation or coding all of this yourself? Also: Is this homework? :)
I am coding it myself. It is not a homework, it is a college related project, but my example here is really just a basis helping me understand how the things work as a concept. A real assignment is much more complex. :)
1

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.

Improve this answer

5 Comments

how do you mean indirect representation? what would mean "if possible"?
@Whizzil For example, the rule "assign W2 to P3 if possible" would get skipped, if W2 is already done or P3 has exhausted its efficiency. This is what I mean by "indirect": don't do blindly what's prescribed by the chromosome, but try to make sense of it. +++ No idea, if there's something similar in the nature, but there are things like methylation, so there's no blind transcription either.
What worries me is the size of a single chromosome. If overall time of all projects is for example 100 days, every day for 12 hours, that is 100 x 12 = 1200 hour slots. Now in every single slot I should memorize what worker works on what project. Is it OK to allocate for every slot a new object TimeSlot that knows what worker works on what project for this particular slot? That would now be 1200 objects allocated for a single chromosome.
In other words, what is the best way to store resources (workers) for active projects, for every hour slot? It seems like a memory overkill to allocate new Project for every hour slot, and then assign it different resources.
@Whizzil You need no big chromosome, as you don't need to be explicit about every hour. If the workers were your employees, would you assign them tasks on hourly basis or would you tell them what project is the most critical?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.