0
$\begingroup$

Given the following constraints:

  • Fixed set of jobs
  • Each job has a fixed start and end time
    • in the example, for r1 it's [0,3], [4,5] and [8,10]
  • Each job can be run in any resource
    • meaning you can mirror the jobs along the horizontal axis and they would still be valid
  • No overlap for two jobs on same resource

    |0|1|2|3|4|5|6|7|8|9|10
r1:  <|=|=|> <|>     <|=|>
r2:    <|>   <|=|>
r3:    <|=|=|=|=|=|=|=|=|>

I'm looking for the following:

  • Algorithms that minimize the makespan, assuming you can reassign jobs to resources
  • Algorithms that can answer if (eg) is it still possible to accept a new job [a,b]? In the previous example, the job [6,10] should be possible if we move job [8,10] to r2 we will have space for [6,10]:

    |0|1|2|3|4|5|6|7|8|9|10
r1:  <|=|=|> <|> <|=new=|>    
r2:    <|>   <|=|>   <|=|>
r3:    <|=|=|=|=|=|=|=|=|>
$\endgroup$

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.