Spesialis pengemasan dari Mainz: nomor satu di seluruh dunia

Ilmuwan Mainz mengalahkan rekor dunia untuk susunan piringan bundar terbaik - Publikasi dalam Tinjauan Fisik E

Bagaimana cara memuat mobil agar semuanya pas? Bagaimana saya bisa mengemas sebuah paket sehingga terisi dengan benar? Berapa banyak piring yang ada di lemari dapur? Dalam hal pengemasan, para ilmuwan Mainz tidak terkalahkan. Mereka semua mampu memecahkan atau mengalahkan rekor dunia yang dibuat dalam kompetisi internasional untuk solusi terbaik untuk masalah pengemasan khusus.

"Kami telah bekerja selama beberapa waktu dalam proyek interdisipliner antara fisika teoretis dan ilmu komputer untuk mengembangkan algoritme komputer terbaik untuk masalah pengemasan," jelas Dr. Johannes Josef Schneider dari fokus yang baru didirikan pada metode penelitian berbantuan komputer dalam ilmu alam di Johannes Gutenberg University Mainz. Ketika para ilmuwan mengetahui tentang kompetisi sesaat sebelum berakhir, mereka hanya dapat mencetak satu rekor dunia, jika tidak, hasil dari beberapa kelompok lain sedikit lebih baik. Didorong oleh ambisi untuk mengalahkan kelompok-kelompok terbaik dunia, beberapa di antaranya telah mengerjakan masalah seperti itu selama bertahun-tahun, mereka mengembangkan lebih lanjut algoritma komputer mereka dan sekarang mampu melemahkan rekor dunia yang dibuat selama kompetisi, dan sebagian besar secara signifikan . Karya itu diterbitkan dalam jurnal terkenal untuk fisika statistik Tinjauan Fisik E.

Kompetisi ini tentang mengatur cakram bundar dengan ukuran berbeda dalam lingkaran sedemikian rupa sehingga mereka mengambil ruang sesedikit mungkin. Jari-jari lingkaran besar di mana cakram yang lebih kecil dikemas karenanya harus sekecil mungkin. 155 kelompok dari 32 negara mengikuti kompetisi dan menyerahkan solusi mereka. Untuk masalah dengan 24 hingga maksimal 50 piringan bundar dengan ukuran berbeda, Schneider, Prof. Dr. Elmar Schömer dari Institut Ilmu Komputer dan mahasiswa pascasarjana André Müller menemukan solusi terbaik sejauh ini. Untuk masalah yang lebih kecil dengan 23 disk dan kurang, mereka setara dengan solusi terbaik sejauh ini - yang menunjukkan bahwa tidak ada solusi yang lebih baik. "Untuk masalah ini dengan disk melingkar berukuran berbeda, kami telah mengembangkan algoritme pengemasan terbaik di dunia," rangkum Schneider.

Namun, para ilmuwan tidak hanya mempertimbangkan masalah ilmiah seperti itu, tetapi juga mentransfer algoritme mereka ke aplikasi praktis. Misalnya, grup sedang menyelidiki bagaimana volume bagasi dapat diukur dengan baik untuk pabrikan mobil besar Jerman. Menurut standar yang ditetapkan oleh Uni Eropa, Tetrapak dengan ukuran tertentu harus dikemas ke dalam bagasi tertentu sedemikian rupa sehingga ruang diisi sebanyak mungkin. “Hingga saat ini, balok kayu telah digunakan untuk menampung sebanyak mungkin Tetrapaks,” jelas Schneider. Di Amerika Serikat, di sisi lain, set koper dari super-kaya harus dikemas seoptimal mungkin di bagasi, itulah sebabnya informasi tentang berapa banyak ruang yang ada di bagasi tidak cukup cocok antara Jerman dan Amerika. brosur iklan. Berdasarkan perbandingan dengan hasil kompetisi, para ilmuwan kini memiliki kepastian bahwa algoritma mereka juga dapat secara optimal menyelesaikan masalah pengepakan bagasi ini.

Tetapi algoritme pengoptimalan seperti itu juga dapat digunakan untuk pertanyaan yang sama sekali berbeda. Misalnya, perjalanan dari pabrik susu ke peternakan dapat dioptimalkan sehingga jarak yang ditempuh truk untuk mengumpulkan susu sesingkat mungkin - tergantung pada urutan pendekatan peternakan. Contoh lain dari industri otomotif adalah perakitan akhir kendaraan: Dengan bantuan komputer, dapat ditentukan di mana urutan masing-masing badan prefabrikasi harus dibawa ke jalur perakitan sehingga produksi dapat dilakukan dengan biaya yang efektif. mungkin. Ada juga kompetisi untuk masalah seperti itu, beberapa di antaranya bahkan diselenggarakan oleh perusahaan. Sebagai mahasiswa doktoral di Regensburg, Schneider sendiri menempati posisi keempat dalam kompetisi yang diadakan oleh produsen mobil Bavaria beberapa tahun yang lalu, meninggalkan perusahaan yang didirikan di bidang optimasi dan mempekerjakan seluruh kelompok orang untuk kompetisi jauh di belakang.

Para ilmuwan Mainz menemukan metode solusi terbaik dengan mendekati solusi dengan mendekatinya. Untuk tujuan ini, peristiwa acak disimulasikan di komputer dengan simulasi Monte Carlo - dinamai menurut distrik Monaco dengan kasino terkenal. "Ini bekerja seperti di kasino, di mana nomor dua belas muncul secara acak di meja roulette, dan komputer secara acak menghasilkan pengaturan," jelas Schneider. Dalam contoh dengan disk melingkar, komputer kemudian memindahkan salah satu disk ke suatu tempat dan membandingkan solusi baru ini dengan yang sebelumnya. Perubahan ini akan dibatalkan jika tingkat degradasi terlalu besar, jika tidak, solusi baru akan tetap ada. "Dengan cara ini, Anda mengubah susunan piringan bundar selangkah demi selangkah hingga Anda mendapatkan hasil akhir."

Sangat mengejutkan bahwa berbagai solusi yang hampir sama baiknya dengan solusi terbaik seringkali memiliki kesamaan. Menurut Schneider, ada struktur yang umum. Dalam kompetisi cakram bundar, misalnya, cakram bundar terbesar seringkali berdekatan dalam solusi yang baik. Kesamaan yang dimiliki oleh solusi yang baik dan solusi terbaik adalah apa yang sedang diselidiki oleh para ilmuwan dalam karya mereka sendiri, yang juga akan segera diterbitkan dalam Physical Review E.

Fokus untuk metode penelitian berbantuan komputer dalam ilmu alam baru saja didirikan oleh Universitas Johannes Gutenberg untuk lebih mendukung posisi luar biasa ilmu alam di Mainz dengan ilmu komputer yang kuat dan inovatif.

karya asli:

André Müller, Johannes J. Schneider, Elmar Schömer Mengemas sistem hard disk multidispersi dalam lingkungan melingkar Tinjauan Fisik E, Volume 79, Nomor 021102, 2 Februari 2009

Sumber: Mainz [JGU]