Teknik Relaksasi Lagrange untuk Penjadwalan Pekerjaan Majemuk dengan Penggunaan Sumberdaya Simultan

OLEH : WINDI

ABSTRAK

Makalah ini membahas beberapa pekerjaan penjadwalan masalah dengan sumber daya simultan. Masalahnya melibatkan satu atau lebih pekerjaan dengan setiap pekerjaan terdiri dari satu set operasi. Setiap operasi dilakukan oleh lebih dari satu sumber secara bersamaan. Jumlah unit masing-masing sumber daya yang digunakan untuk melakukan operasi adalah satu atau lebih unit. Masalahnya berkaitan dengan menentukan jadwal operasi meminimalkan total tardiness tertimbang. Dalam tulisan ini, teknik solusi berdasarkan relaksasi Lagrangian diusulkan. Secara umum, teknik relaksasi Lagrangian terdiri dari tiga bagian menjalankan iteratif, yaitu, (1) memecahkan masalah pekerjaan individu, (2) memperoleh solusi yang layak, dan (3) pemecahan masalah ganda Lagrangian. Untuk memecahkan masalah pekerjaan individu, dua pendekatan yang diterapkan, yaitu, pencacahan dan dinamis

Kata kunci: masalah Penjadwalan; Beberapa pekerjaan; Sumber daya simultan; Relaksasi Lagrangian.

ABSTRAC

This paper discusses some job scheduling problem with resource simultaneously. The problem involves one or more work with each job consists of a set of operations. Each operation carried out by more than one source simultaneously . The number of units of each resource that is used to perform surgery is one or more units. The problem relates to determining the operating schedule to minimize total weighted tardiness . In this paper , the technique proposed solution is based on Lagrangian relaxation . In general , Lagrangian relaxation technique consists of three parts run iteratively , namely , ( 1 ) solve the problem of occupation of individuals , ( 2 ) obtain a viable solution , and ( 3 ) Lagrangian dual problem solving . To solve the problem of individual jobs , the two approaches are applied , ie , enumeration and dynamic

Keywords: Scheduling problems ; Some jobs ; Power sources simultaneously ; Lagrangian

relaxation .

BAB I

PENDAHULUAN

Makalah ini membahas masalah penjadwalan pe-kerjaan majemuk dengan sumberdaya simultan. Masalah penjadwalan melibatkan lebih dari satu pekerjaan dengan tiap pekerjaan terdiri atas satu himpunan operasi. Tiap operasi memerlukan pengerjaan secara simultan oleh lebih dari satu jenis sumberdaya. Jumlah unit dari tiap sumber-daya yang digunakan untuk pengerjaan suatu operasi adalah satu atau lebih. Masalah terkait dengan penentuan jadwal tiap operasi untuk tiap pekerjaan yang meminimumkan total tardiness tertimbang (total weighted tardiness).

BAB II

LANDASAN TEORI

2.1 Pengertian Teknik Relaksasi Lagrange

       Teknik relaksasi Lagrange merupakan teknik yang efektif untuk memecahkan masalah optimisasi kombinatoral yang sulit (hard combinatorial optimization pro-blem) seperti diungkapkan oleh Kaskavelis dan Caramanis. Menurut Morton dan Pentico penjadwalan adalah proses pengorganisasian, pemilihan dan pemberian waktu dalam penggunaan sumber dayanya untuk melaksanakan aktivitas yang diperlukan dalam menghasilkan output yang diinginkan dengan memenuhi waktu yang diinginkan pula. Persoalan penjadwalan timbul apabila jumlah mesin dan peralatan yang dimiliki terbatas sedangkan terdapat beberapa pekerjaan yang dapat dikerjakan secara bersama. 

2.2 Pemecahan Masalah Pekerjaan Individu

• Dasar metode enumerasi adalah sebagai berikut. Untuk tiap pekerjaan , misal himpunan operasi yang mendahului operasi dinyatakan dengan . Misal himpunan operasi yang mengikuti operasi yang membentuk hubungan lurus (linier) dinyatakan dengan .

• Dasar metode enumerasi misal menyatakan himpunan pendahulu dari operasi . Misal operasi didahului oleh operasi dan . Tiap tahap ditandai dengan notasi ( ). Misal himpunan operasi terdiri atas operasi. Dalam metode pemrograman dinamis maju, satu operasi semu ( ) ditambahkan setelah operasi terakhir dengan waktu pengerjaan . Dengan demikian himpunan operasi dinyatakan dengan{ } dan diperbarui menjadi dengan pengambahan bahwa mendahului.

BAB III

PENUTUPAN

Makalah ini telah mengusulkan teknik relaksasi Lagrange untuk memecahkan masalah penjadwal-an pekerjaan majemuk dengan sumberdaya simul-tan. Masalah penjadwalan melibatkan lebih dari satu pekerjaan dengan tiap pekerjaan terdiri atas satu himpunan operasi. Tiap operasi memerlukan pengerjaan secara simultan oleh lebih dari satu jenis sumberdaya dengan jumlah unit dari tiap sumber-daya yang digunakan untuk pengerjaan suatu operasi adalah satu atau lebih. Masalah terkait dengan penentuan jadwal dari tiap operasi dari tiap pekerjaan yang meminimumkan total tardiness tertimbang.