CODEWITHSUNDEEP
javaalgorithmjob-scheduling
PlsWork
PlsWork

Reputation: 2178

Job scheduling with n tasks and m machines

Problem description:

I have n precedence constrained jobs and m independent machines. Each job has a cost c assigned to it (the number of machines required to finish the job in 1 time unit). It takes 1 time unit to finish a job, a job can only be finished if c machines are assigned to it (jobs are atomic, it's not possible to finish half of the job).

So in short, there are n jobs and their precedence constrains, m machines and a deadline d (some number of time units).

My goal:

I want to check if it is possible to assign the jobs to the machines such that all of the jobs are finished within d 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).

Example:

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)<--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)<--Job(2,3)<--Job(1,4)
Job(5,3)<--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 <=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")

My current approach: (second try thanks to @Ole V.V.'s counterexample)

I want to do a backtracking approach (best approach that I can come up with). Currently I have troubles implementing it.

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 m 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 <= d (if the deadline is met).

Example of this approach on the example provided by @Ole V.V. :

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

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

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.

Upvotes: 2

Views: 2427

Answers (3)

Damien Prot
Damien Prot

Reputation: 593

The problem you are looking at is clearly NP-hard, we can do a reduction from the partition problem as follows: Imagine you have a partition problem with integers s1, s2..., sn. The aim is to find a partition of this set into two sets S1 and S2 such that the sum over S1 is equal to the sum over S2.

We can transform this problem to your problem, by defining a job for each integer (whose cost is the value of the integer), and we add an additional job, that has to be done after all the other jobs. We set d=3

We can easily show that there is a solution to the partition problem if and only if there is a solution to your problem, hence your problem is NP-hard.

Upvotes: 1

Anonymous
Anonymous

Reputation: 86399

I believe that your greedy algorithm will not always give you the correct result.

Take:

Job 1 costs 3
Job 2 costs 3
Job 3 costs 1
Job 4 costs 5
Job 5 costs 1

Number of machines is 7.

Precedences are 

#1 before #5
#2 before #5
#4 before #3 before #5

Deadline is 3.

I believe your algorithm will choose

Step 1 jobs 1, 2, total cost 6
Step 2 job 4 cost 5
Step 3 job 3 cost 1

Now job 5 has not been run and the deadline is reached. Your program will says this is impossible.

The following schedule is possible

Step 1 job 4 cost 5
Step 2 jobs 1, 2, 3 total cost 7
Step 3 job 5 cost 1

Upvotes: 1

CaptainTrunky
CaptainTrunky

Reputation: 1707

Your approach seems to be fine, but I believe that there is a simpler way. I would suggest you using constraint saisfaction approach. There are quite a few ways of formulating your problem, e.g. mixed-integer programming, MaxSAT. Your task seems to be rather simple and you're sure that there won't be any large numbers, so you can try Minizinc. For example, consider this scheduling example.

If we are talking about Java-specific tools, look at Choco solver.

Upvotes: 0

Related Questions