Grafik aliran dengan batas bawah bukan nol atau kapasitas 0
Saya khawatir judul pertanyaan mungkin tidak cukup akurat tetapi saya tidak dapat menemukan sesuatu yang lebih akurat
Inilah masalahnya
Diberikan mesin 'n'
- Setiap mesin memiliki serangkaian kemampuan
- Setiap mesin memiliki ketersediaan maksimal (A (m))
Diberikan tugas 'm'
- Setiap tugas membutuhkan sekumpulan kemampuan
- Setiap tugas membutuhkan waktu tertentu (D (t))
- Sebuah tugas harus dilakukan hanya di satu mesin
Masalahnya adalah menentukan apakah semua tugas dapat diselesaikan.
Saya terjebak dengan persyaratan 'satu mesin saja'. Grafik alur satu-satunya yang dapat saya hasilkan tidak menjamin bahwa tugas tidak ditautkan ke lebih dari satu mesin.
Ini semacam masalah pencocokan bipartit tetapi dengan kapasitas> 1
Saya juga mengalami perilaku seperti XOR di jaringan aliran yang serupa tetapi memiliki persyaratan 'xor' pada ujung 'sumber' di mana saya akan membutuhkannya di ujung target.
Adakah yang punya tip? Apakah mungkin untuk memodelkannya sebagai grafik aliran?
Tx!
Peter
PS Mencoba untuk memperjelas persyaratan dengan contoh yang lebih konkret
Gunakan sistem cetak digital dan pekerjaan cetak
- Setiap pers digital dapat berjalan selama beberapa jam
- Setiap pers memiliki beberapa kemungkinan penyelesaian: misalnya 'pemotong lembar', 'laminasi', 'pemotong laser', 'melipat halaman', ....
- Setiap pekerjaan cetak membutuhkan beberapa jam
- Setiap pekerjaan cetak membutuhkan satu atau lebih kemungkinan penyelesaian
Diberikan satu set mesin, ketersediaan untuk masing-masing dan kemungkinan penyelesaian dan juga satu set pekerjaan cetak (durasi, opsi penyelesaian diperlukan) menentukan apakah semua pekerjaan cetak dapat selesai
Jadi mis
- Printer p1 tersedia untuk durasi 10 jam dan memiliki fitur f1 dan f2
- Printer p2 tersedia untuk durasi 10 jam dan memiliki fitur f2 dan f3
- Job1, yang membutuhkan fitur f1 dan f2 membutuhkan waktu 8 jam untuk dijalankan
- Job2, yang membutuhkan fitur f2 dan f3 membutuhkan waktu 8 jam untuk dijalankan
- Job3, membutuhkan fitur f2 membutuhkan 4 jam untuk dijalankan
Printer yang tersedia misalnya 10 jam dapat menjalankan pekerjaan 10 x 1 jam atau pekerjaan 5 x 2 jam, atau pekerjaan 1 x 8 jam dan pekerjaan 1 x 2 jam, ... Pekerjaan selalu harus dijalankan pada satu printer
Diagram alir yang bisa saya hasilkan selalu menghasilkan kasus di mana
8 jam p1 ditetapkan ke pekerjaan1 (menyisakan 2 jam untuk printer p1) 8 jam p2 ditetapkan ke pekerjaan2 (menyisakan 2 jam untuk printer p2)
(sejauh ini bagus)
tapi kemudian
2 jam p1 dan p2 tersisa digunakan untuk mengalir ke pekerjaan3 dan aliran maksimum tampaknya menunjukkan tiga pekerjaan dapat dijalankan (yang tidak ok)
Jawaban
Masalah Anda adalah NP-hard. Dalam kasus khusus di mana tidak ada pekerjaan yang memerlukan fitur tertentu, dan semua printer memiliki ketersediaan yang sama, ini hanya menjadi masalah pengemasan nampan , yang (sangat) NP-complete.
Anda dapat mencoba mengadaptasi algoritme standar untuk pengemasan bin dengan situasi Anda. Misalnya, satu pendekatan akan menggunakan pemrograman linier integer dan berharap pemecah ILP dapat menangani contoh masalah yang dihasilkan.