Atölye Tipi Çizelgelemede Kullanılan Darboğazı Kaydırma Sezgiselinde Çevrim Oluşması Üzerine


Güngör M.

41. Yöneylem Araştırması ve Endüstri Mühendisliği Ulusal Kongresi, Denizli, Turkey, 26 - 28 October 2022, pp.43

  • Publication Type: Conference Paper / Summary Text
  • City: Denizli
  • Country: Turkey
  • Page Numbers: pp.43

Abstract

Atölye tipi çizelgeleme için verimli bir algoritma olan darboğazı kaydırma (shifting bottleneck) sezgiseli, makineleri teker teker çizelgeleme fikrine dayanır. Henüz çizelgelenmemiş her makine için gevşetilmiş bir alt problem çözülür ve azami tamamlanma zamanını (makespan) en büyüten makine darboğaz olarak değerlendirilerek çizelgelenir. Bu tek makineli problemlerin çözümleri, önceden çizelgelenmiş makinelerin ortaya çıkardığı ilave kısıtlar dikkate alınmazsa, problemi tanımlayan çizgede çevrimler oluşturarak olursuz çözümler doğurabilir. Ne var ki bu çok seyrek görülen bir durumdur. Biz bu çalışmamızda, Michael Pinedo'nun meşhur "Scheduling: Theory, Algorithms, and Systems" (2016) çizelgeleme kitabında yer alan yanlış bir örnekten hareketle (Örnek 7.2.3, s. 199), darboğazı kaydırma sezgiselinde çevrim oluşması durumunu teorik olarak inceliyoruz. Öncelikle tek makineli kafa-gövde-kuyruk çizelgeleme problemine dair bir önerme ispatlıyoruz. Böylece gösterebiliyoruz ki darboğazı kaydırma sezgiselindeki tek makineli alt problemlerde iki işlemli makineler, önceleme kısıtları olmasa bile, çevrim oluşturmaz. Bu bilgi ışığında Pinedo'nun kitabındaki yanlış örneğin iç yüzüne ve nasıl düzeltilebileceğine dair sağlam bir fikre sahip olabiliriz.