title: Job scheduling with n tasks and m machines
body: <p><strong>Problem description:</strong></p>
  
  <p>I have <code>n</code> precedence constrained jobs and <code>m</code> independent machines. Each job has a cost <code>c</code> assigned to it (the number of machines required to finish the job in <code>1</code> time unit). It takes <code>1</code> time unit to finish a job, a job can only be finished if <code>c</code> machines are assigned to it (jobs are atomic, it's not possible to finish half of the job).</p>
  
  <p>So in short, there are <code>n</code> jobs and their precedence constrains, <code>m</code> machines and a deadline <code>d</code> (some number of time units).</p>
  
  <p><strong>My goal:</strong> </p>
  
  <p>I want to check if it is possible to assign the jobs to the machines such that all of the jobs are finished within <code>d</code> time units. If this is possible then I want to print out a schedule which assigns a time unit to each job (the time unit in which the job is processed, see example below).</p>
  
  <p><strong>Example:</strong></p>
  
  <pre><code>n = 5; // number of jobs
  m = 6; // number of machines
  d = 4; // deadline (number of time units in which the jobs need to be finished)
  
  Precedences: (read "Job(x,y)&lt;--Job(q,p)" as "job x with cost y needs to be
                finished before job q with cost p can be started")
  Job(3,1)&lt;--Job(2,3)&lt;--Job(1,4)
  Job(5,3)&lt;--Job(4,3)
  Job(6,1)
  
   The solution: in this case it's possible to assign jobs to machines such that each job
  finishes in &lt;=d time units. 
  A possible schedule is 1 2 3 3 4 1.
  
  (read schedule as "job 1 and job 6 are done in the first time unit, job 2
  is done during the second time unit, jobs 3 and 4 during the third time unit, 
  job 5 during the fourth time unit")
  </code></pre>
  
  <p><strong>My current approach: (second try thanks to @Ole V.V.'s counterexample)</strong></p>
  
  <p>I want to do a backtracking approach (best approach that I can come up with). Currently I have troubles implementing it.</p>
  
  <p>I want to store the jobs and their precedences. Then I identify a set A which contains all jobs that can be solved during the current time unit. Then I find a set B (it contains all sets of jobs which I consider solving during this time unit) which contains all subsets of A which are solvable with the limited number of machines <code>m</code> such that no other job can be added to each subset (by adding a job to one of the subsets the cost of all jobs in that subset exceeds 'm'). Then I repeat the procedure but without the solved jobs (A\B), I do a recursive call for every subset in B. I stop when the passed set of leftover jobs (A\B) is empty (all jobs finished), at that point I return the found schedule if the depth of recursion is &lt;= <code>d</code> (if the deadline is met).</p>
  
  <p>Example of this approach on the example provided by @Ole V.V. :</p>
  
  <p><a href="https://i.stack.imgur.com/qDVCv.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/qDVCv.jpg" alt="The steps refer to the depth of recursion, the boxes refer to the jobs (first number is job ID, second is cost in time units. At step 0 I explicitly wrote out the subsets (sets of jobs which I consider solving during this step)."></a></p>
  
  <p>The steps refer to the depth of recursion, the boxes refer to the jobs (first number is job ID, second is cost in time units. At step 0 I explicitly wrote out the subsets (sets of jobs which I consider solving during this step).</p>
  
  <p>Now my problem is storing the jobs and their precedences, finding the jobs which can be solved in the current time unit (set A), finding the subsets of jobs which I consider solving during the current time unit (set B), and putting it all together in a recursive function which in the end outputs the found schedule or "no schedule found" if there is no schedule which meets the deadline.</p>