Project scheduling GA: efficient data structure for the chromosome
<p>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.</p>

<p>I am writing a <strong>Project Scheduling Optimization</strong> library, a special kind of a <em>Job Shop scheduling</em> problem. To keep it simple, so far my algorithm will only work with <strong>workers</strong> 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:</p>

<p>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)</p>

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

<p>To start with, I created a simple <strong>timetable</strong> consisting of only 4 projects and 4 workers.</p>

<p><strong>PROJECTS:</strong></p>

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

<p><strong>WORKERS</strong>:</p>

<ul>
<li>W1; <strong>efficiency</strong>: 10h/day; <strong>available</strong> for projects: P1, P2, P3, P4</li>
<li>W2; <strong>efficiency</strong>: 5h/day; <strong>available</strong> for projects: P1, P3</li>
<li>W3; <strong>efficiency</strong>: 8h/day; <strong>available</strong> for projects: P1, P4</li>
<li>W4; <strong>efficiency</strong>: 6h/day; <strong>available</strong> for projects: P2, P4</li>
</ul>

<p>With a problem being setup like this, I found a single <strong>chromosome</strong> (single schedule) should represent which worker works on which project for every single hour until the last project is finished. </p>

<p>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 <strong>each slot</strong> there should be a <strong>worker with the assigned project</strong> for that hour slot.</p>

<p>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? </p>