I am trying to solve a preemptive multi-core scheduling problem, where the input is the tasks. The number of cores M can be decided after seeing the input tasks. I need to output the minimal M such that the run time is as long as the maximal task length.

I feel this is related to bin packing with fragmentation, but fragmentation does not require linear constraints.

I doubt I am the first to study this problem but have been unable to find a name for this problem. Does it have a name?

  • 1
    $\begingroup$ The name of this kind of problems is "work-stealing scheduling". You can find thousands of papers on Google using this keyword $\endgroup$
    – Lamine
    Commented Aug 12, 2021 at 15:47
  • $\begingroup$ That has dynamically spawns threads for a fixed number of cores. In my problem, the cores is the unknown. $\endgroup$ Commented Aug 12, 2021 at 16:53


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.