11. JOB-SHOP PROBLEM
Dalam masalah job-shop, kita berasumsi bahwa setiap job punya operasi m yang berbeda. Jika beberapa job memiliki kurang dari m operasi, diperlukan jumlah operasi dummy dengan asumsi process time nol. Dengan asumsi ini, kondisi dengan jumlah operasi sama untuk semua pekerjaan bisa terjamin. Dalam job-shop scheduling problem, urutan proses dari job tidaklah sama. Oleh karena itu, aliran dari setiap job pada penjadwalan job-shop tidak undirectional.

Fungsi kompleksitas waktu dari masalah job shop adalah kombinasi yang alami. Oleh karena itu, pendekatan heuristik menjadi populer di topik ini. Tidak seperti model flow shop, tidak ada mesin yang hanya melakukan operasi pertama dari job atau ada mesin yang melakukan hanya operasi terakhir dari pekerjaan. 
Dalam flow shop, jumlah operasi dalam urutan operasi suatu job mungkin sama dengan nomor posisi dari mesin yang dibutuhkan. Maka, tidak ada kebutuhan untuk membedakan antara mereka. Namun, dalam kasus job shop, job yang berbeda akan memiliki urutan operasi yang berbeda. Jadi, kita tidak bisa mengasumsikan aliran lurus untuk masalah job shop. Setiap j operasi di urutan operasi pekerjaan i dalam masalah job shop akan dijelaskan dengan triplet (i, j, k) di mana k adalah mesin yang dibutuhkan untuk memproses operasi jth dari job ith.
Perhatikan data penjadwalan job shop berikut yang melibatkan empat pekerjaan, tiga operasi dan karenanya tiga mesin. Tabel pertama terdiri dari operation processing time dan tabel kedua terdiri dari operasi (proses) urutan job. Himpunan mesin yang dibutuhkan untuk pekerjaan yang diberikan merupakan sebuah rute. Misalnya, pekerjaan 4 memiliki routing 1-3-2.