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
    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$ Aug 12, 2021 at 16:53


Your Answer

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

Browse other questions tagged or ask your own question.