9. JOHNSON’S PROBLEM

9. JOHNSON’S PROBLEM

Seperti yang sudah disebut-sebut di bab-bab sebelumnya, fungsi kompleksitas waktu untuk problem  flow shop pada umumnya adalah masalah eksponensial. Ini artinya, fungsi grow secara eksponensial terhadap jumlah/ukuran problem. Tapi, untuk masalah dengan 2 mesin dan n job, Johnson telah mengembangkan algoritma polinomial untuk mendapatkan solusi yang optimal, yaitu, dalam waktu tertentu, seseorang bisa mendapatkan solusi yang optimal.
Coba pikirkan masalah flow shop berikut :

Di tabel di atas, tij merupakan processing time dari job i pada mesin j.