15. TWO JOBS AND M MACHINES SCHEDULING

15. TWO JOBS AND M MACHINES SCHEDULING

Dua job dan M jadwal mesin, adalah masalah spesial di penjadwalan job shop. Masalahnya terdiri dari 2 job, yang membutuhkan pengolahan pada mesin M. Urutan pemrosesan dari job tidak sama. Karena, ini adalah jenis khusus bawah penjadwalan job shop seperti, masalah Johnson (n pekerjaan dan 2 mesin) di bawah penjadwalan flow shop, kami memiliki prosedur grafis untuk mendapatkan jadwal yang optimum.
Prosedur grafis terdiri dari langkah-langkah berikut:
Langkah 1 : Buatlah sebuah grafik dua dimensi dimana sumbu x mewakili job 1, urutan operasi-nya dan processing times-nya, dan sumbu y mewakili job 2, urutan operasi-nya dan processing times-nya (gunakan skala yang sama untuk kedua sumbu x dan y).
Step 2: Shade each region where a machine would be occupied by the two jobs simultaneously.
Langkah 2 : Gambar bayangan/arsiran setiap daerah di mana mesin akan ditempati oleh dua pekerjaan secara bersamaan.
Langkah 3 : Pengolahan kedua job ditunjukkan oleh garis kontinu yang terdiri dari garis datar, tegak dan diagonal 45 derajat . Garis ditarik dari asal dan terus ke sudut kanan atas dengan menghindari daerah arsiran. Sebuah garis diagonal berarti bahwa kedua job dapat dilakukan secara bersamaan. Jadi, sementara menggambar garis dari asal ke sudut kanan atas, kita harus mencoba untuk memaksimalkan panjang perjalanan diagonal (jumlah dari panjang garis 45 derajat), yang akan meminimalkan makespan masalah.
Dengan menggunakan metode trial and error, seseorang dapat menarik garis akhir, yang memiliki bagian diagonal maksimum. Konsep ini diperagakan dengan menggunakan problem numerik.

ILUSTRASI 8 : Gunakan metode grafik untuk meminimalkan waktu yang dibutuhkan untuk memproses job berikut pada mesin yang ditunjukkan (yaitu untuk setiap mesin, temukan job yang harus dijadwalkan pertama kali). Juga, hitung total waktu berlalu untuk menyelesaikan kedua job.

SOLUSI: Sesuai pernyataan prosedur, data di atas disajikan dalam bentuk grafik seperti yang ditunjukkan pada Fig. 10.4. Garis dari titik asal ke sudut kanan atas menunjukkan rincian pengolahan dan makespan. Makespan (waktu yang terpakai untuk menyelesaikan kedua job itu) adalah 22 jam. Waktu awal dan akhir penyelesaian untuk kedua job diberikan dalam Tabel 10.2.

Dengan gambar dan tabel dengan mudah dapat diamati bahwa total idle untuk job1 adalah 5 jam (2 +3). Maka total waktu menyelesaikan job 1 adalah jumlah dari processing time ditambah waktu idle-nya, yaitu 17 jam + 5 jam = 22 jam.Untuk job 2, tidak ada waktu idle. Maka total waktu yang dibutuhkan untuk menyelesaikan job 2 adalah jumlah dari processing times, yaitu 20 jam.
Makespan adalah maksimal dua kuantitas.
Oleh karena itu, Max (22,20) = 22 jam.

14. PRIORITY DISPATCHING RULES

14. PRIORITY DISPATCHING RULES

Dalam prosedur lengkap enumeration (pencacahan) atau prosedur bercabang dan terikat, jumlah schedule yang dihasilkan sebelum mencapai jadwal yang optimal akan sangat banyak. Namun, tujuan prosedur heuristik pada dasarnya hanya menghasilkan satu jadwal penuh.

Setiap kali, ada sebuah hubungan (konflik) dalam menyeleksi operasi dari antara operasi yang berlawanan, kita harus menggunakan aturan prioritas. Jika ada hubungan pada tingkat yang berbeda, maka kita perlu lebih dari satu aturan prioritas untuk memecahkan keruwetan yang kusut. Untuk R prioritas aturan, satu heuristik didasarkan pada pembentukan jadwal aktif diberikan di bawah ini:
Heuristic Active Schedule Generation 
Langkah 1 :  t = 0 dan assumsikan Pt = {φ}.
St = {Semua operasi tanpa proses pendahuluan/predecessor}.
Langkah 2 : Tentukan q* = min {qj} dan
                     mesin terkait m* yang q* direalisaikan.
                     j E S.

Langkah 3 :Setiap operasi kepunyaan S, yang membutuhkan mesin * m dan memenuhi kondisi Pj <q *, menjadi identifikasi bagi operasi dengan prioritas tertentu dan tambahkan operasi ini ke PI sedini mungkin, sehingga menciptakan hanya satu jadwal parsial, PI + 1 untuk tahap berikutnya.

Langkah 4 : Setiap jadwal parsial PI yang baru + 1 yang dibuat pada Langkah 3, update set data sbb :
(a) Hapus j operasi dari SI.
(b) Bentuklah SI + I dengan menambahkan successor/penerus langsung j operasi untuk SI.
(c) Increment t tiap satu.
Langkah 5 : Ulangi Langkah 2 ke Langkah 4 untuk setiap PI + 1 yang dibuat pada Langkah 3 dan lanjutkan dengan cara ini sampai semua jadwal aktif bisa dihasilkan.

Demikian pula, heuristik lainnya dapat dibuat dari algoritma pembuatan non-delay schedule dengan mengganti kondisi Pj <q * dengan Pj = p * pada Langkah 3. Dua algoritma heuristik ini (active dispatching dan non-delay dispatching) dapat membangun jadwal yang berbeda. Kualitas dari solusi yang diperoleh oleh heuristik ini terutama tergantung pada efektivitas aturan prioritas yang digunakan di dalamnya.

Contoh set aturan prioritas disajikan di bawah ini:
(a) SPT, shortest processing time (waktu pemrosesan terpendek) :
     Pilih operasi dengan processing time yang minimum.
(b) FCFS, first come first served (pertama datang pertama dilayani) :
     Pilih operasi yang masuk SI paling awal.
(c) MWKR, most work remaining (pekerjaan yang paling tersisa) :
     Pilih operasi dengan job dengan pekerjaan yang paling banyak tersisa untuk diproses.

(d) MOPNR, most operations remaining (operasi yang paling tersisa) :
     Pilih operasi yang memiliki jumlah operasi successor/penerus terbesar.
(e) LWKR, least work remaining (pekerjaan paling yang tersisa) :
     Pilih operasi dengan job dengan pekerjaan yang paling sedikit tersisa untuk diproses.
(f) RANDOM (Acak) :
    Pilih operasi secara acak.

13. HEURISTIC PROCEDURES

13. HEURISTIC PROCEDURES

Karena, masalah job shop datang di bawah kategori kombinatorial, waktu yang dibutuhkan untuk memperoleh solusi optimal akan menjadi natural eksponensial. Dalam jenis masalah ini, jumlah jadwal feasibel akan tumbuh secara eksponensial, bahkan untuk kenaikan kecil dalam ukuran masalah. Sebagai hasilnya, maka akan mustahil untuk memecahkan masalah ukuran besar secara optimal. Oleh karena itu, kita harus mengusahakan pendekatan heuristik untuk mendekati solusi optimal .

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.

12. TYPES OF SCHEDULES

12. TYPES OF SCHEDULES 
Secara umum, feasible schedule dengan jumlah tak terbatas adalah mungkin untuk problem job shop, karena seseorang dapat memasukkan jumlah berapa saja idle time pada setiap mesin di antara operasi yang berpasangan. Idle time tidak berguna apapun. Bahkan, ini akan menyebabkan solusi non-optimal pada saat meminimalkan makespan.
Dalam Gantt chart ditunjukkan pada gambar, orang harus mencoba memindahkan blok berbagai operasi ke kiri sebanyak mungkin pada setiap mesin. Hal ini membantu kita membuat jadwal yang kompak, yang biasanyanya terkenal bisa meminimalkan ukuran makespan.

Mengatur waktu mulai beberapa operasi ke arah kiri tanpa mempengaruhi urutan operasi akan meminimalkan idle time yang tidak diinginkan. Mengatur waktu mulai dari beberapa operasi dengan cara ini adalah sama dengan memindahkan blok operasi di sebelah kiri dari bagan Gantt sambil menjaga urutan operasi.

Jenis penyesuaian ini disebut local-left -shift, atau limited-left-shift. Mengingat urutan operasi untuk setiap mesin, hanya ada satu schedule di mana tidak ada local-left -shift yang dapat dibuat. Himpunan semua jadwal di mana tidak ada local-left -shift yang dapat dibuat disebut set jadwal semi-aktif dan setara dengan himpunan semua jadwal yang tidak mengandung satu pun dari idle time yang tidak diinginkan, yang sudah dijelaskan di atas. Setting ini mendominasi set semua jadwal, yang berarti bahwa itu sudah cukup untuk mempertimbangkan hanya jadwal semi-aktif untuk mengoptimalkan tindakan kinerja rutin.

The number of semi-active schedules is finite and is less than the total number of possible schedules. In a semi-active schedule, the start time of a particular operation is constrained either by

Jumlah jadwal semi-aktif yang terbatas dan kurang dari total jumlah jadwal yang memungkinkan. Dalam jadwal semi-aktif, waktu mulai dari operasi tertentu dibatasi juga oleh :

• operasi yang berbeda pada mesin yang sama atau
• memproses operasi langsung pada n mesin yang berbeda. Dalam kasus yang pertama, di mana pengerjaan operasi sebelumnya pada suatu mesin dibatasi, masih mungkin menemukan cara improvement yang jelas.

Bahkan ketika tidak ada local-shifts yang memungkinkan, jadwal yang lebih baik dapat dengan jelas dibuat dengan menggeser operasi ke kiri dan di luar operasi lain yang sudah dijadwalkan pada beberapa mesin. Adjusment di mana beberapa operasi. dimulai lebih awal tanpa menunda operasi lain disebut global left-shift atau simply a left-shift. Himpunan semua jadwal di mana tidak ada global left-shift yang dapat dibuat disebut set jadwal aktif. Hal ini jelas subset dari himpunan jadwal semi-aktif.
Himpunan jadwal aktif yang mendominasi setting jadwal semi-aktif dalam rangka optimalisasi setiap tindakan kinerja rutin. Jadi itu sudah cukup untuk mempertimbangkan hanya jadwal aktif saja.
Jika mesin tidak dibiarkan idle pada saat dimana bisa mulai memproses beberapa operasi maka disebut jadwal non-delay. Kita dapat mengidentifikasi subset jadwal dari set jadwal aktif yang memuaskan properti, yang dikenal sebagai satu setting jadwal non-delay.

Semua jadwal non-delay adalah jadwal aktif, karena tidak ada left-shift yang mungkin. Tidak ada jaminan bahwa subset non-delay akan berisi suatu yang optimal. Diagram Venn menunjukkan ukuran relatif antara berbagai jenis jadwal ditunjukkan dalam gambar berikut. Fig. 10.3. Akan ada setidaknya satu schedule yang optimal dalam set jadwal aktif.