pemotongan guillotine versus pemotongan umum

Masalah pemotongan adalah masalah di mana benda besar tertentu harus dipotong menjadi beberapa benda kecil. Sebagai contoh, bayangkan Anda memiliki sebuah pabrik yang bekerja dengan lembaran kaca besar baku, lebar dan panjang L . Ada beberapa pembeli, yang masing-masing menginginkan jumlah lembaran kaca kecil tanpa batas. Pembeli saya ingin lembaran panjang l i dan lebar w i . Tujuan Anda adalah untuk memotong lembaran kecil dari yang besar, sehingga total yang digunakan dimaksimalkan dan limbah diminimalkan (ada juga jenis lain masalah pemotongan dan pengepakan ).$W$$L$$i$$l_i$$w_i$

Salah satu batasan umum dalam masalah pemotongan adalah bahwa potongan harus potongan guillotine , yaitu, setiap persegi panjang yang ada dapat dipotong hanya untuk dua persegi panjang yang lebih kecil; tidak mungkin untuk membuat bentuk-L dll. Jelas, area maksimum yang digunakan dengan potongan guillotine mungkin lebih kecil dari area maksimum yang digunakan tanpa batasan.

Pertanyaan saya adalah: Apakah ada batas atas dan bawah pada rasio antara potongan guillotine optimal dan potongan umum optimal?

Pekerjaan terkait: Song et al. (2009) menjelaskan suatu algoritma yang menggunakan tipe pemotongan guillotine yang terbatas - pemotongan dua kali-guillotine . Mereka membuktikan, dengan menggunakan batasan geometris, bahwa rasio antara potongan dua kali guillotine maksimum dengan potongan guillotine maksimum dibatasi oleh . Saya mencari hasil yang sebanding tentang rasio antara potongan guillotine maksimum dengan potongan umum maksimum.$\frac{6}{7}$

Meskipun hal ini tidak ketat, saya dapat menawarkan batas bawah dan atas dari dan 3 / 4 pada rasio kasus terburuk antara pemotongan guillotine dan pemotongan umum.$1/4$$3/4$

Mari kita mulai dengan batas atas dan menganggap kita diberi selembar kaca persegi dengan panjang sisi . Selain itu, kami memiliki tepat satu pembeli yang tertarik pada lembaran kaca persegi panjang lebar 1 - ε dan panjang 1 + ε . Menggunakan potongan umum, solusi optimal terlihat seperti gambar berikut, dengan empat persegi panjang yang diinginkan ditempatkan di sekitar kotak kecil dengan panjang sisi ε di tengah.$2$$1-\varepsilon$$1+\varepsilon$$\varepsilon$

Sangat mudah untuk melihat bahwa pola pemotongan ini tidak dapat dicapai melalui pemotongan guillotine. Faktanya, setiap pola pemotongan menggunakan potongan guillotine dapat memuat paling banyak 3 dari persegi panjang yang diinginkan ke dalam kotak asli. Akibatnya, rasio terburuk antara pemotongan guillotine dan pemotongan umum setidaknya .$3/4$

$W$$L$$i$$w_i \leq W$$l_i \leq L$$i$

$i$$1/4$

Saya sadar bahwa batas bawah cukup lemah dan mungkin dapat ditingkatkan dengan sedikit lebih banyak pekerjaan. Tapi ini awal.