Time-indexed mathematical models for order acceptance and scheduling problems

Uzun yıllardır üzerinde çalışılan bir konu olarak, çizelgeleme problemlerini tanımlayan, sınıflandıran ve çözen önemli sayıda çalışma yapılmıştır. Çizelgeleme problemlerinin büyük bir çoğunluğu, hesaplama karmaşıklığı yüksek olduğundan, zordur ve farklı problemlerle birleştirmek hesaplama karmaşıklığını daha çok arttırmaktadır. Bu tez, çizelgeleme problemini siparişleri kabul/red kararıyla birleştiren Sipariş Kabul ve Çizelgeleme Problemleri (SKÇ) üzerine odaklanmakta ve bu problem için ilk kez zaman endeksli Karışık Tam Sayılı Doğrusal Programlama (KTSDP) modelleri sunmaktadır. Sipariş kabul ve çizelgeleme problemi işlem süresi, serbest bırakılma tarihi, teslim tarihi ve son teslim tarihi parametreleriyle tanımlanabilir. Ayrıca, her siparişin maksimum gelir ve önem ağırlığı bulunmaktadır. Ek olarak, ardışık şekilde işlenen siparişler arasında hazırlama süresi bulunabilir. Bu tezde, yukarıdaki parametrelerle tanımlanan, genel sipariş kabul ve çizelgeleme problemi (SKÇ 2) ile serbest bırakılma tarihi ve hazırlama sürelerini dahil etmeyen özel hali (SKÇ 1) ele alınmıştır. Zaman endeksli KTSDP modeli SKÇ 1 ve SKÇ 2 için geliştirildikten sonra, bu modellerin yeterliliği ve etkinliği sayısal olarak test edilmiştir. SKÇ 1 modelinin yeterliliği ve etkinliğini arttırmak için, üç baskınlık özelliği önerilmiştir. Bu baskınlık özellikleri sonucunda hem eniyilik aralığının hem de çözüm zamanının azaldığı gözlemlenmiştir. Bu sayede büyük test örnekli problemler çözülebilmiştir. SKÇ 2, SKÇ'1 e kıyasla daha zor bir model olduğu için, zaman endeksli KTSDP modeli, problemi makul zaman çerçevesinde eniyi sonucu verecek şekilde çözememiştir. Bu sebeple, eniyi çözüme alt ve üst sınır bulabilmek amacıyla farklı yöntemler sunulmuştur. İyi bir üst sınır elde etmek amacıyla Lagrangian Gevşetmesi yanı sıra, üç adet yeni geçerli eşitsizlik içeren Doğrusal Programlama Gevşetmesi önerilmiştir. Yapılan testler sonucunda Lagrangian Gevşetmesi sadece gevşek üst sınırlar bulurken, geçerli eşitsizlik içeren Doğrusal Programlama Gevşetmesi yaklaşık olarak bütün üst sınırları tüm test örnekleri için geliştirmiştir. Alt sınır elde etmek için, basit bir sezgisel yöntem ve yeniden düzenlenmiş KTSDP formülü sunulmuş ve bu yöntemlerin sadece küçük test örnekli problemleri en iyi şekilde çözebildiği gösterilmiştir.