P PT INDONESIA TORAY SYNTHETHICS (PT ITS) merupakan perusahaan Toray bergerak dalam bidang serat sintetis dan tekstil. Produk yang dihasilkan diantaranya adalah benang nylon (Nylon Filament Yarn), serat polyester (Polyester Staple Fibre), benang polyester (Polyester Filament Yarn),polyester chip, dan nylon chip.Permasalahan yang dihadapi perusahaan saat ini adalah pada divisi Nylon FilamentYarn yang memproduksi benang nylon ada beberapa permintaan pelanggan tidak dapatmemenuhi due date yang telah ditetapkan . Sistem penjadwalan yang diterapkan perusahaan saat ini mengakibatkan completion time tiap job melebihi batas waktu yang telah ditetapkan. Berdasarkan permintaan produksi, terdapat tipe benang yang selalu ada pada daftar permintaan pelanggan tiap bulannya yaitu tipe 210-24-700. Dikarenakan tipe benang ini selalu di produksi , maka kelompok mesin spinning II yang terdiri dari 2 mesin dikhususkan untuk memproduksi tipe benang ini, sedangkan pada after treatment terdapat 5 mesin yang berada dalam satu kelompok. Keterbatasan jumlah spin di mesin spinning adalah dalam sekali proses hanya dapat menghasilkan 32 spin, sedangkan proses after treatment membutuhkan 144 spin untuk memulai proses . Karena adanya urutan proses flowshop dari spinning ke after treatment dan perbedaan jumlah spin dari kedua mesin tersebut mengakibatkan pada proses after treatment sering terjadi mesin menganggur karena mesin ini barn beroperasi jika seluruh spin terisi. Oleh karena itu, dengan tingginya jumlah permintaan pelanggan untuk tipe benang ini dan batasan pada jumlah sumber daya yang dimiliki perusahaan, maka perusahaan memerlukan jadwal produksi yang optimal agar permintaan pelanggan dapat diselesaikan sesuai dengan due date-nya.Penelitian tugas akhir ini dimaksudkan untuk membantu perusahaan membuatpenjadwalan barn dengan tujuan meminimasi completion time dan mempertimbangkan pemenuhan due date. Selanjutnya untuk mempercepat proses perhitungan dibuat program penjadwalan untuk model tersebut.Pengolahan data berdasarkan permintaan customer pada bulan Oktober 2008 yang dimulai pada tanggal 9 Oktober 2008. Pada metode ini diawali dengan solusi awal berdasarkan penjadwalan perusahaan yang menghasilkan completion time pada tanggal 4November 2008 pukul 5.34 WIB, algoritma NEH yang menghasilkan completion time pada tanggal 1 November 2008 pukul 13.56 WIB, dan aturan prioritas EDD yang menghasilkan completion time pada tanggal 4 November 2008 pukul 3.00 WIB. Ketiga solusi awal ini akan dilanjutkan ke solusi optimal berdasarkan Algoritma Relaksasi Lagrangian. Hasil penjadwalan solusi optimal ini akan mejadi perbandingan untuk dipertimbangkan sebagai usulan kepada pihak perusahaan.Penjadwalan perusahan menghasilkan completion time pada tanggal 3 November 2008 pukul 5.34 WIB. Hasil penjadwalan dengan algoritma Relaksasi Lagrangian menghasilkan completion time untuk penjadawalan perusahaan revisi pada tanggal 1 November 2008 pukul 23.26 WIB, penjadawalan dari solusi awal algoritma NEH pada tanggal 2 November 2008 pukul 21.12 WIB, penjadwalan dari solusi awal aturan prioritas EDD pada tanggal 2 November 2008 pukul 12.36 WIB. Berdasarkan perbandingan completion time, penjadwalan algoritma Relaksasi Lagrangian dapat meminimasi completion time sebesar 4,98% dari hasil penjadwalan perusahaan.