0
$\begingroup$

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.)

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Vince May 16 at 8:33
  • $\begingroup$ 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 $\endgroup$ – mohammad mozafari May 16 at 9:26
  • $\begingroup$ I think I remember a polynomial solution exists for only 1 or 2 machines (to be check). Any idea of the size of $n$ ? $\endgroup$ – Vince May 16 at 9:46

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.