Algoritma

DispatchAtlas memisahkan perilaku solver dari pembangkitan benchmark dan eksekusi kampanye. Setiap solver berada di dispatchatlas.solve di balik satu registry, dan metadata solver adalah kontrak publik untuk tujuan, kapabilitas, pengodean, dependensi, stokastisitas, visibilitas tingkat-bukti, dan backend opsional. Halaman ini menjelaskan keluarga solver pada tingkat kerja; halaman registry sistem solver adalah katalog otoritatif per solver.

🏗️ Bagaimana solver diorganisasi

default_solver_registry() mengembalikan registry pabrik solver tanpa-status. Setiap entri mendeklarasikan tag kapabilitas, tujuan yang didukung, kriteria henti default, perilaku pemutaran-ulang deterministik atau stokastik-berbenih, sebuah pengodean solusi, kebutuhan dependensi opsional, visibilitas tingkat-bukti, dan sebuah sitasi kanonik (atau justifikasi eksplisit sitasi-tak-berlaku). Sitasi gagal-menutup: sebuah keluarga dengan asal mani kanonik yang menghilangkan referensinya tidak dapat dikonstruksi.

🧰 Keluarga solver

📋 Aturan pendistribusian konstruktif

Baseline deterministik yang dibundel adalah solver list-scheduling konstruktif: masing-masing mengontrol urutan tugas, dan konstruktor serial menghormati permintaan sumber daya yang dideklarasikan setiap tugas. Tujuh keluarga — earliest-start, shortest-processing-time, longest-processing-time, earliest-deadline, earliest-finish-time, minimum-slack, dan greedy-completion — masing-masing menamai referensi mani kanoniknya dalam metadata. Mereka adalah jalur tercepat menuju jadwal yang layak dan menjadi jangkar setiap perbandingan, seperti dalam tutorial pertama.

🔀 Baseline metaheuristik

Lima metaheuristik berbenih representatif — algoritma genetik, anil simulasi, koloni semut, kawanan partikel, dan evolusi diferensial — berbagi operator kelayakan, perbaikan, penilaian, dan pencarian lokal yang sama, sehingga perbandingan mengukur strategi pencarian alih-alih perbedaan perpipaan insidental.

🔌 Solver adapter terkode

Kawanan partikel pembelajaran komprehensif (clpso, d-clpso) dan evolusi diferensial adaptif riwayat-keberhasilan (lshade, d-lshade) mencari sebuah vektor kontinu bernilai-riil dengan satu komponen per tugas. Setiap inti generik atas tujuan kontinu dan diikat ke penjadwalan melalui adapter pengodean bernama (random-key, spv, rounding, dan dekode fungsi-transfer) yang mengubah vektor menjadi urutan tugas berpresedensi-layak, dengan kebijakan perbaikan eksplisit yang mencatat apakah perbaikan terpicu.

🥊 Pesaing terdiversifikasi dan jalur multi-tujuan

Satu himpunan terkurasi sejawat terbit terkini memperluas perbandingan melampaui baseline representatif, masing-masing membawa referensi teks-penuh, kekuatan, dan peringatannya dalam metadata. Seorang sejawat bergabung ke medan publik hanya ketika melewati bar kekuatan-venue bersumber; kolam baseline klasik yang lebih luas tetap terdaftar untuk perbandingan internal. nsga3 adalah pesaing multi-tujuan bernama: ia mengevaluasi setiap urutan berpresedensi-aman atas vektor multi-tujuan (makespan, keterlambatan, keadilan beban) dan memilih penyintas dengan penichingan titik-rujukan.

🎯 Adapter eksak

Adapter backend-opsional (CP-SAT, MILP, branch-and-bound) mendeklarasikan dependensi opsional dan menyonda akar impornya saat runtime; ketika backend tidak ada, mereka memunculkan MissingOptionalDependencyError dengan nama extra dan catatan lisensi alih-alih mengimpor dependensi berat saat impor paket. Adapter native-terbatas (exhaustive-enumeration dan decision-diagram-sequencing) tidak membawa dependensi pihak ketiga dan menyelesaikan instans kecil secara eksak, memunculkan UnsupportedCapabilityError melewati jumlah tugas yang didukung. Pembungkus komersial Gurobi tetap di balik extra exact-commercial dan tidak pernah dibundel; kolam backend opsional yang lebih luas tetap terdaftar untuk penggunaan internal.

🐝 Keluarga NDSO

NDSO adalah keluarga solver pengodean-native milik registry: ia mencari langsung atas jadwal yang layak, sehingga setiap jadwal yang dihasilkannya layak secara konstruksi dan keluarga ini tidak pernah menjalankan langkah enkode/dekode atau pass perbaikan. Ia menyusun satu himpunan kecil mekanisme bernama:

• sebuah Matriks Keyakinan kepercayaan terpelajar per sel (posisi, tugas), diperkuat oleh jadwal yang lebih baik;
• Pemungutan Suara Terbobot-Keyakinan, yang menyintesis jadwal elite dengan memungut suara melintasi populasi yang dibobot oleh matriks itu;
• jadwal Kuantitas-dan-Kualitas yang menetapkan seberapa banyak kandidat berubah dan dari sumber panduan mana ia belajar;
• panduan tiga-sumber — elite tersintesis (eksploitasi), seorang sejawat (keragaman), atau sumber pengetahuan-lenyap (eksplorasi radikal);
• sebuah koefisien adaptif terpadu, satu jadwal non-linear yang menggeser keluarga dari eksplorasi ke eksploitasi.

Sebuah peta ablasi mengenumerasi satu konfigurasi pengisolasi per mekanisme bernama sehingga analisis hilir dapat mengatribusikan kontribusi tiap mekanisme, dan sebuah filter ekspor bertahap gagal-menutup alih-alih mengekspos mekanisme tingkat-lebih-lanjut di bawah cakupan laporan lebih rendah. Detail penuh mekanisme, dewan, ablasi, dan diagnostik berada di sistem solver; tidak ada klaim kinerja yang dibuat sebelum kampanye komparatif berjalan.

🎛️ Seleksi

SolverRegistry.select mencocokkan solver berdasarkan tag kapabilitas, kendala yang dideklarasikan, tujuan yang didukung, dan visibilitas tingkat-bukti — registry.select(objective="makespan", disclosure_label=DisclosureLabel.CORE) dari mulai cepat adalah contoh terkecil. Di atas registry, lapisan seleksi memeringkat solver untuk sebuah masalah dari fitur karakterisasi dan metadata publik, melabeli setiap rekomendasi dengan sumber dan kepercayaannya, dan tidak pernah mengklaim solver terbaik universal. Perekomendasi solver menyajikan penjelasan-penjelasan itu, termasuk mengapa sebuah solver dikecualikan.