1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ You alread know the keyword "scheduling"; that's really the name of the whole field. What have you read about scheduling? $\endgroup$
    – Raphael ♦
    Aug 28, 2016 at 11:57
  • $\begingroup$ @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. $\endgroup$
    – shylent
    Aug 29, 2016 at 8:10
  • $\begingroup$ Why don't you think it's Job Shop? You may want to check out the basic building blocks. $\endgroup$
    – Raphael ♦
    Aug 29, 2016 at 8:42
  • 1
    $\begingroup$ @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. $\endgroup$
    – shylent
    Aug 29, 2016 at 18:10

1 Answer 1

Reset to default
2
$\begingroup$

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.)

Improve this answer
$\endgroup$

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.