I have a job shop problem with n jobs and m machines, a job shop means that not all jobs have to go through every machine.
A job shop problem can be written as such :
[[15,0,15,16], [10,30,20,0], [0,15,5,10]]
This would be an example of a 3 job, 4 machine problem. The matrix is 3x4, with each value being the processing time of each job on the corresponding machine.
A solution can be written as :
[1,0,2]. Which is the ordering of these 3 jobs. For the sake of self-containing the problem, a solution can also be written as :
[[10,30,20,0], [15,0,15,16], [0,15,5,10]]
Which is a re-ordering of the problem matrix according to the order of jobs in the solution.
Precedency constraint : All operations for a single job run from lowest machine index to the highest. If a job has an operation on machine k, k+1 can not be processed.
Question : I need help making an algorithm that takes the above solution as input, and outputs its makespan. The makespan is the time required for all jobs to be processed according to a given order.
Here's an example of the solution above represented kn a gantt chart :
Making the makespan 10 + 15 + 15 + 20 = 60 units of time for all jobs to be processed.