Sıfır olmayan alt sınır veya 0 kapasiteye sahip akış grafiği
Korkarım soru başlığı yeterince doğru olmayabilir ama daha doğru bir şey bulamadım
Sorun burada
Verilen 'n' makineleri
- Her makinenin bir dizi özelliği vardır
- Her makinenin maksimum kullanılabilirliği (A (m))
Verilen 'm' görevleri
- Her görev bir dizi yetenek gerektirir
- Her görev belirli bir süre alır (G (t))
- Bir görevin yalnızca bir makinede gerçekleştirilmesi gerekir
Sorun, tüm görevlerin tamamlanıp tamamlanamayacağını belirlemektir.
'Yalnızca bir makine' gerekliliğiyle sıkışıp kalıyorum. Bulabildiğim tek akış grafiği, bir görevin birden fazla makineyle bağlantılı olmadığını garanti etmiyor.
Bu iki taraflı bir eşleştirme problemi ama kapasiteleri> 1
Aynı zamanda akış ağlarında XOR benzeri davranışla karşılaştım, bu da benzer ancak hedef uçta ihtiyacım olan 'kaynak' ucunda 'xor' gereksinimi var.
Herhangi bir ipucu olan var mı? Bunu bir akış grafiği olarak modellemek mümkün mü?
Tx!
Peter
PS Daha somut bir örnekle gereksinimleri netleştirmeye çalışmak
Dijital baskı sistemlerini ve baskı işlerini varsayın
- Her dijital baskı makinesi birkaç saat çalışabilir
- Her baskı makinesinin bazı sonlandırma olanakları vardır: ör. 'Yaprak kesici', 'laminat', 'lazer kesici', 'sayfa katlama', ...
- Her baskı işi birkaç saat gerektirir
- Her baskı işi bir veya daha fazla sonlandırma olasılığına ihtiyaç duyar
Bir dizi makine verildiğinde, her birinin kullanılabilirliği ve sonlandırma olanakları ve ayrıca bir dizi yazdırma işi (süre, bitirme seçenekleri gerekli) tüm yazdırma işlerinin bitip bitemeyeceğini belirler.
Yani örneğin
- Yazıcı p1, 10 saat süreyle kullanılabilir ve f1 ve f2 özelliklerine sahiptir
- Yazıcı p2, 10 saat süreyle kullanılabilir ve f2 ve f3 özelliklerine sahiptir
- Job1, f1 ve f2 özelliklerini gerektiren çalıştırmak için 8 saat sürer
- Job2, f2 ve f3 özelliklerinin çalıştırılması 8 saat sürer
- Job3, f2 özelliğinin çalıştırılması için 4 saat gerektirir
Örneğin 10 saat kullanılabilir olan bir yazıcı, 10 x 1 saatlik işleri veya 5 x 2 saatlik işleri veya 1 x 8 saatlik işleri ve 1 x 2 saatlik işleri çalıştırabilir, ... İşler her zaman tek bir yazıcıda çalıştırılmalıdır
Bulabildiğim akış diyagramları her zaman şu durumlarda sonuçlanır:
Job1'e 8 saat p1 atanır (yazıcı p1 için 2 saat bırakılır) Job2'ye 8 saat p2 atanır (yazıcı p2 için 2 saat kalır)
(Şimdiye kadar, çok iyi)
ama sonra
Kalan 2 saatlik p1 ve p2, job3'e akış için kullanılır ve maksimum akış, üç işin çalıştırılabileceğini gösterir (ki bu tamam değildir)
Yanıtlar
Senin sorunun NP-zordur. Hiçbir işin belirli bir özellik gerektirmediği ve tüm yazıcıların aynı kullanılabilirliğe sahip olduğu özel durumda, bu sadece (güçlü bir şekilde) NP-tamamlanmış olan bölme paketleme problemi haline gelir .
Bin paketleme için standart algoritmaları kendi durumunuza uyarlamayı deneyebilirsiniz. Örneğin, bir yaklaşım tamsayı doğrusal programlamayı kullanmak ve ILP çözücünün ortaya çıkan problem örneğini çözebileceğini ummak olabilir.