0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What are you trying to minimise/maximise? If you want to run the maximum total number of jobs, an optimal solution is to always schedule, from among the feasible jobs that remain, the one that ends the soonest. BTW, your use of "parallel" is confusing -- IIUC, you want to choose a subset of jobs that can be run completely serially. $\endgroup$ – j_random_hacker Jun 7 at 13:16
  • $\begingroup$ @j_random_hacker Thanks, that was my thoughts as well about scheduling always. I am trying to maximize the number of jobs that can be run in 'parallel'. The reason is use parallel is that the jobs are running at the same time, they are not being run one after other. For example in the above example JOB-A and JOB-C and run in parallel (the numbers don't indicate 'when' they start, they indicate 'where' on the line they are able to run). So JOB-A is can only be run between 30 and 70 (spatially speaking, not time wise). Sorry if thats confusing, I think I did not say that well in the post. $\endgroup$ – user3312156 Jun 7 at 15:12
  • $\begingroup$ Sorry, I still don't understand. Surely the "number line" is time? E.g. the Job A needs access to The Special Resource from time 30 to time 70? In that case you are serialising access to The Special Resource. $\endgroup$ – j_random_hacker Jun 7 at 17:25
  • $\begingroup$ @j_random_hacker Sorry for the confusion. The line is just a line - its more of a spatial representation, it doesn't indicate time. Kind of like a road - a car (JobA) wants to go from 30 to 70 and keeps a 'hold' of its path until it completes, JobC at the same time can go from 10 to 20 but not between 30 to 70 as its 'on hold' for JobA. Researching a bit, I think interval scheduling algorithm might a good fit for this? Atleast so far thats what I think but would love to know if there is something else that might be a good fit. $\endgroup$ – user3312156 Jun 7 at 20:17
  • $\begingroup$ The algorithm I briefly described is indeed a well-known optimal algorithm for interval scheduling, and can be implemented in $O(n\log n)$ time: Just sort the right endpoints of the intervals, then repeatedly grab the first one whose left endpoint is still in the clear. $\endgroup$ – j_random_hacker Jun 8 at 1:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.