MODEL PROGRAM INTEGER UNTUK MENENTUKAN HORIZON WAKTU PERAMALAN DALAM MENYELESAIKAN MASALAH DYNAMIC LOT SIZING
TESIS
Oleh
LUCY KARYATI BASAR 067021004/MT
SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
MODEL PROGRAM INTEGER UNTUK MENENTUKAN HORIZON WAKTU PERAMALAN DALAM MENYELESAIKAN MASALAH DYNAMIC LOT SIZING
TESIS
Untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara
Oleh
LUCY KARYATI BASAR 067021004/MT
SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
Judul Tesis
: MODEL PROGRAM INTEGER UNTUK MENENTUKAN HORIZON WAKTU PERAMALAN DALAM MENYELESAIKAN MASALAH DYNAMIC LOT SIZING Nama Mahasiswa : Lucy Karyati Basar Nomor Pokok : 067021004 Program Studi : Matematika
Menyetujui, Komisi Pembimbing
(Drs. Opim Salim S, M.IKom, PhD) Ketua
(Prof. Dr. Herman Mawengkang) Anggota
Ketua Program Studi
Direktur
(Prof. Dr. Herman Mawengkang)
(Prof. Dr. Ir. T. Chairun Nisa. B,M.Sc)
Tanggal lulus: 16 Juli 2008
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
Telah diuji pada Tanggal 16 Juli 2008
PANITIA PENGUJI TESIS
Ketua
:
Drs. Opim Salim S, M.IKom, PhD
Anggota
:
Prof. Dr. Herman Mawengkang Dr. Sutarman, MSc Dra. Mardiningsih, MSi
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
ABSTRAK Konsep horizon peramalan sudah dipelajari secara luas dalam literature manajemen operasi/riset dalam konteks mengevaluasi dampak data masa datang terhadap keputusan-keputusan saat ini di lingkungan pembuat keputusan perioda ganda. Sebagai pendekatan solusi untuk menghitung horizon-horizon peramalan, program integer sudah terabaikan oleh komunitas riset. Akan tetapi, kelebihan pemodelan dan struktur pendekatan ini disertai dengan perkembangan terbaru yang signifikan dalam program integer secara komputasi menciptakan suatu keadaan yang dapat digunakan dalam konteks horizon peramalan. Tesis ini membahas pemakaian program integer untuk memeriksa horizon-horizon peramalan pada masalah pengukuran lot dinamik (DLS). Ada dua tahap pengerjaan: (i) formulasi syarat-syarat cukup yang terkenal dan karakterisasi horizon-horizon peramalan sebagai pertanyaan-pertanyaan layak/optimal dalam Program Integer, (ii) formulasi karakterisasi untuk horizon-horizon peramalan dengan mengasumsikan permintaan-permintaan akan datang adalah integer. Kata kunci : Horizon peramalan, Program Integer dan Pengukuran lot dinamik
i Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
ABSTRACT The concept of a forecast horizon has been widely studied in the operations management/research literature in the context of evaluating the impact of future data on current decisions in a multi-period decision making environment. As a solution approach for computing forecast horizons, integer programming has been ignored by the research community. However, the modeling and structural advantages of this approach coupled with the recent significant developments in computational integer programming make for a case that can be used in forecast horizons context. This thesis studies the use of integer programming to investigate forecast horizons for the dynamic lot-sizing problem (DLS). There are two steps: (i) formulating some well-known sufficient conditions and characterizations for forecast horizons as feasibility/optimality questions in Integer Programs, (ii) formulating characterization for forecast horizons assuming integer future demands. Keywords : Forecast horizon, Integer Programming, and Dynamic lot-sizing
ii Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
KATA PENGANTAR Puji dan syukur kehadirat Allah SWT penulis panjatkan atas limpahan rahmat dan karunia-Nya atas terselesaikannya penulisan tesis ini yang berjudul ”Model Program Integer untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah Dynamic Lot Sizing”. Pada kesempatan ini, penulis menyampaikan ucapakan terima kasih yang sebesar-besarnya kepada: Bapak Prof. dr. Chaeruddin P. Lubis, DTM&H, Sp.Ak. selaku Rektor Universitas Sumatera Utara yang sudah memberi kesempatan kepada penulis untuk menempuh pendidikan di Universitas Sumatera Utara. Ibu Prof. Dr. Ir. T. Chairun Nisa B., M.Sc. selaku Direktur Sekolah Pascasarjana Universitas Sumatera Utara yang sudah memberikan kesempatan kepada penulis untuk mengikuti Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara. Bapak Prof. Dr. Herman Mawengkang selaku Ketua Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara dan selaku Anggota Komisi Pembimbing yang telah membantu dalam penyelesaian tesis ini. Bapak Dr. Saib Suwilo, M.Sc. selaku Sekretaris Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara yang telah memberikan motivasi kepada penulis.
iii Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
Bapak Drs.
Opim Salim S, M.Ikom.
PhD. selaku Ketua Komisi
Pembimbing yang telah banyak memberikan saran dan bimbingan kepada penulis. Bapak Dr. Sutarman, MSc. dan Ibu Dra. Mardiningsih, MSi. selaku Pembanding atas segala saran dan masukannya. Rektor Unimed, Dekan FMIPA-Unimed, dan Ketua Jurusan Matematika FMIPA-Unimed yang telah memberikan kesempatan kepada penulis untuk melanjutkan pendidikan di Sekolah Pascasarjana Universitas Sumatera Utara. Pengelola bantuan dana pendidikan (BPPS) dari Direktorat Pendidikan Tinggi yang telah memberikan bantuan dana pendidikan dan penelitian selama penulis menempuh pendidikan di Sekolah Pascasarjana Universitas Sumatera Utara. Seluruh staf pengajar pada Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara yang sudah membimbing dan membantu selama penulis mengenyam pendidikan. Seluruh keluarga, mamah dan adik-adik yang senantiasa mendukung dan mendoakan untuk keberhasilan penulis dalam menyelesaikan pendidikan ini. Ibu Dra. Hj. Dina Ampera, MSi. dan keluarga yang sudah banyak membantu penulis dalam menghadapi banyak kesulitan selama menyelesaikan pendidikan ini. Kepada semua temen-teman serta semua pihak yang tidak dapat disebutkan satu persatu penulis ucapkan terima kasih atas bantuan dan dorongan yang telah diberikan sehingga penulis dapat menyelesaikan pendidikan tepat waktu. Tidak lupa terima kasih untuk Misiani, Amd.
selaku staf Administrasi Program
Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara yang telah memberikan pelayanan yang baik kepada penulis. iv Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
Penulis menyadari tesis ini masih mempunyai kekurangan, namun demikian harapan penulis, semoga tesis ini dapat bermanfaat bagi yang membutuhkannya.
Medan, 25 Juli 2008 Penulis,
Lucy Karyati Basar
v Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
RIWAYAT HIDUP Penulis dilahirkan di Bandung pada tanggal 2 Juni 1962, sebagai anak pertama dari tiga bersaudara dari ayah almarhum R. Basar Soetawidjaja dan ibu Djuariah Karmiaty. Penulis menamatkan Sekolah Dasar Negeri Nilem 3 Bandung pada tahun 1974, Sekolah Menengah Pertama Negeri 13 Bandung pada tahun 1977, Sekolah Menengah Atas Negeri 7 Bandung pada tahun 1981, dan pada tahun 1981 melanjutkan pendidikan di Universitas Pajajaran (UNPAD) Bandung, Fakultas Matematika dan Ilmu Pengetahuan Alam, Jurusan Matematika dan lulus pada tahun 1987. Dari tahun 1989 sampai dengan sekarang penulis menjadi staf pengajar di Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Negeri Medan (UNIMED). Pada tahun 2006 penulis mengikuti pendidikan pada Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara.
vi Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
i
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ii
KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . .
iii
RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vii
BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . .
1
1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . .
1
1.2 Perumusan Masalah . . . . . . . . . . . . . . . . . . . .
4
1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . .
4
1.4 Kontribusi . . . . . . . . . . . . . . . . . . . . . . . .
5
1.5 Metodologi . . . . . . . . . . . . . . . . . . . . . . . .
5
BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . .
6
2.1 Perkembangan Kajian Horizon Peramalan . . . . . . . . .
6
2.2 Metode Yang Digunakan Dalam Dynamic Lot Sizing
. . .
8
BAB 3 LANDASAN TEORI . . . . . . . . . . . . . . . . . . . . .
10
3.1 Pengertian Program Linear . . . . . . . . . . . . . . . .
10
3.2 Pengertian Program Integer . . . . . . . . . . . . . . . .
11
3.3 Model Dynamic Lot-Sizing
. . . . . . . . . . . . . . . .
12
. . . . . . . . . . . . . . . . . . . . . . .
14
4.1 Syarat Cukup dari Lundin and Morton (1975) . . . . . . .
14
BAB 4 PEMBAHASAN
vii Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
4.2 Syarat Perlu dan Cukup dari Chand and Morton (1986) . .
19
4.3 Horizon Peramalan Minimal . . . . . . . . . . . . . . . .
24
BAB 5 KESIMPULAN . . . . . . . . . . . . . . . . . . . . . . . .
29
5.1 Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . .
29
DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . .
31
viii Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
BAB 1 PENDAHULUAN
1.1 Latar Belakang Bagi perusahaan-perusahaan pabrikasi, menentukan produksi optimal sangat bergantung pada kebutuhan dan permintaan pasar. Oleh karena itu, untuk perusahaan-perusahaan seperti ini, penentuan jadwal produksi selalu didasarkan pada peramalan permintaan masa datang. Biasanya, peramalan-peramalan akurat yang tersedia pada horizon tertentu hanya untuk beberapa periode awal, sedangkan periode-periode berikutnya menjadi tidak jelas. Oleh karena itu, diperlukan sebuah proses pembuatan keputusan periode ganda, dimana manajermanajer yang terlibat dalam produksi dan pengambilan keputusan secara khusus menggunakan peramalan-peramalan dari beberapa periode awal untuk mengevaluasi keputusan saat ini. Gejala yang diperoleh dari data peramalan, walaupun tidak akurat, tidak dapat diabaikan dan biasanya diikutsertakan dalam keputusan sekarang. Untuk proses pembuatan keputusan yang sempurna diperlukan proses pengevalusian data bisnis masa datang, misalnya biaya (cost) dan permintaan (demand). Untuk itu, diperlukan konsep horizon peramalan (forecasting horizon), yaitu banyaknya periode masa datang yang dibuat untuk memprediksi, (misalnya satu langkah, dua langkah, ..., h langkah) dan konsep horizon waktu (time horizon) atau horizon perencanaan (planning horizon), yakni satu titik waktu tertentu di masa yang akan datang dimana suatu proses akan dievaluasi. Dalam manajemen akunting, finansial, dan resiko, diperlukan sebuah penetapan horizon waktu tertentu sedemikian hingga diperoleh alternatif1 Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
2 aternatif yang dapat dilaksanakan pada periode waktu yang dimaksud. Horizon waktu yang paling umum digunakan adalah triwulan, kuartal, satu sampai lima tahun, bahkan lebih dari 10 tahun. Dalam hal ini, isu dasar adalah seberapa besar pengaruh data masa datang terhadap keputusan saat ini. Terhadap konteks dalam kajian ini, konsep horizon peramalan telah dikaji dalam literatur manajemen operasi dan operasi riset (Chand et al., 2002). Pengertian horizon keputusan mengacu pada jumlah beberapa periode berikut, misalnya τ , namun keputusan harus dibuat pada periode saat ini. Suatu bilangan integer T dinyatakan sebagai horizon peramalan yang berkaitan dengan horizon keputusan τ . Jika data (misalnya, biaya dan permintaan) setelah periode T tidak mempengaruhi keputusan optimal untuk periode τ pertama dalam sebarang masalah N -periode dengan N ≥ T + 1. Untuk suatu horizon keputusan, pentingnya horizon peramalan T , jika ada, adalah: keputusan untuk periode τ pertama dari beberapa penyelesaian optimal masalah T -periode, juga optimal untuk setiap bagian dari masalah dengan lebih dari pada T periode. Akibatnya, tidak perlu untuk meramalkan data setelah periode T . Begitupun, jika T horizon peramalan untuk suatu horizon keputusan, maka akan berlaku untuk setiap integer T 0 ≥ T + 1. Artinya, perlu diperoleh horizon peramalan minimum untuk suatu horizon keputusan. Salah satu kajian awal dari horizon peramalan dalam manajemen operasi diajukan oleh Wagner and Whitin (1958) dan Wagner (2004) yang menganalisa masalah menetukan lot size terhadap waktu dengan adanya biaya persiapan (setup cost), biaya penyimpanan (holding cost) dan permintaan tak statsioner deterministik. Masalah ini dikenal sebagai dynamic lot size/DLS.
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
3 Adanya karakteristik tertentu yang dikaitkan dengan horizon peramalan sehingga isu tentang eksistensinya menjadi hal mendasar. Namun, untuk beberapa masalah, eksistensi tidak diperhatikan (Sethi and Bhaskara, 1985). Untuk model DLS dengan permintaan awal konstan, Chand et al. (1990) mengajukan eksistensi horizon peramalan (yaitu horizon peramalan minimum). Mereka mengkarakterisasi permintaan d1 , (d1 , d2 ), (d1 , d2, d3 ) merupakan horizon peramalan secara berturut-turut untuk T = 1, 2, 3. Akan tetapi untuk nilai T yang lebih besar, karakterisasi ini menjadi sangat ruwet. Pengertian horizon peramalan terdahulu tidak memberikan persyaratan pada data masa datang. Model DLS dari Wagner dan Whitin (1958) mengakomodasi kemungkinan bahwa permintaan masa datang mengambil nilai non-negatif. Secara praktis, bergantung dari persoalannya, karakteristik data masa datang dapat diberi tambahan spesifikasi. Pada kasus tertentu realisasi permintaan tidak dapat diasumsikan sembarang harga. Untuk mengetahui horizon-horizon peramalan, komunitas riset lebih sering menggunakan metoda Dynamic Programming dan Optimal Control.
Sedang-
kan Program Integer sebagai sebuah pendekatan penyelesaian untuk menentukan horizon-horizon peramalan sudah kurang disukai oleh mereka. Akan tetapi, kelebihan integer saat ini yaitu dengan adanya perkembangan komputasi terbaru yang cukup signifikan, sehingga keunggulan pada pemodelan dan struktur pendekatan program integer ini menciptakan suatu keadaan yang dapat digunakan dalam konteks horizon peramalan. Selain itu, untuk menetukan horizon peramalan sangat erat kaitannya dengan waktu, karena model Dynamic Lot Sizing memiliki horizon waktu hingga dan diskrit, maka dengan menggunakan Program Integer akan
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
4 diperoleh penyelesain eksak.
1.2 Perumusan Masalah Rencana produksi merupakan satu masalah klasik dimana seseorang harus memutuskan berapa besar produksi perlu dibuat dalam tiap periodenya sehingga permintaan memenuhi biaya minimal (Wagner and Whittin, 1958 dan Federgruen and Tzur, 1991). Keputusan produksi optimal pada periode saat ini sangat bergantung pada permintaan masa datang dan biaya yang tersedia. Hal ini akan bervariasi berdasarkan perubahan waktu yang dampaknya pada perubahan teknologi dan faktor-faktor di luar faktor ekonomi. Akibatnya permintaan dan biaya harus sudah diperkirakan dan produksi sudah direncanakan berdasarkan peramalan baik untuk horizon rencana jangka panjang, menengah ataupun pendek. Berdasarkan hal-hal yang telah dipaparkan di atas, rumusan masalah yang diajukan adalah bagaimanakah model Program Integer untuk menentukan horizonhorizon peramalan?.
1.3 Tujuan Penelitian Penelitian ini membahas model Program Integer pada masalah keputusan periode ganda untuk menentukan horizon-horizon peramalan dalam masalah keputusan dinamik (dynamic decision) dengan menggunakan pendekatan masalah dynamic lot size.
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
5 1.4 Kontribusi Penelitian ini memiliki kontribusi sebagai berikut:
1. Pada bidang statistika yaitu metoda pada peramalan sehingga kita dapat menentukan horizon waktu peramalan secara analitik. 2. Pada bidang aplikasi peramalan, seperti bidang ekonomi atau lainnya, para pemakai statistika peramalan dapat memperoleh periode waktu peramalan yang terbaik untuk meramalkan bisnis mereka.
1.5 Metodologi Penelitian ini adalah menentukan model DLS untuk memperlihatkan pemakaian Program Integer ketika memeriksa horizon-horizon peramalan. Penelitian ini diawali dengan konsep-konsep, kemudian dilanjutkan dengan,
1. Memformulasikan syarat cukup untuk horizon peramalan sebagai pertanyaanpertanyaan feasibilitas/optimalitas dalam program integer. 2. Mengkarakterisasikan syarat cukup dan perlu untuk horizon peramalan sebagai pertanyaan-pertanyaan feasibilitas/optimalitas dalam Program Integer. 3. Memformulasikan karakterisasi tipe baru dari horizon-horizon peramalan minimal dengan mengasumsikan bahwa permintaan-permintaan masa datang bernilai integer.
Dibagian akhir disajikan kesimpulan.
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
BAB 2 TINJAUAN PUSTAKA
2.1 Perkembangan Kajian Horizon Peramalan Salah satu kajian tentang horizon peramalan yang paling awal dilakukan oleh Wagner and Whitin (1958) dengan mempublikasikan tulisan mereka yang berjudul the ”Dynamic Version of the Economic Lot Size Model ”. Dalam tulisan tersebut mereka mengajukan masalah yang dimisalkan dalam waktu O(n2 ) di mana n panjang horizon perencanaan dan menggunakan masalah menentukan lot size atas waktu terhadap biaya persiapan, biaya penyimpanan, dan permintaan-permintan yang tidak stationer deterministik yang dikenal sebagai model economic lot-sizing (ELS). Walaupun algoritma yang mereka buat memberikan penyelesaian optimal tetapi sulit dimengerti karena sangat rumit. Sejak saat itu dilakukan berbagai riset dalam masalah ini supaya implementasinya menjadi efisien (Lundin and Morton, 1975 dan Saydam and McKnew, 1987), tetapi hasil yang diperoleh tidak lebih baik dari sebelumnya. Selanjutnya riset difokuskan pada rancangan dan analisa secara heuristic (Silver and Meal, 1973 dan Axsater, 1982 ). Akibatnya model ini menjadi salah satu yang paling diminati dalam masalah rencana produksi. Para peneliti sudah secara ekstensif mempelajarinya, survey dan diskusi dilakukan oleh Federgruen and Tzur (1991). Hanya dalam tiga dekade, yaitu pada awal tahun 1990-an model ini sudah terkenal karena dapat menyelesaikan masalah waktu O(n2 ) untuk n-periode. Kemudian, Federgruen
6 Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
7 and Tzur (1991) dan Aggarwal and Park (1993) masing-masing sudah memperlihatkan algoritma yang baik untuk menyelesaikan masalah O(nlogn) secara umum, khususnya untuk masalah struktur biaya. Beberapa peneliti juga sudah menggunakan algoritma untuk mencari horizon peramalan, seperti Wagner and Whitin (1958), Lundin and Morton (1975), Chand and Morton (1986), dan Chand et al. (1990). Secara khusus Wagelmans et al. (1992) membuat algoritma mundur (backward algorithm) sedangkan Federgruen and Tzur (1991) memilih algoritma maju (forward algorithm), dan Aggarwal and Park (1993) menggunakan prosedur rekursif (recursive). Chand et al. (1990) mempelajari syarat eksistensi horizon peramalan. Chand and Morton (1986) mengajukan algorithma untuk mencari horizon peramalan minimal. Federgruen and Tzur (1994) membahas horizon-horizon peramalan termasuk horizon peramalan minimal, mereka masing-masing juga sudah mengembangkan algoritma untuk mencari batas atas errornya. Thompson and Sethi (1980) dan Morton (1978a) mengasumsikan biaya-biaya berbentuk linear stationer. Kunreuther and Morton (1973) mengasumsikan biaya linear non-stationary sedangkan Kunreuther and Morton (1974) dan Morton (1978b), mengasumsikan biaya-biaya convex stationer. Masalah biaya produksi fixed-plus-linear dan biaya penyimpanan linear, dipelajari secara ekstensif oleh Chand and Morton (1986), Chand et al. (1990), Federgruen and Tzur (1994), dan Chand et al. (2002). Sedangkan, Federgruen and Tzur (1991) dan Wagelmans et al. (1992) membahas pemakaian komputer untuk penyelesaian masalah horizon peramalan.
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
8 Konsep horizon peramalan sudah dikembangkan ke variasi masalah keputusan dinamik yang lebih luas; seperti perluasan kapasitas (Rajagopalan, 1992), manajemen inventaris (Chand and Morton, 1986 dan Federgruen and Tzur, 1994), penempatan pabrik (Bastian and Volkmer, 1992), Daskin et al.(1992) rencanaan produksi (Johnson and McClain, 1978; Kleindorfer and Lieber, 1979; Aronson et al., 1984). Chand et al. (2002) menulis bibliografi yang diklasifikasi ekstensif untuk literature horizon peramalan.
2.2
Metode Yang Digunakan Dalam Dynamic Lot Sizing Seperti sudah dijelaskan, masalah DLS merupakan masalah yang sangat
terkenal dalam manajemen inventaris. Jika diberikan permintaan berbentuk deterministik untuk horizon perencanaan berhingga dan diskrit, selanjutnya dicari rencana produksi yang memenuhi permintaan dan total biaya minimum. Masalah seperti ini dapat diselesaikan dengan menggunakan polynomial time dan heuristic karena permasalah seperti algoritma dalam Wagner and Within (1958) sangat sulit dipahami sehingga sangat jarang dipakai oleh para praktisi. Ada dua metoda yang secara umum dipakai mengukur hasil secara heuristic. Pertama, metoda-metoda empiris (empirical methods) di mana kajian dilakukan menggunakan simulasi (Baker, 1989 dan Simson, 2001). Kedua, metoda-metoda analitik yang dapat dirubah ke probabilistik dan analisa kasus terburuk (worst case). Metode probabilistik menganalisa kinerja heuristic sedangkan analisa kasus terburuk untuk mencari batas relatif heuristic. (Axsater, 1982) menganalisa kasus terburuk dari hasil beberapa aturan lot size yang spesifik
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
9 Selanjutnya, Ho et al. (2006) mengembangkan dua robust LPC (Least Period Cost) berdasarkan constructif heuristic, sedangkan Federgruen et al. (2007) mengembangkan dan menganalisa progresif interval heuristic class untuk menyelesaikan masalah JS (joint setup cost) dan JIS (joint and item-dependent setup cost) atas interval waktu yang panjang. Chaudhry et al. (1993) memformulasikan Program Integer campuran (mixed Integer Programming), sedangkan Jayaraman et al. (1999) menerapkan Program Integer campuran untuk model periode tunggal untuk menyeleksi suplier. Dawande et al. (2007) menyajikan investigasi secara struktural dan komputasional kelas horizon peramalan lemah yaitu horizon peramalan dengan mengasumsikan permintaan-permintaan masa datang sebagai kelipatan bilangan real. Mereka juga menyajikan syarat horizon peramalan permintaan bernilai diskrit yang merupakan horizon peramalan permintaan bernilai kontinu.
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
BAB 3 LANDASAN TEORI
3.1 Pengertian Program Linear Program Linear merupakan metode matematika untuk mengalokasikan sumber daya yang biasanya terbatas supaya mencapai hasil yang optimal, misalnya memaksimumkan keuntungan atau meminimumkan biaya. Oleh karena itu program linear banyak dipergunakan dalam menyelesaikan masalah-masalah, antara lain ekonomi dan industri. Para pengambil keputusan sering menghadapi masalah dalam menentukan alokasi sumber daya yang terbatas karena mereka menginginkan hasil yang seoptimal mungkin. Dengan menggunakan model program linear, para pengambil keputusan dapat memprediksi hasil yang akan diperoleh. Bentuk umum model program linear adalah: max(min)Z =
X
cj xj
kendala X
aij xj (≤, =, ≥)bi, (i = 1, 2, ..., m) xj ≥ 0, (j = 1, 2, ..., n)
di mana xj : banyaknya kegiatan j(j = 1, 2, , n) Z
: nilai fungsi tujuan
cj : sumber per-unit kegiatan, untuk masalah memaksimalkan cj menunjukkan 10 Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
11 keuntungan per-unit perkegiatan, sedangkan untuk kasus meminimalkan cj menunjukkan biaya perunit perkegiatan. b : besarnya sumber daya i(i = 1, 2, , m) aij : banyaknya sumber daya i yang dipakai sumber daya j.
3.2 Pengertian Program Integer Pada masalah Program Linear penyelesaian optimalnya dapat berupa bilangan real yang berarti penyelesaian bisa berupa bilangan pecahan. Untuk penyelesaian yang berbentuk pecahan jika mengalami pembulatan ke integer terdekat maka hasil yang diperoleh bisa menyimpang jauh dari yang diharapkan. Akan tetapi banyak permasalahan di kehidupan nyata yang memerlukan penyelesaian variabel keputusannya berupa integer sehingga harus dicari model penyelesaian masalah sehingga diperoleh penyelesaian integer yang optimum. Program Integer merupakan pengembangan dari Program Linear di mana beberapa atau semua variabel keputusannya harus berupa integer. Jika hanya sebagian variabel keputusannya merupakan integer maka disebut Program Integer campuran (mixed Integer Programming). Jika semua variabel keputusannya bernilai integer disebut Program Integer murni (pure Integer Programming). Sedangkan Program Integer 0−1 merupakan bentuk Program Integer di mana semua variabel keputusannya harus bernilai integer 0 atau 1 (binary). Bentuk umum model Program Integer adalah: max(min)Z =
X
cj xj
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
12 kendala X
aij xj (≤, =, ≥)bi, (i = 1, 2, ..., m) xj ≥ 0, (j = 1, 2, ..., n)
xj bernilai integer untuk beberapa atau semua j. Bentuk umum model Program Integer 0-1 adalah: max(min)Z =
X
cj xj
kendala X
aij xj (≤, =, ≥)bi, (i = 1, 2, ..., m)
xj = 0 atau xj = 1, (j = 1, 2, ..., n)
3.3 Model Dynamic Lot-Sizing Dynamic Lot-Sizing/DLS adalah rencana urutan manufaktur/produksi atas banyaknya periode masa datang di mana permintaannya berbentuk dinamik dan deterministik. Seperti masalah menentukan horizon-horizon peramalan standar model lot size dengan variasi waktu permintaan deterministik dan menentukan lot size produksi dengan biaya persiapan dan biaya penyimpanan untuk pemeliharaan inventaris. Berikut ini diberikan formulasi masalah model DLS berdasarkan Wagner and Whittin (1958):
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
13 Masalah DLS untuk T -periode (Masalah DLS-T ): minimum
T X
[kXj + hIj ]
j=1
kendala Qj ≤ (
t X
dr )Xj
r=j
Ij+1 = Ij + Qj+1 − dj+1 Io = 0 IT = 0 Ij , Qj ≥ 0 Xj ∈ {0, 1} di mana T = masalah horizon, yaitu banyaknya periode. k = biaya persiapan (setup cost) untuk produksi. h = biaya penyimpanan (holding cost) per-unit per-periode. dj = permintaan pada periode j, j = 1, 2, ..., T. kuantitas produksi (jumlah permintaan) pada periode j, j = 1, 2, ..., T Qj = 1 jika persiapan diperlukan pada periode j; Xj = 0 untuk lainnya ; j = 1, 2, ..., T
Ij = inventaris pada akhir periode j, j = 1, 2, , T
Karena inventaris awal adalah nol, dan tidak diizinkan adanya penundaan (backlog) maka produksi harus terjadi pada periode pertama dalam setiap periode produksi.
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
BAB 4 PEMBAHASAN
Dalam bab ini akan dibahas formulasi Program Integer yang dipakai untuk mengidentifikasi horizon peramalan yang memenuhi syarat-syarat tertentu. Sebelum masuk ke pembahasan, terlebih dahulu akan diberikan definisi yang akan dipergunakan dalam bab ini. Definisi Misalkan (QF1 )∗ adalah kuantitas produksi periode pertama pada penyelesaian optimum dari masalah F -periode dengan permintaan di untuk periode i, i = 1, 2, ..., F . Periode F adalah horizon peramalan untuk setiap N > F dan semua vector permintaan di , i = F + 1, ..., N , maka ada paling sedikit satu penyelesaian optimal dengan (QF1 )∗ sebagai kuantitas produksi periode pertama. Banyaknya periode permintaan yang dipenuhi oleh (QF1 )∗ adalah horizon keputusan (decision horizon). Selanjutnya akan diperlihatkan formulasi Program Integer untuk mengidentifikasi horizon peramalan yang memenuhi syarat cukup dari Lundin and Morton (1975).
4.1 Syarat Cukup dari Lundin and Morton (1975) Periode F adalah horizon peramalan jika penyelesaian optimal dengan kuantitas produksi periode pertama, (QF1 )∗ untuk masalah F -periode, mempunyai persiapan akhir dalam periode L memenuhi kondisi: setiap masalah S-periode dengan L − 1 ≤ S ≤ F mempunyai penyelesaian optimal dengan kuantitas produksi pe14 Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
15 riode pertama sama dengan (QF1 )∗ . Periode L disebut titik produksi akhir (last production point), periode L − 1 merupakan titik akhir di mana besarnya inventaris adalah nol, disebut titik regenerasi akhir (last regeneration point). Himpunan periode dari L − 1 sampai F disebut himpunan regenerasi (regeneration set). Wagner and Whitin (1958) memperlihatkan bahwa sebarang masalah N -periode dengan N ≥ F + 1 mempunyai titik produksi dalam L, , F +1. Jadi, jika setiap masalah S-periode dengan L − 1 ≤ S ≤ F mempunyai penyelesaian optimal dengan kuantitas produksi periode pertama sama dengan (QF1 )∗, maka (QF1 )∗ adalah produksi periode pertama yang optimal untuk setiap masalah N-periode di mana N ≥ F + 1. Memformulasikan Program Integer untuk menentukan horizon waktu T yang memenuhi syarat cukup di atas harus ditentukan dahulu biaya optimal untuk masalah dengan horizon perencanaan dalam interval dari 1 sampai T . Sehingga diperlukan notasi tambahan berikut: (Qtj ) = Kuantitas produksi dalam periode j pada masalah t-periode. 1 jika persiapan diperlukan dalam periode j untuk masalah t-periode; t Xj = 0 lainnya Ijt = Inventaris yang di bawa dari periode j ke j + 1 pada masalah t-periode. 1 jika periode j himpunan regenerasi dari masalah T -periode; T Rj = 0 lainnya Mt = Biaya optimal untuk masalah t-periode.
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
16 Masalah DLS untuk syarat cukup T (Masalah DLS-T-SC). Cari penyelesaian layak untuk kendala-kendala berikut: t X
kXjt
+
j=1
(
t X
t X
hIjt = Mt , 1 ≤ t ≤ T
(4.1)
j=1
dr )Xjt ≥ Qtj , 1 ≤ j ≤ t, 1 ≤ t ≤ T
(4.2)
r=j t Ijt + Qtj+1 − dtj+1 − Ij+1 = 0,
0 ≤ j ≤ t − 1, 1 ≤ t ≤ T
(4.3)
Kendala (4.1), (4.2), dan (4.3) untuk memastikan bahwa yang dimisalkan hanya penyelesaian optimal. Biaya optimal Mt untuk t = 1, , T diperoleh dengan menyelesaikan hubungan masalah standar DLS t-periode. RTT = 1
(4.4)
RTT −1 = 1
(4.5)
Kendala (4.4) dan (4.5) menjamin bahwa periode T dan T − 1 selalu dalam himpunan regenerasi dari masalah T -periode.
1−
T 1 X T ≤ X , 1 ≤j ≤T −2 T r=j+2 r
RTj
(4.6)
Kendala (4.6) untuk menentukan apakah periode selain T dan T − 1 berada dalam himpunan regenerasi.
X
≤( Qt1 − Qt+1 1
dr )(1 − RTt ), 1 ≤ t ≤ T − 1
(4.7)
dr )(1 − RTt ), 1 ≤ t ≤ T − 1
(4.8)
r=1
Qt1
−
Qt+1 1
≥(
T X r=1
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
17 I0t = 0 Itt = 0 Ijt, Qtj , Xjt ≥ 0 XjT , RTj ∈ {0, 1} Kendala (4.7) dan (4.8) menekankan bahwa, untuk horizon peramalan, kuantitas produksi periode pertama sama keseluruhannya degan untuk horizon perencanaan dalam himpunan regenerasi. Selanjutnya, diformulasikan Program Integer untuk mengidentifikasi horizon perencanaan terkecil yang memenuhi syarat cukup untuk horizon peramalan. Asumsikan bahwa batas atas yaitu T u diketahui berada pada panjang horizon peramalan. Didefinisikan notasi tambahan berikut: 1 jika peroda j berada dalam himpunan regenerasi dari masalah t-periods; t Rj = 0 untuk lainnya 1 jika t adalah horizon peramalan minimal; Wt = 0 untuk lainnya 1 jika t adalah horizon peramalan minimal dan j anggota himpunan regenerasi dari masalah t-periode; Yjt = 0 untuk lainnya
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
18 Masalah DLS untuk identifikasi horizon perencanaan terkecil yang memenuhi syarat cukup untuk horizon peramalan (Masalah-MT-SC). Cari penyelesaian optimal untuk Program Integer berikut :
u
minimum
T X
kWk
k=1
kendala t X
kXjt
j=1
(
t X
+
t X
hIjt = Mt ,
1 ≤ t ≤ Tu
(4.9)
j=1
dr )Xjt ≥ Qtj , 1 ≤ j ≤ t, 1 ≤ t ≤ T u
(4.10)
r=j t = 0, Ijt + Qtj+1 − dtj+1 − Ij+1
Rtt = 1,
1 ≤ t ≤ Tu
Rtt−1 = 1, 1−
Rtj
0 ≤ j ≤ t − 1, 1 ≤ t ≤ T u
1 ≤ t ≤ Tu
t 1 X t ≤ u X , 1 ≤j ≤ t−2 T r=j+2 r
(4.11) (4.12) (4.13) (4.14)
Fungsi objektif untuk meminimumkan panjang horizon peramalan. Kendala (4.9)-(4.14) sama dengan kendala pada formulasi sebelumnya (kendala (4.1)-(4.6)). u
T X
Wt = 1
(4.15)
t=1
Kendala (4.15) untuk menjamin bahwa hanya satu horizon perencanaan yang dipilih sebagai horizon peramalan. Yjt ≤ 0.5Rtj + 0.5Wt , 1 ≤ j ≤ t, 1 ≤ t ≤ T u Yjt ≥ Rtj + Wt − 1,
1 ≤ j ≤ t, 1 ≤ t ≤ T u
(4.16) (4.17)
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
19 Kendala (4.16) dan (4.17) adalah linearisasi dari kendala Yjt = Rtj Wt . u
Qt1
−
Qt+1 1
≤(
T X
dr )(1 − Yjt ),
1 ≤ j ≤ t, 1 ≤ t ≤ T u − 1
(4.18)
r=1 u
Qt1
−
Qt+1 1
≥ −(
T X
dr )(1 − Yjt ), 1 ≤ j ≤ t, 1 ≤ t ≤ T u − 1
(4.19)
r=1
Iot = 0,
1 ≤ t ≤ Tu
Itt = 0,
1 ≤ t ≤ Tu
Ijt, Qtj , Xjt ≥ 0 Xjt , Rtj , Yjt ∈ {0, 1} Kendala (4.18) dan (4.19) untuk memeriksa apakah semua anggota himpunan regenerasi mempunyai kuantitas produksi periode pertama yang sama.
4.2 Syarat Perlu dan Cukup dari Chand and Morton (1986) Chand dan Morton (1986) yang pertama kali mengembangkan prosedur untuk menentukan horizon peramalan minimal. Mereka menggunakan pendekatan yang dirancang dengan meminimisasi himpunan regenerasi yang didefinisikan oleh Lundin dan Morton (1975). Lundin dan Morton (1975) mendefinisikan himpunan regenerasi terdiri dari semua periode yaitu dari periode sebelum titik produksi terakhir sampai periode terakhir, yaitu dari periode L − 1 sampai T . Chand dan Morton (1986) mengetahui bahwa himpunan regenerasi actual, yaitu himpunan periode-periode yang secara potensial dapat menjadi titik regenerasi pada masalah horizon yang lebih panjang, sebenarnya bisa jauh lebih pendek dari yang didefinisikan pada Lundin
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
20 dan Morton (1975). Mereka mendefinisikan konsep himpunan regenerasi minimal dan mengembangkan prosedur untuk mengidentifikasinya. Selanjutnya tinggal diperiksa apakah semua horizon perencanaan di dalamnya mempunyai kuantitas produksi perioda pertama persekutuan yang optimal atau tidak. Berikut ini empat langkah yang mengikuti prosedur Chand and Morton (1986): Langkah dari 1 sampai 3 untuk mengidentifikasi himpunan regenerasi minimal, yang diberi notasi R(T ).
Langkah 1: Misalkan MT s adalah biaya optimal dari masalah T -periode dengan tambahan pembatasan bahwa periode s + 1 adalah titik produksi akhir. Untuk menghitung biaya ini digunakan Program Integer berikut:
Masalah DLS untuk menghitung biaya optimal masalah T -periode (Masalah DLS-T MTS). minimum
T X
(kXj + hIj )
j=1
kendala (
T X
dr )Xj ≥ Qj , 1 ≤ j ≤ T
r=j
Ij + Qj+1 − dj+1 − Ij+1 = 0, Xs+1 = 1 T X
Xr = 0
0 ≤ j ≤T −1 (4.20) (4.21)
r=s+2
Io = 0
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
21 IT = 0 Ij , Qj ≥ 0,
1≤j ≤T
Xj ∈ {0, 1},
1≤j ≤T
Formulasi ini sama dengan Masalah DLS untuk T -periode, kecuali untuk kendala (4.20) dan (4.21). Kedua syarat tersebut untuk menjamin bahwa persiapan terakhir berada pada periode s + 1. Jadi periode s + 1 adalah titik akhir produksi. Fungsi objektif adalah biaya terendah untuk masalah T -periode dengan pembatasan tambahan yaitu s + 1 yang merupakan titik akhir produksi.
Langkah 2: Mengidentifikasi periode maksimum s sehingga (s + 1) merupakan titik akhir produksi (yaitu s berkorespondensi dengan nilai maksimum L(T − 1) atas semua penyelesaian optimalnya) untuk masalah T -periode dengan menggunakanProgram Integer berikut. Didefinisikan : 1 jika periode s + 1 titik produksi akhir yang maksimum atas semua penyelesaian dari masalah T -periode; Rs = 0 untuk lainnya Masalah DLS untuk identifikasi periode maksimum pada masalah T periode (Masalah DLS-T MLT). maksimum
T −1 X
sRs
s=0
kendala MT ≥ MTs Rs , 0 ≤ s ≤ T − 1 T −1 X
Rs = 1
(4.22) (4.23)
s=0
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
22 Rs ∈ {0, 1},
0≤s≤T −1
di mana MT ≤ Mts , s = 0, ..., T − 1. Kebalikan kendala (4.22) bersama dengan kendala (4.23) dan fungsi objektif menjamin pemilihan bahwa hanya itulah penyelesaian optimal (dari masalah T -periode) yang mempunyai titik regenerasi akhirnya maksimum. Masalah DLS-T MLT selalu layak maka dimisalkan l ∗ (T ) adalah nilai penyelesaian optimumnya dan R(T ) = {l ∗ (T )}.
Langkah 3: Hitung ratio Rql∗ dan RTl∗ sebagai berikut : Rql∗ =
MTq − MTl∗ , (q − l∗(T ))h
l∗(T ) < q ≤ T − 1 ∗
RTl∗
MT + k − MTl = (T − l∗(T ))h
Cari v, dimana v adalah periode terbesar yang memenuhi persyaratan:
min
Rvl∗ =
∗
Rql∗
q ∈ {l (T ) + 1, ..., T }
Masukkan v ke dalam himpunan regenerasi, sehingga R(T ) = R(T ) ∪ {v}. Jika v ≤ T − 1 maka himpunan l∗(T ) = v dan kembali ke langkah 3. Cara lainnya, tambahkan T ke himpunan regenerasi, sehingga R(T ) = R(T ) ∪ {v} dan proses selanjutnya masuk ke langkah 4. Langkah terakhir, untuk memeriksa horizon-horizon perencanaan dalam R(T ) mempunyai kuantitas produksi periode pertama persekutuan berupa satu penyelesaian optimal. Dimulai dengan memisalkan himpunan R(T ) = φ.
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
23 Langkah 4: Periksa apakah semua horizon perencanaan yang berada dalam himpunan regenerasi minimal R(T ) mempunyai kuantitas produksi periode pertama persekutuan paling sedikit satu penyelesaian optimal.
Masalah DLS untuk himpunan regenerasi minimal T (Masalah DLST MRT): Cari penyelesaian layak untuk himpunan kendala-kendala berikut: t X j=1
(
t X
kXjt +
t X
hIjt = Mt , t ∈ R(T )
j=1
dr )Xjt ≥ Qtj ,
1 ≤ j ≤ t, t ∈ R(T )
r=j t = 0, 0 ≤ j ≤ t − 1, t ∈ R(T ) Ijt + Qtj+1 − dj+1 − Ij+1
Tiga kendala ini sama dengan tiga kendala pertama pada Masalah DLST-SC, kecuali kendala-kendala tersebut dikenakan hanya pada horizon-horizon perencanaan dalam himpunan regenerasi minimal R(T ). t = 0, 0 ≤ j ≤ t − 1, t ∈ R(T ) Ijt + Qtj+1 − dj+1 − Ij+1
Qt1 − Qs1 = 0, s, t ∈ R(T ), s 6= t I0t = 0,
t ∈ R(T )
Itt = 0,
t ∈ R(T )
(4.24)
Ijt, Qtj ≥ 0, 1 ≤ j ≤ t, t ∈ R(T ) Xjt ∈ {0, 1},
1 ≤ j ≤ t, t ∈ R(T )
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
24 Kendala (4.24) untuk memeriksa eksistensi kuantitas produksi periode pertama persekutuan untuk semua horizon perencanaan dalam himpunan regenerasi minimal. Jika diberikan nilai T , maka langkah 1-4 menentukan apakah T horizon peramalan atau bukan. Horizon peramalan minimal merupakan nilai terkecil dari T , untuk 1 ≤ T ≤ T u di mana Masalah DLS-T-MRT di atas mempunyai penyelesaian layak.
4.3 Horizon Peramalan Minimal Karakterisasi horizon peramalan di atas tanpa adanya pengasumsian permintaan masa datang. Akan tetapi, pada kenyataanya masalah yang sedang diselidiki sering memerlukan penambahan karakteristik yang spesifik untuk permintaan masa datang. Horizon peramalan yang diperoleh dengan menyertakan persyaratan tambahan dikenal sebagai horizon peramalan lemah (weak) ( Bes and Sethi, 1988). Pada bagian ini diselidiki horizon peramalan lemah yaitu horizon peramalan minimal dengan mengasumsikan permintaan masa datang bernilai integer. Integralitas permintaan sudah biasa dalam kenyataannya oleh karena itu, perlu memasukkan karakteristik. Kemudian, untuk sebarang masalah horizon berhingga, tanpa menghilangkan keumumannya, diasumsikan permintaan-permintaan bernilai integer sebagai permintaan-permintaan bernilai rasional. Walaupun hal ini tidak sepenuhnya seperti pembatasan untuk pengasumsian permintaan bernilai integer. Hasilnya memperlihatkan bahwa panjang horizon peramalan minimal dengan permintaan masa datang bernilai integer, secara signifikan, sering lebih
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
25 pendek dari pada tanpa pengasumsian ini. Pengurangan panjang horizon peramalan minimal akan sangat menguntungkan secara praktis. Untuk menghitung horizon peramalan minimalnya, pertama diperlukan syarat perlu dan cukup untuk periode T menjadi horizon peramalan dengan asumsi ini. Seperti pada bagian sebelumnya, permintan pada perioda pertama T diketahui dan diasumsikan secara berturut-turut d1 , d2 , ..., dT . Misalkan P1 (T + 1, αT +1 ) adalah himpunan kuantitas produksi periode pertama yang optimal untuk masalah (T + 1)-periode dengan permintaan untuk periode T + 1 sebesar αT +1. Berikutnya hasil yang dibuktikan oleh Chand and Morton (1982): Rencana produksi optimal pada perioda pertama T dari sebarang masalah Nperioda dengan N ≥ T +1 dapat diperoleh dengan menyelesaikan masalah (T +1)periode dengan permintaan-permintaan d1 , d2 , ..., dT dalam periode pertama T dan permintaan yang terpilih yaitu αT +1 dalam periode T + 1. Hasil ini dipenuhi untuk sebarang permintaan masa datang (bernilai real). Untuk permintaan yang bernilai integer, diperlukan αT +1 yang juga bernilai integer, sehingga jika αT +1 > [ hk ], maka P1 (T + 1, αT +1 ) = P1 (T + 1, 0). Syarat perlu dan cukup untuk T merupakan horizon peramalan diperlihatkan berikut ini. Teorema : Mengasumsikan T adalah horizon peramalan dengan permintaan masa datang bernilai integer jika dan hanya jika ∩αT +1 )∈{0,1,2,...,[ k ] = P1 (T + h
1, αT +1 ) 6= φ Bukti: Syarat perlu: Jika T adalah horizon peramalan dengan mengasumsikan permintaan masa datang bernilai integer maka ∩αT +1 )∈{0,1,2,...,[ k ] = P1 (T + 1, αT +1 ) 6= h
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
26 φ. Untuk membuktikan syarat perlu digunakan kontradiksi. Jika ∩αT +1 )∈{0,1,2,...,[ k ] = h
P1 (T + 1, αT +1 ) = φ maka jelas T bukan horizon peramalan. Karena tidak ada keputusan periode pertama optimal persekutuan untuk permintaan-permintaan 0, 1, 2, ..., [ hk ] dalam periode T + 1. Syarat cukup: Jika ∩αT +1 )∈{0,1,2,...,[ k ] = P1 (T + 1, αT +1 ) 6= φ maka T adalah h
adalah horizon peramalan. Asumsikan ∩αT +1 )∈{0,1,2,...,[ k ] = P1 (T + 1, αT +1 ) 6= φ. h
Sedangkan diketahui bahwa setiap bagian masalah N -periode dengan N ≥ T + 1 mempunyai periode produksi pertama sama dengan masalah (T + 1)-periode dengan permintaan terpilih αT +1 (Chand dan Morton, 1986). Kemudian, dimisalkan dua kasus berikut: (1) jika αT +1 > [ hk ] maka P1 (T + 1, αT +1 ) = P1 (T + 1, 0), maka T adalah horizon peramalan. (2) αT +1 ≤ [ hk ] hasilnya mengikuti hipotesis. Diberikan nilai T , berikut ini formulasi Program Integer untuk menguji horizon peramalannya. Beberapa notasi tambahan yang diperlukan sebagai berikut: MT +1 (α) = Nilai fungsi objektif optimal untuk masalah (T + 1)-periode ketika permintaan dalam periode T + 1 adalah α. Dengan catatan bahwa α = 0 secara esensial adalah masalah T periode. Λ
Xjα
Qαj
= Himpunan permintaan untuk periode T + 1, yang diberi indeks α, dimana Λ ∈ {1, 2, ... kh 1 jika setup diperlukan pada periode j dalam masalah periode T + 1 dengan permintaan α; = 0 untuk lainnya = Kuantitas produksi pada periode j dalam masalah periode T + 1 dengan permintaan α.
Ijα
= Inventaris yang dibawa dari periode j ke j + 1 dalam masalah dengan
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
27
periode T + 1 dan permintaan α.
Masalah DLS untuk menguji T sebagai horizon peramalan (Masalah DLS-T-NSC). Cari penyelesaian layak untuk himpunan kendala-kendala berikut: T +1 X
kXjα
j=1
+
T +1 X
hIjα = MT +1 (α),
α∈Λ
(4.25)
j=1
T X j=1
kXjα +
T X
hIjα = MT (α), α = 0
(4.26)
j=1
Kendala (4.25) dan (4.26) untuk menjamin bahwa hanya penyelesaian itulah yang sama dengan biaya optimal. (
T +1 X
dr )Xjα ≥ Qαj,
1 ≤ j ≤ T + 1, α ∈ Λ
(4.27)
T X dr )Xjα ≥ Qαj, (
1 ≤ j ≤ T, α = 0
(4.28)
r=j
r=j
Kendala (4.27) dan (4.28) menekankan pengendalian standar bahwa produksi tidak dapat terjadi tanpa persiapan. α = 0, Ijα + Qαj+1 − dj+1 − Ij+1
0 ≤ j ≤ T − 1, α ∈ Λ ∪ {0}
α = 0, j = T, α ∈ Λ Ijα + Qαj+1 − α − Ij+1
(4.29) (4.30)
Kendala (4.29) dan (4.30) menekankan konservasi aliran material. = 0, Qα1 − Qα+1 1 I0α = 0,
α ∈ 0, 1, 2, , bk/hc − 1
(4.31)
α ∈ Λ ∪ {0}
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
28 ITα+1 = 0, Ijα , Qαj ≥ 0, Ijα , Qαj ≥ 0, Xjα ∈ {0, 1},
α ∈ Λ ∪ {0}
1 ≤ j ≤ T + 1, α ∈ Λ 1 ≤ j ≤ T, α = 0 1 ≤ j ≤ T + 1, α ∈ Λ
Kendala (4.31) menyatakan bahwa semua nilai permintaan, α ∈ Λ ∪ {0} mempunyai kuantitas produksi periode pertama optimal persekutuan. Horizon peramalan minimal adalah nilai terkecil T dengan 1 ≤ T ≤ T u di mana formula di atas mempunyai penyelesaian layak.
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
BAB 5 KESIMPULAN
5.1 Kesimpulan Penelitian ini membahas model Program Integer untuk menentukan horizon waktu peramalan dalam menyelesaikan masalah Dynamic Lot Sizing/DLS. Sebagai pendekatan penyelesaian untuk menghitung horizon-horizon peramalan Program Integer sudah terabaikan oleh komunitas riset akan tetapi, pemodelan dan kelebihan-kelebihan secara struktur dari pendekatan ini beserta perkembangan secara komputasi dalam Program Integer menciptakan keadaan sehingga pendekatan ini tetap digunakan dalam konteks horizon peramalan. Selain itu, menetukan horizon peramalan erat kaitannya dengan waktu, sehingga dengan menggunakan Program Integer akan diperoleh penyelesain eksak. Adapun kesimpulkan yang dapat diambil dari hasil penelitian ini adalah sebagai berikut: 1. Diberikan permintaan-permintaan untuk perioda-perioda pertama T . T disebut horizon peramalan untuk horizon keputusan yang diberikan, untuk semua bagian dari masalah yang lebih dari T periode, paling sedikit ada satu penyelesaian optimal dengan keputusan-keputusan yang identik untuk horizon keputusan dari penyelesaian optimal masalah T -periode. 2. Karakterisasi syarat cukup dari Lundin and Morton (1975) juga syarat perlu dan cukup dari Chand and Morton (1986) yang dipakai untuk menyelidiki eksistensi T yang bernilai integer menjadi horizon peramalan. 29 Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
30 3. Karakterisasi syarat perlu dan cukup untuk T yang bernilai integer menjadi horizon peramalan minimal ketika permintaan-permintaan masa depan bernilai diskrit.
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
DAFTAR PUSTAKA
Aggarwal, A. and J.K. Park (1993) Improved algorithms for economic lot-size problems, Operations Research,Vol. 41, No. 3 : 549-571. Aronson, J. E., Morton, T. E., and Thompson, G. L. (1984) A Forward Algorithm and Planning Horizon Procedure for the Production Smoothing Problems Without Inventory, European Journal of Operational Research, Vol. 15 : 348-365. Axsater, S. (1982) Worst Case Performance of Lot-Sizing Heuristics. European Journal of Operational Research Vol. 9 : 399-343. Baker, K. R., (1989) Lot-sizing procedures and a standard data set: A reconciliation of the literature, Journal of Manufacturing and Operations Management, Vol. 2 : 199-221. Bes, C., Sethi, S. (1988) Concepts of forecast and decision horizons: applications to dynamic stochastic optimization problems, Mathematics of Operations Research, Vol. 13, No. 2 : 295-310. Bastian, M. and Volkmer, M. (1992) A Perfect Forward Procedure for a Single Facility Dynamic Location Relocation Problem, Operations Research Letters, Vol. 12 : 11-16. Chand, S., Hsu, V.N., Sethi, S.P. (2002) Forecast, Solution, and Rolling Horizons in Operations Management Problems: A Classified Bibliography, Manufacturing & Service Operations Management, Vol. 4, No. 1 : 25-43. Chand, S., and Morton, E. (1986) Minimal Forecast Horizon Procedures for Dynamic Lot Size Models, Naval Research Logistics Quarterly, Vol. 33 : 111-121. Chand, S., Sethi, S. P., and Proth, J. M. (1990) Existence of Forecast Horizon in Undiscounted Discrete-Time Lot Size Models, Operations Research, Vol. 38, No. 5 : 884-892. Daskin, M. S., Hopp, W. J., and Medina, B. (1992) Forecast Horizons and Dynamic Facility Location Planning, Annals of Operations Research, Vol. 28 : 125-151. Dawande, M., Gavirneni S., Naranpanwe S., and Sethi S.P. (2007) Forecast Horizons For a Class of DLS Problem Under Discrete Demand, Operations Research, Vol. 55. No. 4. Federgruen, A. and M. Tzur (1991) A simple forward algorithm to solve general dynamic lot sizing models with n periods in O(n log n) or O(n) time, Management Science, Vol. 37. No. 8 : 909-925. Federgruen, A. and Tzur, M. (1994) Minimum Forecast Horizons and a NewPlanning Procedure for the General Dynamic Lot Sizing Model: Nervousness Revisited, Operations Research, , Vol. 42. No. 3 : 456-468.
31 Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
32 Federgruen, A., Meissner, J., Tzur, M. (2007) Progressive Interval Heuristics for Multi-Item Capacitated Lot-Sizing Problems, Operation Research, Vol. 55, No. 3 : 490502 Ho, J. C., Y-L. Chang and A. O. Solis, (2006) Two modifications of the least cost per period heuristic for dynamic lot-sizing, Operational Research Society, Vol. 57 : 1005-1013. Jayaraman, V., R. Srivastava, and W.C. Benton (1999) Supplier selection and order quantity allocation: a comprehensive model, The Journal of Supply Chain Management : 50-58. Johnson, R. E. and McClain, J. O. (1978) On Further Results on Planning Horizons in the Production Smoothing Problem, Management Science, Vol. 24 :17741776. Kleindorfer, P. and Leiber, Z. (1979) Algorithms and Planning Horizon Results for Production Planning Problems with Separable Costs, Operations Research, Vol. 27 : 875-887. Kunreuther, H. C., T. E. Morton (1973) Planning horizons for production smoothing with deterministic demands. Management Science,Vol. 20 : 110125. Kunreuther, H. C., T. E. Morton (1974) General planning horizons for production smoothing with deterministic demands. Management Science.Vol. 20 : 10371046. Lundin, R.A., and Morton, E. (1975) Planning Horizon for the Dynamic Lot Size Model: Zabel vs. Protective Procedures and Computational Results, Operations Research, Vol. 23, No. 4 : 711-734. Morton, T. (1978a) The nonstationary infinite horizon inventory problem, Management Science, Vol. 24 : 14741482. Morton, T. (1978b) Universal planning horizons for generalized conve production scheduling, Operation. Research, Vol .26 : 10461058. Rajagopalan, S. (1992) Deterministic Capacity Expansion Under Deterioration, Managemen Science, Vol. 38 : 525-539. Saydam, C. and M. McKnew (1987) A Fast Microcomputer Program for Ordering Using the Wagner-Whitin Algorithm, Production and Inventory Management Journal, Vol. 28 : 15-19. Sethi, S. P. and Bhaskaran, S. (1985) Conditions for Existence of Decision Horizons for Discounted Masalahs in a Stochastic Environment: A Note, Vol. 4, No. 2 : 61-64. Silver, E.A., and H.C. Meal (1973) A heuristic for selecting lot size quantities for the case of a deterministic time varying rate and discrete opportunities for replenishment, Production and Inventory Management, Vol. 14 : 64-74.
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008
33 Simpson. C. (2001) Questioning the relative virtues of dynamic lot sizing rules, Computers and Operations Research, Vol. 28 : 899914. Thompson, G. L., S. P. Sethi (1980) Turnpike horizons for production planning, Management Science, Vol. 26 : 229241. Wagelmans P. M., C. P. M. van Hoesel, and A. Kolen (1992) Economic lot sizing: An O(n log n) algorithm that runs in linear time in the Wagner-Whitin case, Operations Research, Vol. 40 : S145S156. Wagner, H.M, and Whitin, T.M. (1958) Dynamic Version of the Economic Lot Size Model, Management Science, Vol. 5, No. 1 : 89-96. Wagner, H. M. (2004) Comments on Dynamic Version of the Economic Lot Size Model, Vol. 50, No. 12 : 1775-1777.
Lucy Karyati Basar : Modal Program Integer Untuk Menentukan Horizon Waktu Peramalan Dalam Menyelesaikan Masalah..., 2008 USU e-Repository © 2008