8. FLOW SHOP SCHEDULING

8. FLOW SHOP SCHEDULING

Dalam masalah penjadwalan flow shop, ada job n, masing-masing memerlukan pemrosesan pada mesin m yang berbeda. Urutan di mana mesin yang diperlukan untuk memproses pekerjaan disebut process sequence dari job tersebut.

Process sequences dari semua job boleh sama. Tapi waktu proses/processing time untuk berbagai job pada suatu mesin bisa saja berbeda. Jika suatu operasi absen dari job, maka waktu proses dari operasi pekerjaan itu diasumsikan sama dengan nol.

Masalah penjadwalan flow-shop dapat diberikan cirinya sebagai berikut ini :

1. Satu set job multi-operasi yang siap untuk proses pada time zero (Setiap pekerjaan memerlukan m operasi dan setiap operasi memakai mesin yang berbeda).
2. Waktu set-up untuk operasi itu tersendiri, dan masuk dalam waktu proses/processing time.
3. Deskriptor job diketahui di muka.
4. m mesin yang berbeda terus tersedia.
5. Setiap operasi individual dari job diproses sampai selesai tanpa istirahat.

Perbedaan utama penjadwalan flow shop dari basic single machine scheduling adalah bahwa waktu idle disisipkan mungkin menguntungkan dalam penjadwalan flow shop. Meskipun mesin saat ini sedang bebas, jika pekerjaan dari mesin sebelumnya tidak dirilis ke mesin saat ini, kita tidak bisa mulai memproses pekerjaan itu. Jadi, mesin saat ini harus menganggur sekali ini. Oleh karena itu, waktu menganggur yang disisipkan pada beberapa mesin akan menyebabkan optimalitas.

Sebagai contoh, selesaikanlah masalah flow-shop sebagai berikut :

Jika urutan job adalah 2-1-4-3, maka makespan yang sesuai dihitung seperti ditunjukkan pada Fig.10.1. Makespan berikut ini adalah 25. Juga, perhatikan idle time yang disisipkan pada mesin 2 adalah dari 0 sampai 3, 4 sampai 8 dan 12 sampai 15.

Pikirin deh, sekuen lain bilang 3-4-1-2. Gantt chart untuk urutan ini ditunjukkan pada Fig. 10.2. Makespan untuk jadwal pada Fig. 10,2 adalah 26. Mesin 2 memiliki idle time dari 0 sampai 6 dan 8 sampai 13.
Masalah ini memiliki 4 job. Maka, 4! urutan yang mungkin. Tidak seperti di single machine scheduling, dalam penjadwalan flow shop, disisipkannya idle time akan meminimalkan makespan.

Di dua sekuen atas, 2-1-4-3 dan 3-4-1-2, urutan pertama memiliki makespan yang lebih rendah. Seperti ini, seseorang dapat menghitung semua urutan 4!, kemudian pilih urutan dengan makespan minimum sebagai urutan yang optimal. Karena, n! tumbuh secara eksponensial dengan n, kita perlu beberapa prosedur yang efisien untuk memecahkan problem ini. Untuk n yang bernilai besar, akan sulit untuk memecahkan masalah. Dalam situasi seperti ini, kita bisa menggunakan beberapa heuristik yang efisien.