Membuat model jadwal kerja yang kompleks

9

Saya punya masalah dunia nyata yang saya coba wakili dan otomatisasi. Saya telah menyederhanakan dan mengabstraksikannya sebagai berikut:

  • Ada n tempat kerja (P1, P2, ..., Pn).
  • Setiap tempat, Pn memiliki kunci, Kn.
  • Ada m Pekerja, (W1, W2, ..., Wm).
  • Untuk dapat bekerja di Pn, seorang pekerja harus memegang Kn.
  • Setiap kunci dapat dipegang oleh seorang pekerja, atau ditinggalkan di Exchange, E.

  • Seorang pekerja dapat melakukan perjalanan ke Bursa kapan saja untuk mengambil beberapa kunci yang tidak diklaim atau menurunkan beberapa kunci untuk digunakan orang lain.

  • Sekarang, ada jadwal kerja eksogen yang harus diselesaikan dalam urutan yang ketat. Sebagai contoh:

    • 2016-04-21 W1 harus bekerja di P6
    • 2016-04-21 W2 harus bekerja di P3
    • ** diperlukan pertukaran kunci **
    • 2016-04-22 W3 harus bekerja di P3
    • 2016-04-22 W2 harus bekerja di P6

  • Sejumlah pekerja mungkin harus bekerja di Pn di beberapa titik dalam jadwal mereka, meskipun tidak pernah pada hari yang sama

Kita tahu:

  • Lokasi awal semua kunci, baik dengan pekerja atau di E
  • Perintah kerja masa depan yang harus dipenuhi oleh setiap pekerja

Jadi, saya berjuang untuk memodelkan seluruh situasi ini. Dapatkah Anda menyarankan struktur data dan algoritma yang harus saya perhatikan untuk mendapatkan pegangan dan mulai mengoptimalkan perjalanan ke pertukaran untuk setiap pekerja?

Yang ingin saya perkecil adalah jumlah total perjalanan ke E. Tujuan sekunder adalah untuk memastikan bahwa tidak ada pekerja yang melakukan jumlah perjalanan yang tidak proporsional.

Terima kasih sebelumnya!!

algorithms data-structures graph Gareth Lloyd
sumber
2
Jumlah rata-rata perjalanan ke E per pekerja = "jumlah total perjalanan" / m. Jadi, jika m konstan, dua sasaran Anda adalah tujuan yang sama. Lebih menarik: saya kira setiap pekerja dapat membawa lebih dari satu kunci pada saat yang sama?
Doc Brown
Ya, pekerja dapat membawa sejumlah kunci. Mengenai "rata-rata" saya pikir saya mengekspresikan diri saya dengan buruk. Saya lebih banyak berpikir tentang keadilan, bahwa tidak ada pekerja yang harus menyelesaikan sejumlah perjalanan yang tidak proporsional, sehingga varians yang rendah. (pertanyaan diedit untuk mencocokkan)
Gareth Lloyd
Karena pekerja jelas dipercaya dengan kunci dan dapat menyimpan kunci pada malam hari dan selama diperlukan - selama pertukaran tidak diperlukan - mengapa tidak membuat satu set kunci untuk setiap pekerja yang mereka simpan secara permanen? Atau, buat satu set kunci untuk setiap pekerja untuk semua tempat yang mereka kunjungi untuk periode waktu tertentu, katakanlah, seminggu. Kunci digandakan sesuai kebutuhan untuk membuat satu minggu yang ditetapkan untuk setiap pekerja. Semua pekerja bertukar kunci sekali seminggu.
radarbob
Apakah ada biaya (uang atau waktu) untuk pergi ke bursa?
Dan Pichelman
Ya, lebih banyak perjalanan ke bursa adalah hasil yang lebih buruk.
Gareth Lloyd

Jawaban:

1

Pertanyaannya sedikit ambigu pada satu poin kunci: elemen mana yang kita coba selesaikan. Apakah kita ingin mengoptimalkan urutan sumber daya yang didelegasikan? Meminimalkan perjalanan ke bursa? Memaksimalkan throughput perintah kerja?

Dengan mengingat hal itu, saya akan berasumsi bahwa kita bisa melakukan campuran dari semua hal ini dan menjaga jawabannya tetap tinggi.

Hal pertama yang terlintas di benak saya adalah bahwa masalah yang saling terkait bahwa upaya ini untuk memecahkan sebagian besar berpusat di sekitar manajemen ketergantungan. Pekerja, kunci, dan lokasi dapat dianggap sebagai dependensi yang harus diselesaikan untuk menyelesaikan pekerjaan pekerjaan.

Membawa ini ke tingkat berikutnya, saya akan melihat adaptasi penyortiran topologis ( https://en.wikipedia.org/wiki/Topological_sorting ). Model ruang masalah sebagai grafik besar (basis data grafik modern mungkin juga merupakan media yang baik untuk beberapa analisis ini) dan kemudian gunakan berbagai macam topologi untuk menyelesaikan berbagai aspek ruang masalah.

Pada sedikit singgung, ini terdengar seperti proyek yang sangat menyenangkan. Hari ini, saya iri dengan Anda, Tuan.

Michael
sumber
Lihatlah grafik di github github.com/MatheusArleson/Graphs
linuxunil
Apakah algoritma pewarnaan membantu dalam situasi ini? en.m.wikipedia.org/wiki/Graph_coloring
linuxunil