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 &lt;&lt; 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?
This can been seen as a variation of the job shop problem where you want to find the policy that yields the minimum makespan (time taken for all machines to process all jobs); as well as a variation of the assignment problem (find the optimal pairing of workers to jobs that minimizes cost). The variation in both cases is an added dependency between jobs (Job A must complete before Job C) etc. This collection of combinatorial optimization problems is NP-Hard. Most of what you'd find in the literature is approximation heuristics to find a near optimal policy (sequence of tasks per worker).

This paper is one such approach: "Approximation Algorithms for Multiprocessor Scheduling under Uncertainty" 

A quick way to solve your problem (quick as in prototype a solution, not necessarily runtime, or necessarily near optimal), is to construct a topological sort of your job dependency graph, use breadth first search to batch all jobs of a given height and put that batch on a stack (assumes directed edge represents a depends on relationship, with zero out degree nodes having no dependencies). Afterwards, Until the stack is empty, pop a batch and treat it as a traditional assignment problem and solve using the Hungarian algorithm, then enqueue the tasks to each assigned worker's task queue. Afterwards you'd have a policy. (When you go to execute the policy, you'd have to have some signalling mechanism that a task completed so that workers don't start on a task whose dependencies haven't finished yet.)