Variable neighborhood search for order acceptance and scheduling problem

G ün üm üz rekabet ortam ında, bir firma i çin sipari ş kabul etme ya da reddetme kararı olduk ça önem kazanm ıştı r. Bu problemin ortaya çı kması nı n ası l nedeni, bir taraftan her fi rman n belirli bir üretim kapasitesinin ve kı t kaynaklar n n olması di ğer taraftan da sipari ş veren her m ü şterinin ilgili firmadan belirli bir beklentisinin olmas ıdı r. Bu nedenlerle, firma özellikle çok fazla sipari ş ald ığı zamanlarda, gelen sipari slerin bir kı smı nı reddetmek durumunda kalabilir. Bu noktada firman n hangi sipari şi kabul edece ğine ve kabul etti ği sipari şleri nası l cizelgeleyece ğine dair önemli bir karar vermesi gerekmektedir. Bu problem yazı nda sipari ş kabul etme ve çizelgeleme problemi (SKEÇ) olarak bilinir. Bu tezde, tek makine uzerinde iki farklı SKEÇ problemi ele alı nm ıştı r. İlk problemde her sipari şin teslim tarihi, i şlem s üresi ve getirisi vard r. Kabul edilen ve teslim zaman ından önce tamamlan ıp, m ü şteriye teslim edilen her sipari ş üreticiye en b üy ük kazanç sa ğlar. Ge ç teslim edilen sipari şler kazan çta bir d üşüş yarat ır. Herhangi bir sipari şin reddedilmesi m ümkündür ve hi çbir ek maliyet getirmez. Bazen m uşteriler sipari şleri i çin son teslim tarihi belirleyebilirler. Son teslim tarihi bir sipari şin kabul edilebilmesi i cin m üşteri taraf ından üreticiye verilen en son zamandı r. E ger bir sipari ş son teslim tarihinden sonra m üşteriye ula şt ırı lı rsa, m üşteri sipari şi reddeder ve sat ın almaz. Ek olarak, baz sipari şler i şlenmeye ba şlamaya hazı r olmak i cin serbest b ırak ılma zamanları na ihtiya ç duyabilirler. İlk incelenen problem bir sipari şin son teslim tarihini, serbest b rakı lma zamanı n ve sipari şler aras ında sı raya ba ğlı haz ırlı k s ürelerini yok sayarak problemi ele al ırken bu özellikler ikinci problemde kapsanm ıştı r. Her iki problemin ama ç fonksiyonu elde edilen kazancı en b üyuklemektir. Bu tezde, incelenen problemler i çin de gi şken kom şuluklu arama (DKA) algoritmas ı önerilmi ştir. DKA algoritması etkili yerel arama y öntemi ile iki kom şuluk yap ısı nı n kullanı lması yoluyla geli ştirilmi ştir. Önerilen algoritmanı n performansı , yaz nda bulunan sezgisel y öntemlerle k ıyaslanm ıştı r. SKEÇ problemine uygulanan DKA algoritmasını n yaz ında bulunan sezgisel y öntemlere g öre g üçl ü ve zay ıf y önleri verilmi ştir.