I have a single resource that will need to shared for running multiple parallel jobs. Think of the resource as a straight line numbered from 1 to 100. The jobs occupy part of the line while they are running. Each job has a start and end unit associated with it and it can only be run between those ranges.
For example lets say we have 3 jobs waiting to run –
- JOB-A is defined to run between 30 (start) to 70(end) units on the line
- JOB-B between 40 to 90
- JOB-C between 10 to 20 etc
We can run as many parallel jobs as we want but none of them should overlap with the other one thats running. So in this case we can only run either JOB-A and JOB-C or JOB-B and JOB-C at the same time as JOB-A and JOB-B overlap each other in their range.
The time taken by the job to finish running is based on its length. For example JOB-A runs for 40 seconds (70 minus 30). Once a job is done, it is removed and we get free space that we can allocate to other newer jobs.
So in the above example, if we were to pick JOB-A and JOB-C to run in parallel, we have to wait 40 seconds for JOB-A to complete before we can run JOB-B (since JOB-B’s range overlaps with JOB-A). We cannot break up the jobs into pieces.
Is there an algorithm that fits this problem? What do you think would be a good way to approach this?