I am trying to find/develop an algorithm that can minimise total time for scheduling jobs (with running times) to machines. I.E the standard multiprocesser scheduling algorithm.
However I have two additional constraints: Some jobs must be completed before others (precedence). Only certain machines can run certain jobs (job exclusions). Jobs are not unique to processers though.
For example I may have 4 jobs such that -
(cost): j1 (4) , j2 (2) , j3 (10), j4 (12)
3 machines: m1, m2, m3
Such that:
m1 can run j1, j2, j3
m2 can run j1, j2 and
m3 can run j3, j4
j1 must be run before j2 and j4
I aim to find the optimal schedule for each machine in order to minimise total time.
I have looked into using an multiprocesser scheduling algorithm for unrelated machines (setting the excluded tasks to infinite cost) but this isn't ideal as the costs aren't actually variable (either infinite or the normal cost).
Using a DAG should work well for the precedence constraint but I can't work out how to include the exclusions.
At the moment I am using a greedy algorithm that maximises the cost of the freed (no longer constrained) jobs in all other processors. However I have no idea if this is optimal or even good.
I am fairly certain this is NP-hard so I don't assume an optimal algorithm exists. It may be that using multiprocesser scheduling is the issue here as it may be better to use knapsacking or minimal path algorithms.
Help with both constraints would be preferred but literature on dealing with excluded jobs is minimal (according to some googling) so advice on just dealing with this would be beneficial.
One way to handle this is as follows.
Introduce a binary variable assign(j,m) to indicate if we assign a job j to machine m. Then just fix all variables assign(j,m)=0 for all combinations that are not allowed. A good MIP solver will remove the corresponding variables from the model in the presolve phase.
When I do this, and complete the MIP formulation and solve it, I see:
---- 63 --------------- data ---
---- 63 SET ok allowed job/machine combinations
machine1 machine2 machine3
job1 YES YES
job2 YES YES
job3 YES YES
job4 YES
---- 63 PARAMETER proctime processing time
job1 4.000, job2 2.000, job3 10.000, job4 12.000
---- 63 SET prec precedence
job2 job4
job1 YES YES
---- 63 --------------- solution -----
---- 63 VARIABLE assign.L assign job to machine
machine1 machine2 machine3
job1 1.000
job2 1.000
job3 1.000
job4 1.000
---- 63 VARIABLE start.L job start time
job2 4.000, job4 4.000
---- 63 VARIABLE finish.L job finish time
job1 4.000, job2 6.000, job3 10.000, job4 16.000
---- 63 VARIABLE makespan.L = 16.000 time last job is finished
(Note that start times of zero are not printed)
The complete model is here.