CODEWITHSUNDEEP
javaoptimizationschedulinggenetic-algorithmjob-scheduling
Whizzil
Whizzil

Reputation: 1364

Project scheduling GA: efficient data structure for the chromosome

This is a continuation of my previous question that was how to represent a single chromosome, I found a way how, but I have a problem with how to represent this in memory.

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 (later I should be able to add more resources), and there are only 2 types of constraints (later there will be more constraints too) 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 [or even hours] 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, I found a single chromosome (single schedule) should represent which worker works on which project for every single hour until the last project is finished.

In this example, the timetable should go from April, the 20th until July the 1st + 60 days. So that is 130 days in total x 12 hours = 1560 hour slots. In each slot there should be a worker with the assigned project for that hour slot.

What would be the correct data structure to use for the slot (it seems inefficient to allocate new Worker object for every slot?), and that is capable for crossover and mutation?

Upvotes: 0

Views: 192

Answers (1)

maaartinus
maaartinus

Reputation: 46422

You surely don't have to allocate anything, but one array. With your 4 projects and 4 workers, you can pre-allocate all 4*4 combinations and store references to them in your chromosome.

This is doable even with hundreds of projects and workers. You could store their indexes instead and you could even pack them into a longer integer type (with up to two billion projects and workers, a long would do).

However, it's a pretty premature and probably useless optimization as other operations will most probably dominate the running time.

Upvotes: 1

Related Questions