Common due date early/tardy scheduling on a single machine with deteriorating jobs and deteriorating maintenance

Bu çalışma pozisyonlarına bağlı olarak bozulan işlerin ve makine bakım faaliyetinin, tek makinede çizelgelenmesi problemini ele alır. Problem, bakım faaliyeti ve bozulma olmadığı durumda bile NP-zor'dur. Çözüm: (i) işlerin sıralarını, (ii) bakım faaliyetinin pozisyonunu, (iii) çizelgedeki ilk işin başlama zamanını kapsamaktadır. Bakım faaliyetinden sonra makine başlangıç haline geri döner ve bozulma yeniden başlar. Amaç fonksiyonu ağırlıklı erkenlik ve geçlik maliyetlerini en küçüklemektir. Teslim tarihinden önce (sonra) çizelgelenen işler erkenlik (geçlik) maliyetleri ile cezalandırılır. Özel durumlar için polinom zamanlı (O(n log n)) çözümler üretilmiştir. Teslim tarihinin kısıtlayıcı olduğu durumlar için ise polinom zamanlı bir algoritma mevcut değildir. Tamsayılı programlama modeli ve bu modelin çözüm zamanı açısından etkin olmadığı durumlar için algoritmalar önerilmiştir. Sayısal veriler, önerilen algoritmaların hem sonuç kalitesi hem de çözüm zamanı açısından iyi performans sergilediğini göstermektedir.