JSP

單車間調度問題（Job-shop scheduling problem, JSP）是最基本、最著名的調度問題，也是NP難問題，無最優解精確演演算法。一般類型的JSP問題可表達為：n個工件在m台機器上加工，每個工件有特定的加工工藝，每個工件加工的順序及每道工序所花時間給定，安排工件在每台機器上工件的加工順序，使得某種指標最優。題設為：

不同工件的工序之間無順序約束；

工序開始則不能間斷，每個機器在同一時刻只能加工一個工序；

機器不發生故障。

調度的目標就是確定每個機器上工序的加工順序和每個工序的開工時間，使最大完工時間（makespan）最小或其他指標達到最優。JSP調度問題簡明表示為n/m/G/ 。