Ihrlich'in yorumuna göre (teşekkürler btw), "zamanlama" terimi yanıltıcı olabilir ve bu daha uygun bir açıklama olabilir: bir N * N matrisi verilirse, verilecek satırda bir permütasyon elde edilir. en büyük çapraz toplamı.İşlemcilerde işlerin zamanlaması için algoritma
Ben N işler ve N işlemcilerin bir dizi var. Tüm işlemciler birbirinden farklı olabilir. Her (iş, işlemci) çifti için, bu işlemin o işlemci üzerinde çalıştığı performansa sahibim. Performans IPC'de ölçülür (Döngü Başlığı).
Ben IPC genel toplamını maksimize bir zamanlama (1-to-1 ayırma) bulmaya çalışıyorum. Mümkün olan tüm çizelgeleri, O (N!) Ile yaşayamayacağım, bu da geçerli değil. Sonra yüklerini ve işlemcilerin tercihlerini sıralamak için IPC'leri kullanılarak, "kararlı uygun" algoritması O (N^2) kullanmayı denemişlerdir. Çok hızlı çalışır ve iyi bir program getirir, ama en uygun olanı değil.Sorularım şunlardır:
1) Gerçekten kararlı eşleştirme algoritması optimum ödevi geri edebilmek için bekliyordu. Birisi neden başarısız olduğunu açıklayabilir mi? Şimdiye kadarki en iyi tahminim farklı (iş, işlemci) çiftleri arasındaki bağların varlığı. Ayrıca şanssız "kayıtsızlık ile istikrarlı eşleme" algoritmasını denedim. Algoritmanın benim uygulamam nedeniyle başarısız olmadığından bahsetmeliyim. Algoritmanın neden bu sorunu çözemediğine dair daha teorik bir cevap arıyorum.
2) Bundan ben kullanabileceğiniz bir algoritma biliyor musunuz? Biri bile var mı?
Bunun için bir bilgisayar bilimi dalı var. Aslında başlangıçta üretim yönetiminden geliyor. Başlıyor – iehrlich
için https://en.wikipedia.org/wiki/Scheduling_(computing) okuma düşünün, oldukça yararlı görünüyor. Ancak, hızlı bir şekilde gözden geçirdikten sonra, sunulan tüm algoritmaların sezgisel olduğu anlaşılıyor ve en uygun zamanlamayı geri getirmesi garanti edilmiyor. – prodromou
Bir sebepten dolayı "yeni başlayanlar için" dedim :) Ayrıca, programın optimal olup olmadığını nasıl kontrol edersiniz? – iehrlich