I have a workshop problem with n jobs and m machines, that is, not all jobs need to go through all machines.

Here is an example of a solution to a job shop problem:

The matrix defines 3 tasks x 4 machines, the values being the processing times. The order of the tasks matters, the problem is 3! = 6 possible solutions, which are the permutations of 3 jobs.

But I'm just trying to calculate the makespan of each solution. The third job, for example, has a processing time of 0 on machine 1. This means not only that there is no precedence constraint for J3 x M2, but that it will not respect the constraint of priority.

Each machine can never be inactive at any time, unless forced because of priority constraints.

Thus, Job1 x Machine 1 is executed for 10 units, then Job2 x Machine 1 for 15 years, and so on, which gives the shortest duration for this solution 10 + 15 + 15 + 20.

I'm trying to think of an algorithm that takes the matrix as input and generates the minimum amount of time required for that specific matrix.

A matrix means that the highest tasks always have priority, unless a task has 0 processing times for a specific machine and the next machine is available. As in the example where Job 3 is run at the same time as Job 1 because it does not have to wait for it because machine 2 is available.