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 :


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 :


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 :

enter image description here

enter image description here

Making the makespan 10 + 15 + 15 + 20 = 60 units of time for all jobs to be processed.

  • $\begingroup$ I tried to explain it as much as I could. A matrix is in itself a solution through the order of its rows, which represent the jobs. I explained it this way to avoid that exact question, Which one do you want, "the makespan of every solution" or "minimum possible makespan"?. I dont want help with finding minimum makespan, but I want help with finding makespan for any solution. Like I said on my post, it should take a matrix as input, and output the makespan for that solution. $\endgroup$ – Zee Apr 12 at 7:17
  • $\begingroup$ I still reworded my question to remove information that you feel is redundant, thanks for your feedback. $\endgroup$ – Zee Apr 12 at 7:57
  • $\begingroup$ "Making the makespan 10 + 15 + 15 + 20 = 60 units of time for all jobs to be processed". Shouldn't it be "15 /*job 3 on M2*/ + 30 /*job 1 on M2*/ + 20 /*job 1 on M3/ = 65"? $\endgroup$ – Apass.Jack Apr 12 at 22:07
  • $\begingroup$ @Apass.Jack Well caught :) I guess I misrepresented the gantt chart and didn't double check the values. Either way I found a solution to my question now. $\endgroup$ – Zee Apr 13 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.