Bir Montaj Hattı Dengeleme Probleminin GAMS’de Modellenmesi

Merhaba arkadaşlar, bu hafta sizlerle bir montaj hattı dengeleme problemini GAMS’de modelleyeceğiz.

Aşağıdaki şekilde faaliyetlerin öncelik ilişkilerine dair bir diyagram verilmiştir. Hattı dengelerken bu öncelik ilişkileri dikkate alınarak faaliyetler atanmalıdır. Problemde verilen faaliyetlerin maksimum 4 istasyon kullanılarak dengelenmek istendiğini varsayalım. Belirlenen çevrim süresi de 50 dakika olsun. Faaliyetlerin süreleri ise aşağıdaki şekilde faaliyetlerin üzerinde gösterilen değerlerdir. Öncelikle problemin matematiksel modelini inceleyeceğiz, daha sonrasında ise GAMS’de kodlayacağız.

Problemin Matematiksel Modeli

Problemin amacı minimum istasyon kullanarak faaliyetleri istasyonlara atamaktır, bu yüzden problemimiz minimizasyon problemi olur.

Problemin GAMS’de Modellenmesi

Problemi GAMS’de modellemeden önce öncelik ilişkilerini gösteren öncelik matrisini oluşturalım. Bu matrisi oluştururken yukarıda verilen öncelik diyagramından yararlanırız. Ayrıca faaliyetler arasındaki öncelik durumunu GAMS’de kodlarken bu matristen yararlanacağız.

Görevler	1	2	3	4	5	6	7	8	9	10
1	0	1	1	0	0	0	1	1	1	1
2	0	0	1	0	0	0	1	1	1	1
3	0	0	0	0	0	0	1	1	1	1
4	0	0	0	0	1	1	0	0	1	1
5	0	0	0	0	0	1	0	0	1	1
6	0	0	0	0	0	0	0	0	1	1
7	0	0	0	0	0	0	0	0	1	1
8	0	0	0	0	0	0	0	0	1	1
9	0	0	0	0	0	0	0	0	0	1
10	0	0	0	0	0	0	0	0	0	0

Tablo-1 Öncelik Matrisi

Şimdi problemimizi modellemeye başlayabiliriz. Öncelikle indislerimizi tanımlayalım.

Problemimizde i ve k olmak üzere iki indisimiz var. İ faaliyetleri temsil ederken k ise istasyonlarımızı temsil etmektedir. Aşağıdaki görselde kırmızı çerçeve ile içine alınmış kısım dikkatinizi çekecektir. Bu hafta yeni öğreneceğimiz komutlardan bir tanesi “Alias”. Alias komutu ile i ve h indislerinin aynı anlama geldiğini ifade ederiz. Bu ifade sayesinde öncelik tablomuzu oluşturabiliriz.

Tablo-11 ‘de gösterilen öncelik matrisini GAMS’de “table” fonksiyonu kullanarak gösteririz.

Problemimizdeki parametrelerimiz faaliyetlerin süresidir. Bu değerleri “parameters” komutunu kullanarak aşağıdaki gibi yazabiliriz.

Problemde verilen çevrim süresi sabit bir değer olduğu için “scalar” komutunu kullanırız.

Bu problemde değişkenlerimizi tanımlarken “binary variable” komutunu kullanırız. Bunun nedeni x değişkenlerimizin sadece 1 veya 0 almasını istememizdir. Yani 1. faaliyet 1. istasyona atanmalı ise 1 atanmamalı ise 0 alsın. Z değerimizi “free variable” olarak yazabiliriz.

Şimdi de kısıtlarımızı ve amaç fonksiyonu eşitliklerini yazacağız.

Amaç fonksiyonumuz toplam istasyon sayısının minimum olmasıydı. Öncelikle amaç fonksiyonumuza ait eşitliği yazarak kısıtları yazmaya başlarız. Sırasıyla kısıtları; atama kısıtı çevrim süresi kısıtı, öncelik kısıtı ve istasyon kısıtı olarak yazdım.

Atama kısıtı her görevin sadece bir istasyona atanmasını sağlayan bir kısıttır. Her bir faaliyet için geçerlidir. Bu gibi durumlarda kısıtın adını yazdığımız yerde parantez içinde (i) yazarak belirttiğimizde bu her i değeri için geçerli olduğunu gösterir. “atamakisiti(i)..” sonrasında iki nokta ekleyerek eşitliğimizi yazarız.

Diğer kısıtımız ise çevrim süresi kısıtıdır. Bu kısıt faaliyetlerin, istasyonun çevrim süresini aşmamasını sağlar. Bütün i faaliyetleri için geçerli olduğundan yine kısıt adının yanına (i) yazdık. İstasyon çevrim süresinden küçük olması gerektiği için “ =l= “ şeklinde eşitliği gösterdik.

Öncelik kısıtı a faaliyeti, b faaliyetinden önce gelmesi gerektiği durumlarda yazılır. Bu öncüllük ilişkisini öncelik matrisine bakarak anlayabiliriz. Örneğin; matrisimizi incelediğimizde 1. faaliyetin 2. faaliyetten önce olması gerektiğini görüyoruz. Bir koşul söz konusu. Kısıtı yazarken herhangi bir i ve h faaliyeti için yazarız. Buradaki şartımız i’nin h‘nin öncülü olması durumudur. Şart GAMS’de $ işareti ile gösterilir. Kısıtın adı yazılırken aşağıdaki gibi koşul durumunu da belirtiriz.

Öncelik kısıtlık (i,h) $ (öncelik(i,h) eq 1)

Bu, öncelik tablosunda, i satırı ve h sütunu 1’e eşit ise bu işlemi gerçekleştir anlamına gelir. “eq” olarak yazdığımız ifade eşit anlamını verir. Daha sonra iki nokta konularak kısıt denklemi yazılır.

Biz k’yı indis olarak tanımlamıştık. Fakat yukarıda verilen eşitlik kısıtlarında k’nın değerine ihtiyaç duyduğumuzu görüyoruz. k ifadesi ile bir çarpım durumu söz konusudur. “ord” komutu ile k’nın kendi değerini kullanabiliriz. k hangi değeri alırsa ord(k)’da o değere eşit olacaktır. Örneğin k=1 için ord(1) =1’dir gibi.

Son olarak istasyon kısıtımızı yazarız. Bu kısıt, istasyonların sıralı olmasını sağlar.

Daha sonrasında equations yazarak eşitliklerimizi burada tanımlarız.

Son olarak modelin adını ve türünü yazıp problemi çözdürürüz. Ben modelin adına montaj yazdım ve /all/ komutunu kullandım. Eğer problemdeki bütün kısıtları çözdürmek istemiyorsanız sadece çözülmesini istediğiniz kısıtların adını yazarak problemi çözdürebilirsiniz.

Problemimiz MIP yani karma problemdir. Bunun nedeni de binary değişkenlerimizin de olmasıdır.

GAMS Çözüm Çıktısı

Problemi çözdürdükten sonra display kısmından x değişkenini seçelim. Burada her bir faaliyetin hangi istasyona atandığına dair sonucu görebiliriz. Problemimizin sonucunda 4 istasyona atanan faaliyetlerin aşağıdaki gibi olduğunu görüyoruz.