# Scheduling N variable-time interdependent tasks across M workers

I have N tasks, each of them requires some time to complete. Time to complete is not the same for all tasks. Each task may depend on a number of other tasks (assume, that no dependency cycles are present). I have M (M is fixed, small and << N) workers that may be used to complete the tasks. I need to find a sequence of tasks, that each worker must complete in order to minimize the total processing time.

How is this problem formalized / modelled? I am not sure, which textbook or paper I should read in order to understand, how one might approach this problem (looking for keywords here).

If there is a need to "peg" some tasks (not all) to certain workers, how is the problem "affected"? That is, does it become significantly harder to solve or reason about?

• You alread know the keyword "scheduling"; that's really the name of the whole field. What have you read about scheduling? Commented Aug 28, 2016 at 11:57
• @Raphael I've examined the variations of "Job Shop Problem" (mostly google/wikipedia trying to get a feel of what I need to read in-depth), but the described problem does not fit into job shop / open-shop / flow-shop scheduling. I am not familiar with this branch of CS, unfortunately, so I am a bit lost here. Commented Aug 29, 2016 at 8:10
• Why don't you think it's Job Shop? You may want to check out the basic building blocks. Commented Aug 29, 2016 at 8:42
• @Raphael Actually, I am not sure, why. Now that I re-read it, "Job Shop" is the general class of problems ("Many variations of the problem exist, including the following: ..., jobs may have constraints, for example a job i needs to finish before job j can be started, ..., jobs and machines have mutual constraints, for example, certain jobs can be scheduled on some machines only, ..."), so, definitely, the problem in my question belongs to this class. Thanks for the link to relevant terminology, too. Commented Aug 29, 2016 at 18:10