D Dalam memenuhi kepuasan konsumen akan suatu produk, perusahaan dituntut untuk dapat memenuhi permintaan konsumen, baik dari segi harga, mutu dan pelayanan yang baik yaitu ketepatan waktu penyelesaian. Dari pihak perusahaan, biaya untuk produksi harus ditekan seminimal mungkin sehingga akan mendapatkan keuntungan yang lebih besar. PT INDO KERAMIK INTI WIDYA adalah sebuah perusahaan keramik yang sedang berkembang. Perusahaan ini berusaha untuk meningkatkan pelayanan konsumen. Namun sexing terjadi perusahaan tidak dapat memenuhi pesanan konsumen pada waktu yang telah disepakati oleh kedua belah pihak. Pada bagian produksi, sexing mengalami pesanan yang belum pada waktunya telah selesai diproses, sedangkan pesanan yang seharusnya sudah selesai diproduksi dan dikirim ke konsumen belum dapat diselesaikan. Di samping itu biaya yang dikeluarkan akan semakin besar. Penjadwalan yang dilakukan oleh pihak perusahaan pada saat ini tergantung dari kepala divisi dalam mengatur penjadwalan berdasarkan pada pengalaman yang dimiliki. Oleh karena itu diperlukan adanya suatu model penjadwalan yang dapat dipakai sebagai acuan dalam menjalankan proses produksi. Model penjadwalan yang diusulkan yaitu model penjadwalan dengan pendekatan Lagrangian Relaxation dan Network Flow. Penjadwalan ini terdiri dari beberapa tahap yaitu : 1. Formulasi problem dual dari problem (P) dan pecahkan menj adi subproblem penjadwalan produksi atau production scheduling (PS) untuk tiap pesanan menggunakan Lagrangian relaxation pada pembatas kapasitas mesin. 2. Aplikasi dari a minimum cost linear network flow (MCLNF) algorithm untuk menyelesaikan tiap subproblem PS. Program Relax4 digunakan sebagai alat bantu dalam penyelesaian subproblem PS. 3. Aplikasi metode subgradien untuk menyelesaikan problem dual nondifferensial. 4. Mengembangkan algoritma heuristik yang dapat menyelesaikan solusi relax dari no. 1 sampai no. 3 sehingga dapat menghasilkan solusi (P) yang feasible dan near optimal dengan menggunakan interpretasi marginal cost dari variabel dual dan struktur network dari aliran produksi. Dan hasil perhitungan dan analisa yang telah dilakukan dapat diambil kesimpulan sebagai berikut : 1. Model penjadwalan ini meminimumkan biaya produksi yang terlibat secara langsung dalam proses produksi. 2. Model penjadwalan ini memperhitungkan kapasitas mesin yang tersedia dalam memenuhi pesanan dengan minimum cost linear network flow (MCLNF) algorithm.