0
$\begingroup$

Problem

I stumbled over the following job scheduling problem.

  • There are two resources, for simplicity I call them ...
    • CPU_RAM (MAX_CPU_RAM specifies what is available in total)
    • GPU_RAM (MAX_GPU_RAM specifies what is available in total)
  • Each job has ...
    • CPU_RAM requirements
    • GPU_RAM requirements
    • a duration, that is the time needed for execution
    • an earliest start time, i.e. it cannot be executed before that
    • is known "offline". There are changes (addition/removal, resource usage change) but they are infrequent.

For example, Job A needs 20MB GPU_RAM, 100MB CPU_RAM and 5 minutes to execute. It cannot be started before 9:00. There are other jobs that have different requirements.

Goal

Given the constraints above I want to find a schedule with the earliest completion time.

I don't need a perfect solution as I doubt it would be feasible. Since there will be roughly 50 jobs, yet up to 200 jobs should be possible. Instead I am interested in a solution that works in practice.

Execution time should be less than 10 seconds to be feasible. Yes the domain I am working in is not actually scheduling jobs on a PC. But scheduling jobs on a PC is easier to describe, than what I am doing.

First Heuristic

The heuristic I am using atm. is quite primitive.

  1. I sort the jobs by their earliest start time.
  2. Then I pick the one that can start earliest and add it to the schedule.
  3. Taking the reduced resources into consideration the possible start times of the remaining jobs are updated.
  4. The job with the earliest possible start time is added. On a tie I take the job that uses most of the RAM for both CPU/GPU.

The problem with that approach is that jobs using less RAM are preferred since they fit easier and thus tend to have lower earliest possible start times. So I am thinking of making the heuristic more like bin packing, by doing first-fit decreasing.

Research

After the heuristic I looked into The Algorithm Design Manual, if anything there might be of help.

I think pin packing algorithms with 3D boxes might apply. The constraint though would be that each box needs to have a specific alignment. Then one dimension could represent CPU_RAM, the other GPU_RAM and finally one time. Missing in that case would be the earliest start time, which I would have to consider myself when deciding which box can be added next. Moreover the bin would have to be "open" in one dimension (time).

My google search was not that fruitful though, finding an algorithm that has a specific alignment for the boxes.

Hints/Advice/Feedback

I would be very grateful if you could give me advice of what algorithms, papers, or topics to look into, that can help me fulfil the goal outlined.

$\endgroup$
  • 1
    $\begingroup$ Anyway, one possible approach is to formulate this as an integer linear programming problem: the worst-case complexity will be exponential, but depending on the nature of the the specific problem instance, it might complete fast enough. Maybe. There might well be far better algorithms, though (maybe there's some greedy strategy?). $\endgroup$ – D.W. Sep 29 '16 at 19:51
  • $\begingroup$ Thanks I'll look into it. I kept thinking about it and it might be possible to reduce the problem space by one dimension (just CPU_RAM), since it might dominate the other.But I need to check the figures out first. Unfortunately these figures are offline configurable, so depending on the configuration there might be just one relevant dimension and other times not. $\endgroup$ – mfuchs Sep 29 '16 at 20:26
  • 1
    $\begingroup$ Another approach is to start with a greedy approach (such as your first-fit heuristic), and then tweak it by randomizing its choices, so that each time you run it, it outputs a semi-random choice of schedule. Then, repeat it 1000 times and take the best of those 1000 candidate schedules. See, e.g., eecs.harvard.edu/~michaelm/postscripts/ipl2006.pdf. $\endgroup$ – D.W. Sep 29 '16 at 21:33
  • $\begingroup$ Thank you for the input! The paper you posted and its references are great. My future searches in this field will also rely on better keywords. $\endgroup$ – mfuchs Oct 3 '16 at 19:41

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.