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.
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.
The heuristic I am using atm. is quite primitive.
- I sort the jobs by their earliest start time.
- Then I pick the one that can start earliest and add it to the schedule.
- Taking the reduced resources into consideration the possible start times of the remaining jobs are updated.
- 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.
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.
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.