# Job scheduling with minimum makespan

You are given n jobs, m workstations and an n × m two-dimensional task matrix T of the time each job will spend at each workstation. Each job becomes available at a specified time and may be processed in only one workstation at a time. Each workstation may process only one job at a time. The goal is to assign a start time for each job at each workstation that minimizes the finish time of the last job.

How can I solve this problem optimally?
(I think we must use dynamic programming.)

• This problem is known as Job shop scheduling (en.wikipedia.org/wiki/Job_shop_scheduling). It is generally NP-complete. Is it a school assignment ? Do you have any further constraint or maybe indication on input size ? – Vince May 16 at 8:33
• Yes, it is a school assignment. The constraints are : There are 3 machines, there is no order for processing jobs in different machines and jobs become available at a certain time (not from beginning) @Vince – mohammad mozafari May 16 at 9:26
• I think I remember a polynomial solution exists for only 1 or 2 machines (to be check). Any idea of the size of $n$ ? – Vince May 16 at 9:46