Pada artikel ini kami akan memberi tahu Anda bagaimana kami memecahkan masalah kurangnya sel bebas di gudang dan pengembangan algoritma optimasi diskrit untuk memecahkan masalah tersebut. Mari kita bicara tentang bagaimana kita βmembangunβ model matematika dari masalah optimasi, dan tentang kesulitan yang tidak terduga yang kita temui saat memproses data masukan untuk algoritma.
Jika Anda tertarik dengan penerapan matematika dalam bisnis dan Anda tidak takut dengan transformasi identitas rumus yang kaku di tingkat kelas 5, selamat datang di kucing!
Artikel ini akan bermanfaat bagi mereka yang menerapkannya WMS-sistem, bekerja di industri gudang atau logistik produksi, serta pemrogram yang tertarik pada penerapan matematika dalam bisnis dan optimalisasi proses dalam suatu perusahaan.
Bagian pengantar
Publikasi ini melanjutkan rangkaian artikel di mana kami berbagi pengalaman sukses kami dalam menerapkan algoritma optimasi dalam proses gudang.
Π menjelaskan secara spesifik gudang tempat kami menerapkan WMS-sistem, dan juga menjelaskan mengapa kami perlu memecahkan masalah pengelompokan kumpulan barang yang tersisa selama implementasi WMS-sistem, dan bagaimana kami melakukannya.
Ketika kami selesai menulis artikel tentang algoritma optimasi, ternyata jumlahnya sangat besar, jadi kami memutuskan untuk membagi materi yang terkumpul menjadi 2 bagian:
- Pada bagian pertama (artikel ini) kita akan berbicara tentang bagaimana kita βmembangunβ model matematika dari masalah tersebut, dan tentang kesulitan besar yang tidak terduga yang kita temui saat memproses dan mengubah data masukan untuk algoritma.
- Pada bagian kedua kita akan mempertimbangkan secara rinci implementasi algoritma dalam bahasa tersebut C + +, kami akan melakukan eksperimen komputasi dan merangkum pengalaman yang kami peroleh selama penerapan βteknologi cerdasβ tersebut dalam proses bisnis pelanggan.
Cara membaca artikel. Jika Anda membaca artikel sebelumnya, maka Anda bisa langsung menuju ke bab βIkhtisar Solusi yang Adaβ; jika belum, maka uraian masalah yang sedang diselesaikan ada pada spoiler di bawah ini.
Deskripsi masalah yang diselesaikan di gudang pelanggan
Kemacetan dalam proses
Pada tahun 2018, kami menyelesaikan proyek untuk dilaksanakan WMS-sistem di gudang βTrading House βLDβ di Chelyabinsk. Kami menerapkan produk β1C-Logistics: Warehouse Management 3β untuk 20 tempat kerja: operator WMS, pemilik toko, pengemudi forklift. Luas gudang rata-rata sekitar 4 ribu m2, jumlah sel 5000 dan jumlah SKU 4500. Gudang tersebut menyimpan ball valve produksi kami sendiri dengan berbagai ukuran mulai dari 1 kg hingga 400 kg. Persediaan di gudang disimpan secara batch, karena perlu dilakukan pemilihan barang sesuai FIFO.
Selama perancangan skema otomatisasi proses gudang, kami dihadapkan pada masalah penyimpanan inventaris yang tidak optimal. Kekhususan penyimpanan dan peletakan crane sedemikian rupa sehingga satu unit sel penyimpanan hanya dapat menampung barang-barang dari satu batch (lihat Gambar 1). Produk tiba di gudang setiap hari dan setiap kedatangan merupakan batch terpisah. Secara total, sebagai hasil dari 1 bulan pengoperasian gudang, 30 batch terpisah dibuat, meskipun masing-masing batch harus disimpan dalam sel terpisah. Produk seringkali dipilih tidak dalam palet utuh, tetapi dalam potongan, dan sebagai hasilnya, di zona pemilihan potongan di banyak sel, gambar berikut diamati: dalam sel dengan volume lebih dari 1 m3 ada beberapa potongan crane yang menempati kurang dari 5-10% volume sel.
Gambar 1. Foto beberapa bagian dalam satu sel
Jelas kapasitas penyimpanan tidak digunakan secara maksimal. Untuk membayangkan skala bencana, saya dapat memberikan angka: rata-rata, terdapat 1 hingga 3 sel dengan volume lebih dari 100 m300 dengan saldo βsangat kecilβ selama berbagai periode pengoperasian gudang. Karena ukuran gudang relatif kecil, selama musim sibuk gudang, faktor ini menjadi βhambatanβ dan sangat memperlambat proses penerimaan dan pengiriman gudang.
Ide solusi masalah
Timbul gagasan: kumpulan sisa makanan dengan tanggal terdekat harus dikurangi menjadi satu kumpulan tunggal, dan sisa makanan tersebut dengan kumpulan terpadu harus ditempatkan secara kompak dalam satu sel, atau dalam beberapa sel, jika tidak ada cukup ruang dalam satu sel untuk menampungnya. seluruh jumlah sisa. Contoh βkompresiβ tersebut ditunjukkan pada Gambar 2.
Gambar.2. Skema untuk mengompresi residu dalam sel
Hal ini memungkinkan Anda mengurangi secara signifikan ruang gudang yang ditempati yang akan digunakan untuk penempatan barang baru. Dalam situasi di mana kapasitas gudang kelebihan beban, tindakan seperti itu sangat diperlukan, jika tidak, mungkin tidak ada cukup ruang kosong untuk menampung barang baru, yang akan menyebabkan terhentinya proses penempatan dan pengisian ulang di gudang dan, sebagai konsekuensinya, terhentinya penerimaan dan pengiriman. Sebelumnya, sebelum penerapan sistem WMS, pengoperasian seperti itu dilakukan secara manual, sehingga tidak efektif, karena proses pencarian saldo yang sesuai di dalam sel cukup lama. Kini, dengan diperkenalkannya sistem WMS, kami memutuskan untuk mengotomatiskan proses, mempercepatnya, dan menjadikannya cerdas.
Proses penyelesaian masalah tersebut dibagi menjadi 2 tahap:
- pada tahap pertama kami menemukan kelompok batch yang tanggalnya hampir sama untuk kompresi (khusus untuk tugas ini );
- pada tahap kedua, untuk setiap kelompok batch kami menghitung penempatan sisa barang yang paling kompak di dalam sel.
Pada artikel kali ini kita akan fokus pada algoritma tahap kedua.
Tinjauan solusi yang ada
Sebelum melanjutkan ke deskripsi algoritma yang telah kami kembangkan, ada baiknya melakukan tinjauan singkat tentang sistem yang sudah ada di pasar WMS, yang menerapkan fungsi kompresi optimal serupa.
Pertama-tama, perlu diperhatikan produk β1C: Enterprise 8. WMS Logistics. Manajemen gudang 4", yang dimiliki dan direplikasi oleh 1C dan milik generasi keempat WMS-sistem yang dikembangkan oleh AXELOT. Sistem ini mengklaim fungsionalitas kompresi, yang dirancang untuk menyatukan sisa-sisa produk yang berbeda dalam satu sel yang sama. Perlu disebutkan bahwa fungsi kompresi dalam sistem seperti itu juga mencakup kemungkinan lain, misalnya, mengoreksi penempatan barang di sel sesuai dengan kelas ABC-nya, namun kami tidak akan membahasnya secara mendalam.
Jika Anda menganalisis kode sistem 1C: Enterprise 8. WMS Logistics. Manajemen gudang 4" (yang terbuka di bagian fungsi ini), kita dapat menyimpulkan sebagai berikut. Algoritme kompresi sisa menerapkan logika linier yang agak primitif dan tidak ada pembicaraan tentang kompresi βoptimalβ. Tentu saja, hal ini tidak mengatur pengelompokan partai. Beberapa klien yang menerapkan sistem seperti itu mengeluhkan hasil perencanaan kompresi. Misalnya, dalam praktiknya, situasi berikut sering terjadi selama kompresi: 100 pcs. Direncanakan untuk memindahkan sisa barang dari satu sel ke sel lain, dimana 1 buah berada. barang, meskipun optimal dari sudut pandang konsumsi waktu untuk melakukan hal sebaliknya.
Selain itu, fungsi mengompresi sisa barang dalam sel diumumkan di banyak negara asing. WMS-sistem, tapi, sayangnya, kami tidak memiliki masukan nyata mengenai efektivitas algoritme (ini adalah rahasia dagang), apalagi gagasan tentang kedalaman logikanya (perangkat lunak sumber tertutup berpemilik), jadi kami tidak dapat menilai.
Cari model matematika dari masalahnya
Untuk merancang algoritma berkualitas tinggi untuk memecahkan suatu masalah, pertama-tama kita perlu merumuskan masalah ini secara matematis dengan jelas, itulah yang akan kita lakukan.
Ada banyak sel , yang berisi sisa-sisa beberapa barang. Berikut ini, kita akan menyebut sel-sel tersebut sebagai sel donor. Mari kita tunjukkan volume barang di dalam sel $.
Penting untuk dikatakan bahwa hanya satu produk dari satu batch, atau beberapa batch yang sebelumnya digabungkan menjadi satu cluster (baca: ), hal ini disebabkan oleh kekhususan penyimpanan dan penyimpanan barang. Produk yang berbeda atau kelompok batch yang berbeda harus menjalankan prosedur kompresinya sendiri-sendiri.
Ada banyak sel , di mana residu dari sel donor berpotensi ditempatkan. Kami selanjutnya akan menyebut sel-sel tersebut sebagai sel kontainer. Ini bisa berupa sel gratis di gudang atau sel donor dari berbagai jenis . Selalu banyak adalah bagian .
Untuk setiap sel dari banyak Batasan kapasitas telah ditetapkan , diukur dalam dm3. Satu dm3 berbentuk kubus dengan panjang sisi 10 cm, produk yang disimpan di gudang cukup besar, sehingga dalam hal ini diskritisasi tersebut cukup.
Diberikan matriks jarak terpendek dalam meter antara setiap pasangan sel Dimana ΠΈ milik set ΠΈ masing.
Mari kita tunjukkan βbiayaβ pemindahan barang dari sel ke dalam sel . Mari kita tunjukkan βbiayaβ pemilihan wadah untuk memindahkan residu dari sel lain ke dalamnya. Bagaimana tepatnya dan dalam satuan pengukuran apa nilai-nilai tersebut akan dihitung ΠΈ kita akan pertimbangkan lebih lanjut (lihat bagian menyiapkan data masukan), untuk saat ini cukup dikatakan bahwa nilai tersebut akan berbanding lurus dengan nilai ΠΈ masing.
Mari kita nyatakan dengan variabel yang mengambil nilai 1 jika sisanya berasal dari sel dipindahkan ke wadah , dan 0 sebaliknya. Mari kita nyatakan dengan variabel yang mengambil nilai 1 jika wadahnya berisi sisa barang, dan 0 sebaliknya.
Tugas tersebut dinyatakan sebagai berikut: Anda perlu menemukan begitu banyak kontainer dan dengan demikian βmenempelkanβ sel donor ke sel wadah untuk meminimalkan fungsinya
di bawah pembatasan
Secara total, ketika menghitung solusi masalah, kami berusaha untuk:
- pertama, untuk menghemat kapasitas penyimpanan;
- kedua, untuk menghemat waktu pemilik toko.
Pembatasan terakhir berarti kami tidak dapat memindahkan barang ke dalam wadah yang tidak kami pilih, sehingga tidak βmembebankan biayaβ untuk pemilihannya. Pembatasan ini juga berarti bahwa volume barang yang dipindahkan dari sel ke kontainer tidak boleh melebihi kapasitas kontainer. Yang kami maksud dengan memecahkan suatu masalah adalah sekumpulan wadah dan metode untuk menempelkan sel donor ke wadah.
Rumusan masalah optimasi ini bukanlah hal baru, dan telah dipelajari oleh banyak ahli matematika sejak awal tahun 80an abad yang lalu. Dalam literatur asing terdapat 2 masalah optimasi dengan model matematika yang sesuai: ΠΈ (kita akan membicarakan perbedaan tugas nanti). Patut dikatakan bahwa dalam literatur matematika, rumusan dari dua masalah optimasi tersebut dirumuskan dalam kaitannya dengan lokasi perusahaan di lapangan, oleh karena itu dinamakan βLokasi Fasilitasβ. Hal ini sebagian besar merupakan penghormatan terhadap tradisi, karena kebutuhan untuk memecahkan masalah kombinatorial seperti itu pertama kali datang dari bidang logistik, terutama dari sektor industri militer pada tahun 50-an abad yang lalu. Ditinjau dari lokasi perusahaan, tugas-tugas tersebut dirumuskan sebagai berikut:
- Terdapat sejumlah kota terbatas yang berpotensi untuk menempatkan perusahaan manufaktur (selanjutnya disebut kota manufaktur). Untuk setiap kota manufaktur, biaya pembukaan perusahaan di dalamnya ditentukan, serta batasan kapasitas produksi perusahaan yang dibuka di dalamnya.
- Terdapat sekumpulan kota terbatas di mana klien sebenarnya berada (selanjutnya disebut kota klien). Untuk setiap kota klien tersebut, volume permintaan produk ditentukan. Untuk mempermudah, kita asumsikan hanya ada satu produk yang diproduksi oleh perusahaan dan dikonsumsi oleh pelanggan.
- Untuk setiap pasangan kota-produsen dan kota-klien, nilai biaya transportasi untuk pengiriman volume produk yang diperlukan dari produsen ke klien ditentukan.
Anda perlu mencari kota mana untuk membuka bisnis dan cara menghubungkan klien ke bisnis tersebut untuk:
- Total biaya pembukaan usaha dan biaya transportasi sangat minim;
- Volume permintaan dari pelanggan yang ditugaskan pada perusahaan terbuka mana pun tidak melebihi kapasitas produksi perusahaan tersebut.
Sekarang perlu disebutkan satu-satunya perbedaan dalam dua masalah klasik ini:
- Masalah Lokasi Fasilitas Berkapasitas Sumber Tunggal β klien disuplai hanya dari satu fasilitas terbuka;
- Masalah Lokasi Fasilitas Berkapasitas Multi-Sumber β klien dapat disuplai dari beberapa fasilitas terbuka pada saat yang bersamaan.
Perbedaan antara kedua masalah tersebut pada pandangan pertama tidak signifikan, tetapi, pada kenyataannya, mengarah pada struktur kombinatorial yang sama sekali berbeda dari masalah tersebut dan, sebagai konsekuensinya, pada algoritma yang sama sekali berbeda untuk menyelesaikannya. Perbedaan antara tugas-tugas tersebut ditunjukkan pada gambar di bawah ini.
Gambar.3. a) Masalah Lokasi Fasilitas Berkapasitas Multi-Sumber
Gambar.3. b) Masalah Lokasi Fasilitas Berkapasitas Sumber Tunggal
Kedua tugas -sulit, yaitu tidak ada algoritma pasti yang dapat menyelesaikan masalah seperti itu dalam polinomial waktu dalam ukuran data masukan. Dengan kata sederhana, semua algoritma yang tepat untuk menyelesaikan suatu masalah akan bekerja dalam waktu eksponensial, meskipun mungkin lebih cepat daripada pencarian opsi yang lengkap. Sejak tugas itu -sulit, maka kita hanya akan mempertimbangkan heuristik perkiraan, yaitu algoritma yang secara konsisten akan menghitung solusi yang sangat mendekati optimal dan akan bekerja cukup cepat. Jika Anda tertarik dengan tugas seperti itu, Anda dapat menemukan ikhtisar bagus dalam bahasa Rusia di sini.
Jika kita beralih ke terminologi masalah kompresi barang yang optimal dalam sel, maka:
- kota klien adalah sel donor dengan sisa barang,
- kota manufaktur β sel kontainer , di mana sisa sel lain seharusnya ditempatkan,
- biaya transportasi - biaya waktu penjaga toko untuk memindahkan volume barang dari sel donor ke dalam sel kontainer ;
- biaya membuka usaha - biaya memilih wadah , sama dengan volume sel wadah , dikalikan dengan koefisien tertentu untuk menyimpan volume bebas (nilai koefisien selalu > 1) (lihat bagian menyiapkan data masukan).
Setelah analogi dengan solusi klasik yang terkenal dari masalah tersebut ditarik, perlu untuk menjawab pertanyaan penting yang menjadi dasar pilihan arsitektur algoritma solusi: memindahkan sisa dari sel donor hanya mungkin dilakukan ke satu. dan hanya satu wadah (Single-Source), atau apakah sisanya bisa dipindahkan ke beberapa sel wadah (Multi-Source)?
Perlu dicatat bahwa dalam praktiknya kedua rumusan masalah tersebut terjadi. Kami menyajikan semua pro dan kontra untuk setiap pengaturan di bawah ini:
| Varian masalah | Kelebihan dari opsi ini | Kontra dari opsi |
|---|---|---|
| Sumber tunggal | Operasi pergerakan barang dihitung menggunakan varian soal ini:
|
|
| Multi-Sumber | Kompresi yang dihitung menggunakan versi soal ini biasanya 10-15% lebih kompak dibandingkan dengan kompresi yang dihitung menggunakan opsi βSumber Tunggalβ. Namun kami juga mencatat bahwa semakin kecil jumlah residu dalam sel donor, semakin kecil perbedaan kekompakannya | Operasi pergerakan barang dihitung menggunakan varian soal ini:
|
Tabel 1. Kelebihan dan kekurangan opsi Sumber Tunggal dan Multi Sumber.
Karena opsi Sumber Tunggal memiliki lebih banyak keunggulan, dan juga mempertimbangkan fakta bahwa semakin kecil jumlah residu dalam sel donor, semakin kecil perbedaan derajat kekompakan kompresi yang dihitung untuk kedua varian masalah, pilihan kami jatuh pada opsi Sumber Tunggal.
Patut dikatakan bahwa solusi untuk opsi Multi-Sumber juga ada. Ada sejumlah besar algoritma yang efektif untuk menyelesaikannya, yang sebagian besar bertujuan untuk memecahkan sejumlah masalah transportasi. Ada juga tidak hanya algoritma yang efisien, tetapi juga algoritma yang elegan, misalnya,
Mempersiapkan Data Masukan
Sebelum mulai menganalisis dan mengembangkan suatu algoritma untuk menyelesaikan suatu masalah, perlu diputuskan data apa dan dalam bentuk apa kita akan memasukkannya sebagai masukan. Tidak ada masalah dengan volume sisa barang di sel donor dan kapasitas sel kontainer, karena ini sepele - jumlah tersebut akan diukur dalam m3, tetapi dengan biaya penggunaan sel kontainer dan matriks biaya perpindahan, tidak semuanya sangat sederhana!
Mari kita lihat perhitungannya terlebih dahulu biaya pemindahan barang dari sel donor ke sel wadah. Pertama-tama, perlu diputuskan dalam satuan pengukuran apa kita akan menghitung biaya pergerakan. Dua pilihan yang paling jelas adalah meter dan detik. Tidak masuk akal untuk menghitung biaya perjalanan dalam meteran βmurniβ. Mari kita tunjukkan ini dengan sebuah contoh. Biarkan selnya terletak di tingkat pertama, sel dihapus sejauh 30 meter dan terletak di tingkat kedua:
- Pindah dari Π² lebih mahal daripada pindah dari Π² , karena turun dari tingkat kedua (1,5-2 meter dari lantai) lebih mudah daripada naik ke tingkat kedua, meskipun jaraknya sama;
- Pindahkan 1 buah. barang dari sel Π² Ini akan lebih mudah daripada memindahkan 10 buah. produk yang sama, meskipun jaraknya akan sama.
Lebih baik mempertimbangkan biaya pemindahan dalam hitungan detik, karena ini memungkinkan Anda memperhitungkan perbedaan tingkatan dan perbedaan jumlah barang yang dipindahkan. Untuk memperhitungkan biaya pergerakan dalam hitungan detik, kita harus menguraikan operasi pergerakan menjadi komponen-komponen dasar dan melakukan pengukuran waktu untuk pelaksanaan setiap komponen dasar.
Biarkan dari sel bergerak komputer. barang dalam wadah . Biarkan β kecepatan rata-rata pergerakan seorang pekerja di gudang, diukur dalam m/detik. Membiarkan ΠΈ β kecepatan rata-rata satu kali operasi pengambilan dan penempatan, masing-masing, untuk volume barang yang sama dengan 4 dm3 (volume rata-rata yang diambil seorang karyawan pada suatu waktu di gudang saat melakukan operasi). Membiarkan ΠΈ tinggi sel tempat operasi pengambilan dan penempatan dilakukan. Misalnya tinggi rata-rata tingkat (lantai) pertama adalah 1 m, tingkat kedua adalah 2 m, dan seterusnya. Maka rumus untuk menghitung total waktu menyelesaikan suatu operasi perpindahan adalah berikut:
Tabel 2 menunjukkan statistik waktu pelaksanaan setiap operasi dasar, yang dikumpulkan oleh karyawan gudang, dengan mempertimbangkan spesifikasi barang yang disimpan.
| Nama operasi | Penunjukan | Nilai rata-rata |
|---|---|---|
| Kecepatan rata-rata seorang pekerja bergerak di sekitar gudang | |
1,5 m/s |
| Kecepatan rata-rata satu operasi untuk dilakukan (untuk volume produk 4 dm3) | |
2,4 dtk |
Tabel 2. Rata-rata waktu penyelesaian operasional gudang
Kami telah memutuskan metode penghitungan biaya perpindahan. Sekarang kita perlu memikirkan cara menghitungnya biaya memilih sel kontainer. Segala sesuatu di sini jauh lebih rumit dibandingkan dengan biaya pemindahan, karena:
- pertama, biaya harus berbanding lurus dengan volume sel - lebih baik menempatkan volume residu yang sama yang ditransfer dari sel donor ke dalam wadah dengan volume lebih kecil daripada di wadah besar, asalkan volume tersebut benar-benar muat di kedua wadah. Oleh karena itu, dengan meminimalkan total biaya pemilihan kontainer, kami berusaha untuk menghemat kapasitas penyimpanan gratis yang βlangkaβ di area pemilihan untuk melakukan operasi penempatan barang selanjutnya di dalam sel. Gambar 4 menunjukkan pilihan untuk memindahkan residu ke dalam kontainer besar dan kecil dan konsekuensi dari pilihan pemindahan ini dalam operasi gudang selanjutnya.
- kedua, karena dalam memecahkan masalah awal kita perlu meminimalkan total biaya dengan tepat, dan ini adalah jumlah dari biaya pemindahan dan biaya pemilihan kontainer, maka volume sel dalam meter kubik perlu dihubungkan dengan detik, yang jauh dari kata sepele.
Beras. 4. Pilihan untuk memindahkan sisa makanan ke dalam wadah dengan kapasitas berbeda.
Gambar 4 menunjukkan dengan warna merah volume sisa makanan yang tidak lagi dapat dimasukkan ke dalam wadah pada penempatan barang berikutnya tahap kedua.
Ini akan membantu untuk menghubungkan meter kubik biaya untuk memilih kontainer dengan detik biaya untuk memindahkan persyaratan berikut untuk solusi yang diperhitungkan untuk masalah tersebut:
- Saldo dari wadah donor harus dipindahkan ke wadah penampung jika hal ini mengurangi jumlah total wadah penampung yang berisi produk.
- Penting untuk menjaga keseimbangan antara volume kontainer dan waktu yang dihabiskan untuk perpindahan: misalnya, jika dalam solusi baru suatu masalah dibandingkan dengan solusi sebelumnya, peningkatan volumenya besar, tetapi kerugian waktunya kecil. , maka Anda perlu memilih opsi baru.
Mari kita mulai dengan persyaratan terakhir. Untuk memperjelas kata βkeseimbanganβ yang ambigu, kami melakukan survei terhadap karyawan gudang untuk mengetahui hal berikut. Biarkan ada sel wadah volume , yang mana pergerakan sisa barang dari sel donor ditugaskan dan total waktu pergerakan tersebut sama dengan . Misalkan ada beberapa alternatif pilihan untuk menempatkan barang dalam jumlah yang sama dari sel donor yang sama ke dalam wadah lain, dimana setiap penempatan memiliki perkiraannya masing-masing. Dimana < ΠΈ Dimana >.
Pertanyaan yang diajukan: berapa keuntungan minimum dalam volume dapat diterima, untuk nilai kerugian waktu tertentu ? Mari kita jelaskan dengan sebuah contoh. Semula jenazah seharusnya ditempatkan dalam wadah dengan volume 1000 dm3 (1 m3) dan waktu perpindahan 70 detik. Terdapat pilihan untuk menempatkan residu di wadah lain dengan volume 500 dm3 dan waktu 130 detik. Pertanyaan: apakah kita siap meluangkan tambahan 60 detik waktu pemilik toko untuk memindahkan barang guna menghemat 500 dm3 volume bebas? Berdasarkan hasil survei terhadap pegawai gudang, disusun diagram sebagai berikut.
Beras. 5. Diagram ketergantungan penghematan volume minimum yang diperbolehkan terhadap peningkatan selisih waktu pengoperasian
Artinya, jika biaya waktu tambahan adalah 40 detik, maka kita siap menggunakannya hanya jika perolehan volume minimal 500 dm3. Meskipun terdapat sedikit nonlinier dalam ketergantungan, untuk mempermudah perhitungan lebih lanjut kita asumsikan bahwa ketergantungan antar besaran adalah linier dan dijelaskan oleh pertidaksamaan.
Pada gambar di bawah, kami mempertimbangkan metode penempatan barang dalam kontainer berikut ini.
Beras. 6. Opsi (a): 2 kontainer, total volume 400 dm3, total waktu 150 detik.
Beras. 6. Opsi (b): 2 kontainer, total volume 600 dm3, total waktu 190 detik.
Beras. 6. Opsi (c): 1 kontainer, total volume 400 dm3, total waktu 200 detik.
Opsi (a) untuk memilih kontainer lebih disukai daripada opsi awal, karena pertidaksamaannya berlaku: (800-400)/10>=150-120, yang berarti 40 >= 30. Opsi (b) kurang disukai dibandingkan opsi awal option , karena pertidaksamaan tidak berlaku: (800-600)/10>=190-150 yang berarti 20 >= 40. Namun opsi (c) tidak cocok dengan logika seperti itu! Mari pertimbangkan opsi ini lebih detail. Di satu sisi, ketimpangan (800-400)/10>=200-120, yang berarti ketimpangan 40 >= 80 tidak terpenuhi, yang menunjukkan bahwa peningkatan volume tidak sebanding dengan kerugian yang besar seiring berjalannya waktu.
Namun di sisi lain, dalam opsi (c) ini kita tidak hanya mengurangi total volume yang terisi, namun juga mengurangi jumlah sel yang terisi, yang merupakan persyaratan pertama dari dua persyaratan penting untuk solusi komputasi terhadap permasalahan yang disebutkan di atas. Jelasnya, agar persyaratan ini mulai terpenuhi, perlu menambahkan beberapa konstanta positif ke sisi kiri pertidaksamaan. , dan konstanta tersebut perlu ditambahkan hanya ketika jumlah kontainer berkurang. Mari kita ingat hal itu adalah variabel yang sama dengan 1 ketika wadahnya dipilih, dan 0 saat wadah tidak terpilih. Mari kita tunjukkan β banyak wadah dalam larutan awal dan β banyak kontainer dalam solusi baru. Secara umum ketimpangan baru akan terlihat seperti ini:
Mengubah pertidaksamaan di atas, kita peroleh
Berdasarkan hal tersebut, kami mempunyai rumus untuk menghitung total biaya beberapa solusi untuk masalah ini:
Namun kini muncul pertanyaan: nilai apa yang seharusnya dimiliki oleh konstanta tersebut? ? Tentunya nilainya harus cukup besar agar syarat pertama pemecahan masalah selalu terpenuhi. Anda tentu saja dapat mengambil nilai konstanta sebesar 103 atau 106, tetapi saya ingin menghindari βangka ajaibβ seperti itu. Jika kita mempertimbangkan secara spesifik pelaksanaan operasi gudang, kita dapat menghitung beberapa perkiraan numerik yang masuk akal dari nilai konstanta tersebut.
Biarkan β jarak maksimum antara sel-sel gudang di satu zona ABC, dalam kasus kita sama dengan 100 m. Misalkan β volume maksimum sel kontainer di gudang, dalam kasus kita sama dengan 1000 dm3.
Cara pertama untuk menghitung nilainya . Mari kita pertimbangkan situasi di mana ada 2 kontainer di tingkat pertama, di mana barang-barang tersebut sudah berada secara fisik, yaitu, mereka sendiri adalah sel donor, dan biaya pemindahan barang ke sel yang sama secara alami sama dengan 0. Ini perlu untuk menemukan nilai konstanta tersebut , yang akan menguntungkan jika selalu memindahkan sisa makanan dari wadah 1 ke wadah 2. Mengganti nilainya ΠΈ Dalam pertidaksamaan yang diberikan di atas kita memperoleh:
dari yang berikut
Mengganti nilai waktu rata-rata untuk melakukan operasi dasar ke dalam rumus di atas, kita mendapatkan
Cara kedua untuk menghitung nilainya . Mari kita pertimbangkan situasi di mana ada sel donor yang rencananya akan dipindahkan barangnya ke wadah 1. Mari kita nyatakan β jarak dari sel donor ke container 1. Ada juga container 2 yang sudah berisi barang-barang, dan volumenya memungkinkan untuk menampung sisa semuanya. sel. Untuk mempermudah, kita asumsikan bahwa volume barang yang dipindahkan dari sel donor ke wadah adalah sama dan sama . Diperlukan untuk menemukan nilai konstanta tersebut , di mana penempatan semua sisa dari sel ke dalam wadah 2 akan selalu lebih menguntungkan daripada menempatkannya di wadah yang berbeda:
Mengubah ketimpangan yang kita dapatkan
Untuk βmemperkuatβ nilai kuantitas , mari kita asumsikan itu = 0. Jumlah rata-rata sel yang biasanya terlibat dalam prosedur kompresi saldo gudang adalah 10. Mengganti nilai kuantitas yang diketahui, kita mendapatkan nilai konstanta berikut
Kami mengambil nilai terbesar yang dihitung untuk setiap opsi, ini akan menjadi nilai kuantitas untuk parameter gudang yang diberikan. Nah, untuk kelengkapannya, mari kita tuliskan rumus menghitung total biaya untuk beberapa solusi yang layak :
Sekarang, bagaimanapun juga upaya besar Dengan mentransformasikan data masukan maka dapat dikatakan bahwa seluruh data masukan telah diubah ke bentuk yang diinginkan dan siap digunakan dalam algoritma optimasi.
Kesimpulan
Seperti yang diperlihatkan oleh praktik, kompleksitas dan pentingnya tahap penyiapan dan transformasi data masukan untuk suatu algoritme sering kali diremehkan. Dalam artikel ini, kami secara khusus memberikan banyak perhatian pada tahap ini untuk menunjukkan bahwa hanya data masukan berkualitas tinggi dan disiapkan dengan cerdas yang dapat membuat keputusan yang dihitung oleh algoritme benar-benar berharga bagi klien. Ya, ada banyak turunan rumus, tapi kami sudah memperingatkan Anda bahkan sebelum kata :)
Pada artikel berikutnya kita akhirnya akan sampai pada tujuan dari 2 publikasi sebelumnya - algoritma optimasi diskrit.
Mempersiapkan artikelnya
Roman Shangin, programmer departemen proyek,
Perusahaan Bit pertama, Chelyabinsk
Sumber: www.habr.com