Journal of Information System, Applied, Management, Accounting and Research. http://journal.stmikjayakarta.ac.id/index.php/jisamar , jisamar@stmikjayakarta.ac.id , jisamar2017@gmail.com e-ISSN: 2598-8719 (Online), p-ISSN: 2598-8700 ( Printed) , Vol. x No.x   bulan xxxx  202x

## OPTIMALISASI  PENJADWALAN PROSES PRODUKSI BERBASIS  PROGRAM KOMPUTER
Optimization Of Computer-Based Production Process Scheduling
Jeffry Susanto 1) , Ngarap Imanuel Manik 2) ,
1,2 Mathematics Departement, SoCS,Bina Nusantara University Jl.Kebon Jeruk Raya no.27 Jakarta Barat, Indonesia
Corresponding author e-mail: manik@binus.ac.id
Received: February 18, 2023 . Revised: March 5, 2023 . Accepted: March 28, 2023 .  Issue Period: Vol.7 No.2 (2023), Pp.280-288
Abstrak: Penjadwalan  merupakan  salah  satu  masalah  yang  penting  dalam  suatu sistem  produksi.    Pembentukan  jadwal  yang  optimal  untuk    proses  produksi  cukup sulit  dan  membutuhkan  waktu  perhitungan  yang  cukup  lama,  sehingga  diperlukan bantuan  program  Komputer  untuk  menyelesaikan  masalah  penjadwalan  tersebut. Makalah  ini  membahas  tentang  optimalisasi  penyelesaian  penjadwalan  proses produksi  dengan  menggunakan  bantuan  program  komputer  Algoritma  Relaksasi Lagrange.  Adapun  tahapan  yang  dilakukan  adalah  pada  awal  masalah  diselesaikan pada tingkatan job dengan pemrograman dinamis lalu dengan menggunakan metode subgradien  memperbarahui  nilai  pengali  lagrange.  Hasil  menunjukkan  bahwa penjadwalan  proses  produksi  yang  didapat  melalui  tahapan-tahapan  ini  merupakan penjadwalan yang optimal.
Kata kunci: : Penjadwalan Produksi, Optimalisasi, Algoritma Relaksasi Lagrange
Abstract: Scheduling  is  one  of  the  important  problems  in  a  production  system.  The formation  of  an  optimal  schedule  for  the  production  process  is  quite  difficult  and requires  a  long  calculation  time,  so  that  the  assistance  of  a  computer  program  is needed to solve the scheduling problem. This paper discusses the optimization of the completion  of  production  process  scheduling  using  the  help  of  the  Lagrange Relaxation Algorithm computer program. The steps taken are at the beginning of the problem  solved  at  the  job  level  with  dynamic  programming  and  then  using  the subgradient method to update the value of the lagrange multiplier. The results show that  the  scheduling  of  the  production  process  obtained  through  these  stages  is  the optimal scheduling.
Keywords: Production Scheduling, Optimization, Lagrange Relaxation Algorithm

## I. PENDAHULUAN
Untuk memenuhi pesanan secara efisien dan efektif dibutuhkan sebuah proses produksi yang berjalan dengan  lancar,  perusahaan  memerlukan  suatu  penjadwalan  proses  produksi  yang  baik  pula.  Dengan penjadwalan  proses  produksi  yang  terencana  secara  teratur,  perusahaan  tidak  hanya  dapat  mempersingkat waktu  tunggu  pelanggannya,  perusahaan  tersebut  juga  dapat  meningkatkan  efisiensi  dan  efektivitas  serta menghemat penggunaan sumber daya yang ada.
Journal of Information System, Applied, Management, Accounting and Research. http://journal.stmikjayakarta.ac.id/index.php/jisamar , jisamar@stmikjayakarta.ac.id , jisamar2017@gmail.com e-ISSN: 2598-8719 (Online), p-ISSN: 2598-8700 ( Printed) , Vol. x No.x   bulan xxxx  202x
PT NP adalah perusahaan yang memproduksi berbagai macam produk yang terbuat dari plastik, antara lain  kantong  plastik  (kresek),  kantong  bumbu,  tali  rafia  , polibag dan  sedotan.  Selama  ini  PT  Nilaco  Permai belum mempunyai sistem penjadwalan proses produksi yang baik dan optimal, sehingga setiap harinya proses produksi dilakukan dengan cara mengurutkan  sesuai daftar pesanan yang diterima, yaitu siapa yang memesan lebih awal akan mendapatkan hasil produksinya lebih awal pula atau hal ini disebut juga dengan FCFS ( First Come First Serve ). Untuk keperluan tersebut penulis akan mencoba membuat suatu sistem penjadwalan proses produksi yang lebih baik, sehingga dapat meningkatkan kelancaran produksi. Dengan penjadwalan yang lebih baik perusahaan dapat lebih memuaskan pelanggan dalam hal pemenuhan pesanan dari segi waktu,di samping itu perusahaan juga dapat lebih hemat dalam penggunaan sumber daya yang ada.
Dalam  upaya  mengatur  penjadwalan  proses  produksi  PT  NP  terdapat  beberapa  masalah  yang  harus dirumuskan terlebih dahulu. Perumusan masalah tersebut antara lain sebagai berikut :
a).  Faktor–faktor  apa  saja  yang  mempengaruhi  proses  produksi,  yang  harus  diperhatikan  dalam  membuat penjadwalan yang baik pada PT NP?
b).  Sumber  –  sumber  (mesin,  bahan  baku  dan  operator  mesin)  mana  yang  akan  dialokasikan  untuk melaksanakan tiap-tiap pekerjaan dalam proses produksi ?
c).  Apakah  dengan  adanya  penjadwalan  proses  produksi  yang  optimal  pada  PT  NP  memberikan  hasil  yang memuaskan bagi semua pihak.
Makalah ini membahas tentang penjadwalan statik dan deterministik pada pekerjaan ( job ) independen dengan  operasi-operasi  yang  dependen  untuk  kasus  banyak  sumber  (mesin,  bahan  baku  dan  operator  mesin). Tiap job mempunyai  beberapa  operasi  dengan  urutan  operasi  yang  bervariasi  (hubungan  ketergantungan  dari operasi untuk suatu job dianggap membentuk directed acyclic graph dan tiap job berakhir dengan satu operasi tunggal)  dan  pengerjaannya  memerlukan  beberapa  sumber  sekaligus.  Setiap  pekerjaan  memerlukan  sejumlah waktu tertentu untuk diselesaikan dan setiap operator hanya dapat menjalankan mesin tertentu. Proses produksi pada tahap tertentu baru dapat dikerjakan apabila proses pada tahap sebelumnya telah selesai pengerjaannya.

## 1.1 Algoritma Relaksasi Lagrange
Relaksasi  Lagrange  merupakan  suatu  algoritma  yang  semakin  banyak  digunakan  dalam  berbagai penerapan  pemrograman  matematika  berskala  besar.  Penerapan  relaksasi  lagrange  dimotivasi  oleh  adanya pengamatan  bahwa  banyak  masalah  pemrograman  bilangan  bulat  dapat  dimodelkan  dengan  mudah  dengan menghilangkan nasty  side  constraints [1]. Nasty  side  constraints dihilangkan  dari  himpunan  pembatas  dan ditempatkan  pada  fungsi  tujuan.  Ini  dikenal  dengan  istilah  dualisasi  ( dualizing ) nasty  side  constraints . Proses dualisasi  ini  menghasilkan  suatu  masalah  yang  relatif  mudah  untuk  dipecahkan  dan  solusinya  memberikan suatu batas bawah bagi solusi optimal dari masalah awal.
Bagi  masalah  penjadwalan  dengan  kriteria  meminimumkan  tardiness  tertimbang  total  untuk pendekatan relaksasi lagrange adalah sebagai berikut (disebut masalah P) :[2][3]
Minimasi J =  i i t T w
dengan memperhatikan pembatas-pembatas : precedence : c ij ≥ c il + t ij ; i  , j  ;  j , l є J
ketersediaan sumber : hk i j ijhk M    kebutuhan waktu proses : b ij = c ij – t ij + 1 ; i  , j  ;  j є J dengan : c ij adalah slot waktu akhir (penyelesaian) pengerjaan operasi j untuk job i. b ij adalah slot waktu awal pengerjaan operasi j untuk job i. t ij adalah waktu pemrosesan/pengerjaan operasi j untuk job i.
ijhk  adalah  variabel  biner 0 atau 1; ijhk  = 1  jika  operasi j  untuk job i menggunakan sumber h pada slot waktu k, ijhk  = 0 jika sebaliknya.
M hk adalah konstanta yang menunjukkan ketersediaan sumber h pada slot waktu k.
Journal of Information System, Applied, Management, Accounting and Research. http://journal.stmikjayakarta.ac.id/index.php/jisamar , jisamar@stmikjayakarta.ac.id , jisamar2017@gmail.com e-ISSN: 2598-8719 (Online), p-ISSN: 2598-8700 ( Printed) , Vol. x No.x   bulan xxxx  202x
Misalkan J adalah nilai tujuan optimal untuk masalah P dan diberikan suatu vektor pengali Lagrange tak negatif π hk untuk  merelaksasi  pembatas  ketersediaan  sumber
hk
i j ijhk M    maka  akan  diperoleh  masalah
Lagrange R, dimana :        R: min   i i t T w +           j i hk ijhk k h hk M , ,   (1)
dengan memperhatikan pembatas precedence dan pembatas kebutuhan waktu proses. Karena  nilai  L( π )  merupakan  batas  bawah  untuk  sembarang π ≥  0,  maka  masalahnya  sekarang  adalah bagaimana  menentukan pengali  Lagrange π* yang  memberikan  batas  bawah  terbaik.  Masalah  ini  disebut dengan masalah Dual Lagrange, dan dinyatakan dengan masalah D, yaitu [11] :
D:maks L , dengan  L=                i N j k h ijhk hk i i k h hk hk i T w M 1 , , min    (2)
dengan memperhatikan pembatas π hk ≥ 0 , pembatas precedence dan pembatas kebutuhan waktu proses.
Jika suatu operasi job dikerjakan pada slot  waktu tertentu  dan sumber tertentu,  maka ijhk  = 1. Jadi, jika π hk dikalikan dengan ijhk  untuk slot waktu k dan sumber h yang digunakan, hasilnya akan tetap bernilai π hk . Maka nilai   i N l j k h ijhk hk ,   akan sama dengan nilai π pada sumber h yang digunakan dan slot waktu k yang terpakai (dari slot waktu awal operasi (b ij ) sampai slot waktu akhir operasi (c ij )), yaitu
    i ij ij N l j c b k ijhk  (3)
Sehingga dapat dilakukan penyederhanaan sebagai berikut :
D : maks L , dengan L= 
       
          i N j c b k ijhk i i k h hk hk i ij ij T w M 1 , min   (4)
dan  jika  job-job  adalah  independen  maka  minimum  dari  penjumlahan  adalah  jumlah  dari  minima  sehingga bentuk rumusan D dapat dinyatakan sebagai berikut :
D : maks L , dengan  L=                   i N j c b k ijhk i i k h hk hk i ij ij T w M 1 , min   (5)
dengan memperhatikan pembatas π hk ≥ 0 , pembatas precedence dan pembatas kebutuhan waktu proses. Berdasarkan rumusan Dual Lagrange di atas, maka model permasalahan tersebut dapat disederhanakan menjadi dekomposisi dari submasalah untuk tiap job i (untuk { π hk } yang diberikan) sebagai berikut :
R i : min L i dengan L i ≡
     i ij ij N j c b k ijhk i i T w 1  (6)
dengan memperhatikan pembatas c ij ≥ c il + t ij ; i  , j  ;  j , l є J b ij = c ij – t ij + 1 ; i  , j  ;  j є J

## 1.2       Metode Subgradien
Masalah  yang  muncul  pada  algoritma  Relaksasi  Lagrange  adalah  bagaimana  mendapatkan  pengali Lagrange π hk * yang  memberikan batas bawah terbaik. Untuk  mendapatkan solusi dual  Lagrange  yang optimal π hk * , terdapat berbagai teknik yang tersedia, diantaranya adalah metode elipsoid , metode ascent direction dan metode  subgradien.  Di  antara  metode-metode  tersebut,  metode  subgradien  merupakan  metode  yang  paling
Journal of Information System, Applied, Management, Accounting and Research. http://journal.stmikjayakarta.ac.id/index.php/jisamar , jisamar@stmikjayakarta.ac.id , jisamar2017@gmail.com e-ISSN: 2598-8719 (Online), p-ISSN: 2598-8700 ( Printed) , Vol. x No.x   bulan xxxx  202x
banyak diterapkan karena kemudahannya dalam implementasinya. Misalkan π hk menyatakan vektor dari pengali Lagrange maka :[4]
π hk =  π hk + ∆π hk dimana ∆π hk =
H L i  
dengan : ~ H merupakan horizon waktu dari job ~λ merupakan suatu skalar yang nilainya dipilih antara 0 dan 2. Selanjutnya untuk meningkatkan konvergensi geometrik menuju keoptimalan, Fisher menentukan nilai λ terbaik adalah 2.
~ i n i i L L L    dimana i n i L L 3 , 1  sehingga i i L L 3 , 0  
Prosedur  pencarian  nilai  tersebut  diusulkan  oleh  Caramis  &  Kaskavelis  [5],  didapat  dari  percobaan  numerik yang berulang-ulang.

## II. METODE DAN MATERI
Metode  yang  digunakan  untuk  menyelesaiakan  masalah    ini  menggunakan  Model  rekayasa  piranti  lunak  yang digunakan adalah Classic Cycle ( Waterfall Model ). Model ini dipilih karena sistem yang dirancang akan mudah dievaluasi walaupun belum mendapatkan hasil akhir. Terdiri dari lima tahap:

## 1. Requirements definition
Dalam tahapan ini, difokuskan pada perancangan piranti lunak yang akan dibangun, pembatasan kegunaan dan tujuan  yang  akan  dicapai  oleh  sistem.  Dikumpulkan  pula  informasi  yang  dibutuhkan  dan  dipahami  fungsi  apa saja yang diinginkan sesuai dengan kesepakatan dalam konsultasi antara pengguna dan perancang piranti lunak.

## 2. System and software design
Dalam tahapan ini, didesain penggambaran modul dari piranti lunak secara terperinci dan dilakukan pengkajian kualitas.  Tahapan  ini  berfokus  pada  struktur  data,  arsitektur  piranti  lunak  dan  prosedur  secara  detil.  Selain  itu dilakukan juga langkah pengkodean dengan mengubah desain yang telah dirancang ke dalam bentuk yang dapat dibaca oleh mesin.

## 3. Implementation and unit testing
Sebuah piranti  lunak terdiri dari sekumpulan  unit program  ( program units )  yang  memiliki tugas dan deskripsi masing-masing  yang  lebih  spesifik.  Pada  tahapan  ini  dilakukan  pengujian  setiap  unit  program  secara  terpisah dengan melihat kesesuaian unit dengan spesifikasi yang diinginkan.

## 4. Integration and system testing
Setelah pengujian setiap unit program, maka semua unit program yang ada akan diintegrasikan menjadi sebuah piranti  lunak  yang  lengkap  dan  dilakukan  pengujian  pada  semua  fungsi  dalam  piranti  lunak  yang  sudah dibangun.  Pengujian  ini  dimaksudkan  untuk  menemukan  kemungkinan  adanya  kesalahan  serta  memastikan keluaran yang dihasilkan telah sesuai dengan yang diinginkan.

## 5. Operation and maintenance
Piranti  lunak  yang  baik  harus  mampu  melakukan  penyesuaian  terhadap  perubahan/peningkatan  yang  mungkin terjadi  di  masa  mendatang,  baik  dikarenakan  peningkatan  kebutuhan  pengguna  ataupun  pengembangan  dari lingkungan  di  luar  sistem  piranti  lunak  tersebut  sehingga  tidak  perlu  dibuat  program  baru  hanya  untuk memenuhi kebutuhan yang mungkin menjadi lebih kompleks.
Secara  keseluruhan  metode  perancangan  ini  merupakan  tahapan  dalam Classic  Cycle atau Waterfall  Model menurut Sommerville  yang ditunjukkan seperti pada gambar 1.[6]
Journal of Information System, Applied, Management, Accounting and Research. http://journal.stmikjayakarta.ac.id/index.php/jisamar , jisamar@stmikjayakarta.ac.id , jisamar2017@gmail.com e-ISSN: 2598-8719 (Online), p-ISSN: 2598-8700 ( Printed) , Vol. x No.x   bulan xxxx  202x
Gambar 1. Waterfall Model menurut Sommerville

## Flowchart algoritma
Membuat suatu sistem penjadwalan proses produksi yang baik dan optimal dipengaruhi oleh beberapa variabel  antara  lain  seperti  :  banyaknya  jumlah  pekerjaan/job,  due  date  dari  job,  bobot  job,  horizon  waktu, banyak  operasi  untuk  tiap  job,  waktu  masing-masing  operasi  dan  sumber  yang  digunakan  untuk  tiap  operasi. Sedangkan  ukuran  kinerja  yang  digunakan  adalah  tardiness  tertimbang  total  dimana  semakin  kecil  nilai tardiness semakin baik suatu sistem penjadwalan. Gambar 2. adalah flowchart algoritma penyelesaian  masalah secara keseluruhan.[7].
Gambar 2.  Flowchart Algoritma Penyelesaian Masalah
Requirements System and Software Design Integration and Operation and Implementation Tidak Ya Mulai Input variabel perhitungan Inisialisasi pengali Lagrange Menentukan slot waktu yang mungkin Menentukan nilai fungsi tujuan tardiness minimum dengan dynamic programming Nilai fungsi tujuan tardiness List Scheduling Metode Subgradien memperbaiki nilai pengali Selesai Penjadwalan untuk tiap Slot waktu awal untuk tiap operasi Nilai fungsi tujuan tardiness Perhitungan Volume
Journal of Information System, Applied, Management, Accounting and Research. http://journal.stmikjayakarta.ac.id/index.php/jisamar , jisamar@stmikjayakarta.ac.id , jisamar2017@gmail.com e-ISSN: 2598-8719 (Online), p-ISSN: 2598-8700 ( Printed) , Vol. x No.x   bulan xxxx  202x

## Perancangan
Program  aplikasi  akan  dibuat  menggunakan  4  layar  tampilan,  yaitu  layar  detail job, layar  detail  operasi,  layar volume dan gantt chart. Gambar 3 berikut adalah state transition diagram antar layar :[9][10]
Gambar  3. State Transition Diagram Antar Layar

## III. PEMBAHASAN  DAN HASIL
Program  yang  dibuat  untuk  menyelesaiakan  masalah  ini  menggunakan  pemrogramnan  Java,  kemudian  setelah dibuat  dan  di-run  program  maka  ditampilkan  beberapa  hasil  dari  program  dimaksud  seperti  berikut  ini.    Pada program ini terdapat 4 layar: a). Layar Detail Job b).Layar Detail OperasiL     c). Layar Volume      d). Layar Gantt Chart
Ad.1 Layar  Detail  Job; Pada  layar  detail  job  kita  dapat  mengisi  detail-detail  yang  berhubungan  dengan job . Horizon  waktu  ,batas  waktu job ,  jumlah  sumber  dan  bobot job adalah  untuk  masing-masing  sumber  yang di input . Pada layar ini terdapat pula scroll bar untuk jumlah job dan jumlah sumber, scroll bar ini dimaksudkan untuk mempermudah pengisian data. Hal ini dapat dilihat pada gambar 4.
Gambar 4. Layar Detail Job
Klik tab menu layar volume Klik tab menu layar detail job Klik tab menu layar detail operasi Klik tab menu layar volume Klik button tampil input atau button processs Kembali ke layar aktif Program diterminasi Kembali ke layar aktif Kembali ke layar aktif Klik button gantt chart Klik tab menu layar detail operasi Klik button tampil input atau button process Klik tab menu layar detail job Layar Detail job Layar Detail operasi Layar Gantt Chart Mula i Layar Volume
Journal of Information System, Applied, Management, Accounting and Research. http://journal.stmikjayakarta.ac.id/index.php/jisamar , jisamar@stmikjayakarta.ac.id , jisamar2017@gmail.com e-ISSN: 2598-8719 (Online), p-ISSN: 2598-8700 ( Printed) , Vol. x No.x   bulan xxxx  202x
Ad.2 Layar  Detail  Operasi ;  Pada  layar  detail  operasi  kita  dapat  mengisi  detail-detail  yang  berhubungan dengan operasi. Waktu operasi, sumber yang dipakai serta keterangan mengenai sumber dan operasi pendahulu adalah untuk masing-masing operasi. Pada layar ini terdapat pula scroll bar untuk jumlah operasi, scroll bar ini dimaksudkan untuk mempermudah pengisian data, seperti pada gambar 5.

## Gambar 5. Tampilan Untuk Tombol Process
Ad.3 Layar Volume ; Pada layar ini kita dapat menghitung waktu pengerjaan dalam satuan jam ataupun volume apabila salah satunya diketahui. Untuk perhitungan juga perlu diketahui operasi yang mana serta sumber yang digunakan, seperti pada gambar 6.

## Gambar 6. Layar Volume Setelah Diinput
Ad.4 Layar Gantt Chart ; Pada layar ini penjadwalan dibuat dalam bentuk chart sehingga lebih mudah untuk dilihat. Sumbu  mendatar adalah untuk  waktu  sedangkan sumbu tegaknya adalah  untuk  sumber, seperti terlihat dalam gambar 7.
Gambar 7. Tampilan Gantt Chart
Journal of Information System, Applied, Management, Accounting and Research. http://journal.stmikjayakarta.ac.id/index.php/jisamar , jisamar@stmikjayakarta.ac.id , jisamar2017@gmail.com e-ISSN: 2598-8719 (Online), p-ISSN: 2598-8700 ( Printed) , Vol. x No.x   bulan xxxx  202x
Berikut adalah hasil yang didapat dengan menggunakan algoritma Relaksasi Lagrange  seperti yang ditampilkan pada tabel 1
Tabel 1.Rincian Untuk Tiap Pekerjaan No. Pekerjaan / job Horizon waktu Due date Bobot Waktu Selesai Tardiness Nilai Fungsi Tujuan Tardiness 1. Kantong Plastik HD 11 8 5 9 1 69,55 2. Kantong Plastik PP 10 7 4 7 0 74 3. Kantong Plastik PE 9 7 4 8 1 83,33 4. Tali 7 5 3 5 0 51,484 5. Sedotan 4 4 2 3 0 28 6. Polibag 10 8 6 9 2 99,6 7. Kantong Bumbu 7 4 3 4 0 36,342
Berikut adalah perbandingan hasil produksi PT NP sebelum menggunakan algoritma relaksasi lagrange dengan sesudah menggunakan algoritma relaksasi lagrange ditunjukkan dalam tabel 2.
Tabel 2. Perbandingan Hasil Produksi Rata-rata per hari No. Produk Tipe Hasil rata-rata perhari tanpa algoritma relaksasi lagrange Hasil rata-rata perhari dengan algoritma relaksasi lagrange 1. Kantong Plastik (kresek) High Density (HD) 1555,2 kg 1790,6 kg Polyethylene (PE) 1718,3 kg 2029,7 kg Polypropylene (PP) 1632,6 kg 1916,5 kg 2. Tali rafia Polypropylene (PP) 432,2 kg 492,1 kg 3. Polibag Polyethylene (PE) 1812,5 kg 2204,9 kg 4. Sedotan High Density (HD) 87,4 kg 98,3 kg 5. Kantong Bumbu Polypropylene (PP) 248,7 kg 279,2 kg
Dapat  dilihat  bahwa  dengan  algoritma  relaksasi  lagrange  terdapat  peningkatan  hasil  produksi  rata-rata  perhar, seperti pada tabel 3..
Tabel 3. Persen Peningkatan Hasil Produksi Rata-rata per hari No. Produk Tipe Persen Peningkatan 1. Kantong Plastik (kresek) High Density (HD) 15,14 % Polyethylene (PE) 18,12 % Polypropylene (PP) 17,39 % 2. Tali rafia Polypropylene (PP) 13,86 % 3. Polibag Polyethylene (PE) 21,16 % 4. Sedotan High Density (HD) 12,47 % 5. Kantong Bumbu Polypropylene (PP) 12,26 %

## IV. KESIMPULAN
Dari analisa yang sudah dilakukan maka dapat ditarik beberapa kesimpulan dimana penarikan kesimpulan bahwa dengan adanya penjadwalan proses produksi  yang dibentuk berdasarkan algoritma  Relaksasi  Lagrange  maka PT NP mempunyai  sistem  penjadwalan  yang  lebih  baik  dan  optimal  daripada  sebelumnya.  Seperti  contohnya  terlihat  pada hasil  rata-rata  perhari  kantong  plastik  HD  yang  sebelumnya  hanya  1555,2  kg  sekarang  menjadi  1790,6  kg  atau meningkat sebesar 15,14 %. Faktor-faktor yang mempengaruhi dalam membuat penjadwalan yang baik dan optimal di PT  NP  adalah  due  date  dari  job,  bobot  job,  horizon  waktu,  banyak  operasi  untuk  tiap  job,  waktu  masing-masing operasi  dan  sumber  yang  digunakan  untuk  tiap  operasi,  seperti  contohnya  proses  produksi  kantong  plastik  HD  dan kantong  plastik  PP  mempunyai  detail  yang  berbeda  sehingga  nilai  fungsi  tujuan  tardiness  masing  –  masing  juga berbeda  yaitu  69,55  dan  74.  Kemudian  penjadwalan  dengan  algoritma  Relaksasi  Lagrange  menghasilkan  manfaat
Journal of Information System, Applied, Management, Accounting and Research. http://journal.stmikjayakarta.ac.id/index.php/jisamar , jisamar@stmikjayakarta.ac.id , jisamar2017@gmail.com e-ISSN: 2598-8719 (Online), p-ISSN: 2598-8700 ( Printed) , Vol. x No.x   bulan xxxx  202x
yang cukup besar bagi PT NP, dengan adanya peningkatan hasil produksi dan tentu saja penjadwalan proses produksi yang lebih baik, PT NP dapat menghasilkan keuntungan yang lebih dan dapat meningkatkan kepuasan pelanggan

## Saran
Dengan  algoritma  Relaksasi  Lagrange  dapat  diperoleh  suatu  sistem  penjadwalan  yang  dari  segi  efisiensi  dan efektivitas  mendekati  optimal,  tapi  tidak  tertutup  kemungkinan  memperbaiki  performansi  algoritma  Relaksasi Lagrange  baik  dari  segi  efisiensi  maupun  efektivitas.  Dari  segi  efisiensi,  misalnya  dengan  mengganti  metode subgradien dengan metode-metode baru yang berkembang dewasa ini. Dari segi efektivitas, penggunaan metode list scheduling yang  merupakan  metode  heuristik  dalam  pembentuan  jadwal  layak  dapat  digantikan  dengan  metode heuristik lain yang lebih baik atau dengan pendekatan optimal yang akan menjamin kualitas solusi yang baik. Konsep model  dan  algoritma  Relaksasi  Lagrange  yang  dikembangkan  penulis  ini  juga  dapat  dikembangkan  untuk penyelesaian  masalah  penjadwalan  yang  lebih  kompleks  lagi  sesuai  dengan  permasalahan  di  dunia  nyata,  seperti jumlah job yang sangat banyak serta penggunaan sumber dengan berbagai macam batasan.

## REFERENSI
[1]    Rius-Sorolla  G1  ,  Maheut  J,  “Lagrangian  relaxation  of  the  Generic  Materials  and  Operations  Planning  model”,
Central European Journal of Operations Research . 28, 2020, pp105-123.
[2]    Michael. “ Scheduling : theory, algorithms, and systems” , 4 nd Edition Prentice Hall, Springer,  2013
[3]  Allahverdi, Ali. “A Survey of Scheduling Problems with No-Wait in Process: A Survey of Scheduling Problems with No-Wait in Process.” European Journal of Operational Research 255, no. 3, Elsevier (2016): pp.665–86.
[4]   Le  Hai Yen,  Le  Dung Muu,“A  subgradient  method  for  equilibrium  problems  involving  quasiconvex bifunctions”, Operations Research Letters , Volume 48, 5, 2020, Pages 579-583
[5]   Yaohua  Hu,  et  all,  “A  Subgradient  Method  Based  on  Gradient  Sampling  for  Solving  Convex  Optimization Problems”, Numerical Functional Analysis and Optimization , Volume 36,12, 2015, pp 1559-1584
[6]    Sommerville, Ian., Software Engineering . 10 th Edition. Pearson  Publisher, Canada, 2015
[7 ]   Jian-YaDing , ShijiSong , Jatinder  N.D.Gupta at  all,  ”An  improved  iterated  greedy  algorithm  with  a  Tabu-based reconstruction  strategy  for  the  no-wait  flowshop  scheduling  problem ”,  Applied  Soft  Computing Volume 30, 2015, Pages 604-613
[8]   Peter B. Luh, Xing Zhao, Yajun Wang, and Lakshman S. Thakur ,“Lagrangian Relaxation Neural Networks for Job Shop Scheduling” , IEEE Transactions on Robotics and  Automation, Vol. 16, No. 1, 2000, pp 78-88.
[9] Sapkal, S.U. Laha, D., and J.N.D. Gupta. “A Penalty-Shift-Insertion Based Algorithm to Minimize Total Flow Time in No-Wait Flow Shops.” Journal of the Operational Research Society 65, no. 10, Elsevier (2014),pp11– 24.
[10]  Ding,  Jian-Ya,  Shiji  Song,  Jatinder  ND  Gupta,  Rui  Zhang,  Raymond  Chiong,  and  Cheng  Wu.  "An  improved iterated  greedy  algorithm  with  a  Tabu-based  reconstruction  strategy  for  the  no-wait  flowshop  scheduling problem." Applied Soft Computing 30, Elsevier (2015):pp. 604-613.
[11]  Suprayogi , Valentine, “ Teknik Relaksasi Lagrange  untuk Penjadwalan Pekerjaan Majemuk dgn Penggunaan Sumberdaya Simultan”, Jurnal Teknik Industri , Vol. 17, No. 2, (2015), pp 71-80