A tabu search algorithm for order acceptance and scheduling problem

Bu tezde, sipariş teslim zamanlarının ve kısıtlı üretim kapasitesinin gelen siparişlerin seçilerek kabul edilmesini gerektirdiği, bir siparişe dayalı üretim sistemi ele alınmıştır. Ele alınan sistemde, kabul edilen ve teslim zamanından önce tamamlanıp, müşteriye teslim edilen her sipariş üreticiye kazanç sağlar. Geç teslim edilen siparişler teslim gecikmesi ile orantılı olarak kazançta bir düşüş yaratırken, termin zamanından önce tamamlanamayan işler kazanç getirmez. Herhangi bir siparişin reddedilmesi mümkündür ve hiçbir ek maliyet getirmez. Kabul edilen siparişler tek makine üzerinde, serbest bırakılma zamanlarından sonra olacak şekilde çizelgelenebilirler ve siparişler arasında sıraya bağlı hazırlık süreleri vardır. Kabul edilen siparişin kazancı, o siparişin tamamlanma zamanının birfonksiyonu olduğu ve bir siparişin işlenmesi sonraki siparişlerin gecikmesine neden olabileceği için sipariş kabul etme ve çizelgeleme kararları birlikte ele alınmalıdır. Elde edilen kazancı enbüyüklemek için, üretici hangi siparişleri kabul edeceğini ve bu siparişleri hangi sırada işleyeceğini belirlemelidir. Bu NP-zor eniyileme problemi için, etkili olasılıksal yerel arama ve çeşitlendirme mekanizmaları ile desteklenmiş bir tabu arama algoritması önerdik. Önerilen algoritmanın performansı, çeşitli parametre değerleri ile rassal olarak oluşturulmuş, çok sayıda örnek problem ile çözülerek incelenmiştir. Ayrıca bu algoritma, literatürde var olan iki ayrı sezgisel yöntem ile kıyaslanmıştır. Karşılaştırmalarda performans ölçütü olarak çözümlerin kazançlarının en yüksek kazançtan ne kadar uzak olduğu ele alınmıştır. Karışık tamsayılı programlama kullanılarak en yüksek kazanç için bir üst sınır elde edilmişve bu üst sınıra dayanarak hesaplanmış ortalama optimalite aralığı verilmiştir. Yaptığımız hesaplamalı deneylerin sonuçlarına göre, tabu arama algortiması amaç fonksiyonu açısından test edilen örneklerde kıyasladığımız diğer iki sezgisel yöntemden çok daha iyi sonuçlar vermiştir. Buna karşın, tabu arama algortimasının çalışma zamanı 100 adet sipariş verildiği örnekler için bile oldukça kısadır. Önerilen sezgisel yöntemin başarısı, büyük ölçüde, arama sürecine sipariş kabul etme ve çizelgeleme kararlarını birlikte dahil edebilmesine ve etkili çeşitlendirme mekanizmaları kullanmasına bağlıdır.