Television commercial scheduling with industry-specific constraints and audience-based ratings

Televizyon (TV) kanalları için başlıca gelir kaynağını reklamlar oluşturmaktadır. Ancak bu kanallar, reklamların çizelgelenmesi ve faturalandırılmasıyla ilgili sektörel ve devlet kaynaklı düzenlemelere uymak zorundadır. Bu çalışma, Türkiye'nin en önde gelen TV kanallarından biri için, sıkı düzenleyici kısıtlar ve hedef kitleye özel gereksinimlerin, özellikle yüksek talep durumlarında uygulanabilir bir çizelge bulmayı dahi zorlaştırdığı reklam seçimi ve çizelgeleme problemini ele almaktadır. Ayrıca, reklamların sağladığı gelirin büyük ölçüde hedef kitleden elde edilen reytinglere bağlı olması, çizelgeleme sürecinin etkisini daha da artırmaktadır. Reklam çizelgeleme problemi; yenilenemeyen kaynak kısıtlı, özdeş paralel makineler üzerinde, makineye ve zamana bağlı ödül ve kısıtlarla tanımlanan bir çizelgeleme problemi olarak çerçevelendirilebilir ve toplam ödülün maksimize edilmesi amaçlanmaktadır. Bu karmaşık problemi çözmek amacıyla, iki farklı Karışık Tamsayılı Programlama (MIP) formülasyonu ile, path-relinking ve Variable Neighborhood Descent (VND) yaklaşımlarıyla geliştirilen özgün bir Greedy Randomized Adaptive Search Procedure (GRASP) sunulmuştur. Ayrıca, problem Team Orienteering Problem with Time Windows (TOPTW) olarak yeniden yapılandırılmış ve GRASP algoritması, Hybrid Artificial Bee Colony (HABC) algoritması ile karşılaştırılmıştır. Gerçek dünyadan alınan 10 örnek üzerinde gerçekleştirilen deneyler, GRASP algoritmasının düşük hesaplama yüküyle tutarlı biçimde optimal çözüme yakın sonuçlar elde ettiğini ortaya koymaktadır.