P PT. SkyCamping Indonesia adalah perusahaan manufaktur yang bergerak dalam bidang garment, dan membagi produknya ke dalam 3 divisi yaitu Tenda, Outwear, dan tas dengan jenis sport duffel, backpack, computer case, roller duffel, sport equipment bag & gun case. Setiap divisi memiliki lantai produksi tersendiri. Seluruh jenis produk di produksi berdasarkan pesanan, dan semuanya untuk di eksport. Banyaknya variasi produk yang dipesan, menyebabkan SkyCamping mengalami kesulitan untuk menetapkan jadwal produksi. Pada divisi tas, keterlambatan terbesar terjadi padi bagian sewing. Hal ini disebabkan karena penjadwalan dilakukan hanya berdasarkan pengalaman tanpa adanya suatu sistem penjadwalan tertentu. Bagian sewing memiliki 23 lini produksi (parallel), 770 mesin jahit dan dengan 2.638 pekerja. Ke 23 lini produksi tersebut dapat mengerjakan berbagai macam jenis tas yang dipesan. Permasalahan yang terjadi adalah bagaimana menentukan urutan penjadwalan untuk 23 lini parallel tersebut dan bagaimana menentukan jumlah produk yang sebaiknya dikerjakan pada setiap lini hingga dapat meminimasi jumlah dan waktu keterlambatan. Algoritma Kaspi-Montreuil adalah sistem penjadwalan untuk n mesin parallel yang menitik beratkan pada minimasi mean tardiness dan tardy job dengan mempertimbangkan due date serta waktu proses dari setiap job. Metode Neighborhood-search digunakan untuk menyempurnakan algoritma Kaspi-Montreuil. Namun, dari penelitian yang dilakukan, diketahni bahwa perhitungan dengan algoritma Kaspi-Montreuil dan metode Neighborhood-search belum bisa mencapai hasil yang diinginkan karena ada beberapa job dengan jumlah produksi yang besar sekali, sehingga tidak efektif untuk mengerjakan job tersebut hanya dalam satu lini raja. Hal ini menyebabkan perlu dilakukan modifikasi dan pengembangan dari algoritma utama yang sudah ada, yaitu dengan memecah job tersebut menjadi beberapa batch dan dikerjakan pada lini yang lain. Berdasarkan basil perhitungan, dari 65 job yang ada, setelah dipecah maka menjadi 86 batch, serta diperoleh penjadwalan barn. Hasil penjadwalan baru tersebut menunjukan job yang mengalami keterlambatan (tardy job), maksimum tardiness dan mean tardiness menjadi lebih kecil dari penjadwalan mula-mula. Pada penjadwalan awal, jumlah tardy job sebesar 26, dan pada penjadwalan baru jumlah tardy job sebesar 5. Jumlah maksimum tardiness yang tadinya 117.5 jam, turun menjadi 103.2 jam. Besarnya mean tardiness pada penjadwalan yang lama adalah sebesar 14.7 jam, sedangkan pada penjadwalan barn menjadi 2.27 jam.