مسئله بسته‌بندی

مساله بسته بندی کلاسیک (انگلیسی: Bin packing problem)، (BPP) ^[۱]^[۲]^[۳]^[۴] به دلیل کاربردهای بسیار زیاد و ساختار ترکیبیاتی خوب آن به طور گسترده ای در مقالات تحقیق در عملیات، علوم کامپیوتر و مهندسی صنایع مورد توجه قرار گرفته است ^[۵]. از دیدگاه نظری این مساله می‌تواند زیر مساله تعداد زیادی از مسائل بهینه‌سازی ترکیبیاتی (مانند مساله مسیریابی خودرو) باشد. این مساله اولین بار در سال 1971 میلادی توسط [اولمان ] معرفی گردید. در مساله بسته‌بندی یک بعدی مجموعه‌ای متنهاهی از اشیاء وزن‌دار باید در کمترین تعداد ممکن از بسته‌های با ظرفیت یکسان قرار داده شود ^[۶].

مسئله بسته‌بندی را می‌توان به عنوان یک حالت خاص از مسئله برش ورق در نظر گرفت.

تعریف و مدلسازی ریاضی مساله بسته‌بندی[ویرایش]

فرض کنید تعداد n شی با وزن‌های w₁، w₂، ... ، w_n داده شده باشد. یک بسته‌بندی از این اشیاء را در کمترین تعداد ممکن از بسته‌های مشابه به ظرفیت واحد پیدا کنید که مجموع وزن اشیاء داخل هر بسته از ظرفیت بسته تجاوز نکند.

مساله بسته‌بندی می تواند به صورت یک مساله برنامه ریزی خطی عدد صحیح و به صورت زیر مدلسازی شود.

minimize $K=\sum _{j=1}^{n}y_{j}$
subject to	$K\geq 1,$
	$\sum _{i\in I}^{n}w(i)x_{ij}\leq By_{j},$	$\forall j\in \{1,\ldots ,n\}$
	$\sum _{j=1}^{n}x_{ij}=1,$	$\forall i\in I$
	$y_{j}\in \{0,1\},$	$\forall j\in \{1,\ldots ,n\}$
	$x_{ij}\in \{0,1\},$	$\forall i\in I\,\forall j\in \{1,\ldots ,n\}$

که در آن $y_{j}=1$ اگر بسته $j$ مورد استفاده قرار گیرد و $x_{ij}=1$ اگر شی $i$ ام در بین $j$ ام بسته بندی شود.^[۷]

پیچیدگی مساله[ویرایش]

مساله بسته‌بندی یک مساله قویاً NP -سخت است. چون حتی در حالتی که همه پارامترهای مساله با یک چند‌جمله‌ای از ابعاد مساله محدود شوند نیز مساله NP -سخت باقی می‌ماند و بنابراین می‌توان نتیجه گرفت که با فرض P≠NP الگوریتمی شبه چندجمله‌ای برای BPP وجود ندارد ^[۸].

به علاوه، هیچ الگوریتم تقریبی با فاکتور تقریب کوچکتر از ${\tfrac {3}{2}}$ برای مساله بسته‌بندی وجود ندارد مگر اینکه ${\mathsf {P}}={\mathsf {NP}}$ . این می‌تواند با کاهش از مسئلهٔ افراز ثابت شود:^[۹] با توجه به نمونه‌ای از مساله افراز که مجموع همهٔ اعداد ورودی $2T$ است، نمونه‌ای از مساله بسته‌بندی را ایجاد کنید که در آن ظرفیت بسته $T$ است. اگر افراز برابر ورودی‌ها وجود داشته باشد، پس بسته‌بندی بهینه نیاز به 2 بسته دارد؛ بنابراین، هر الگوریتم با نسبت تقریب کوچکتر از 3/2 باید کمتر از 3 بسته را برگرداند، که باید 2 بسته باشد. در مقابل، اگر افراز برابر ورودی‌ها وجود نداشته باشد، پس بسته‌بندی بهینه حداقل به 3 بسته نیاز دارد.

الگوریتم های تقریبی برای مساله بسته‌بندی[ویرایش]

برای اندازه‌گیری عملکرد یک الگوریتم تقریبی، دو نوع نسبت تقریب در ادبیات موضوع مورد بررسی قرار می‌گیرند. برای یک لیست داده شده از اشیاء $L$ ، عدد $A(L)$ تعداد بسته‌های استفاده شده را نشان می‌دهد زمانی که الگوریتم $A$ بر روی لیست $L$ اعمال می‌شود، در حالی که $\mathrm {OPT} (L)$ تعداد بهینه برای این لیست را نشان می‌دهد. نسبت عملکرد بدترین حالت مطلق $R_{A}$ برای یک الگوریتم $A$ به صورت زیر تعریف می‌شود:

R_{A}\equiv \inf\{r\geq 1:\forall L\quad A(L)/\mathrm {OPT} (L)\leq r\}.

از طرف دیگر، نسبت بدترین حالت مجانبی $R_{A}^{\infty }$ به صورت زیر تعریف می‌شود:

R_{A}^{\infty }\equiv \inf\{r\geq 1:\exists N>0,\forall L\ (\mathrm {OPT} (L)\geq N)\quad A(L)/\mathrm {OPT} (L)\leq r\}.

به طور معادل، $R_{A}^{\infty }$ کوچکترین عددی است که برای ثابت Kای و برای همهٔ لیست‌های L:^[۴]

A(L)\leq R_{A}^{\infty }\cdot \mathrm {OPT} (L)+K

.

علاوه بر این، می‌توان لیست‌ها را به آنهایی محدود کرد که همهٔ اشیاء در آن‌ها اندازه‌ای حداکثر $\alpha$ دارند. برای چنین لیست‌هایی، نسبت‌های عملکرد اندازه محدود به صورت $R_{A}({\text{size}}\leq \alpha )$ و $R_{A}^{\infty }({\text{size}}\leq \alpha )$ نشان داده می‌شوند.

الگوریتم‌های تقریبی برای بسته‌بندی در جعبه می‌توانند به دو دسته تقسیم شوند:

هیوریستیک‌های آنلاین، که اشیاء را در ترتیب داده شده در نظر می‌گیرند و آن‌ها را یکی یکی درون بسته‌ها قرار می‌دهند. این هیوریستیک‌ها همچنین قابل اجرا برای نسخهٔ آنلاین این مسئله هستند.
هیوریستیک‌های آفلاین، که لیست داده شده از اشیاء را تغییر می‌دهند، به عنوان مثال با مرتب‌سازی اشیاء بر اساس اندازه. این الگوریتم‌ها دیگر قابل اجرا برای نسخهٔ آنلاین این مسئله نیستند. با این حال، آن‌ها یک تضمین تقریب بهبود یافته دارند در حالی که مزیت پیچیدگی زمان کوچک خود را حفظ می‌کنند. یک زیر دسته از هیوریستیک‌های آفلاین، طرح‌های تقریب مجانبی است. این الگوریتم‌ها یک تضمین تقریب به شکل $(1+\varepsilon )\mathrm {OPT} (L)+C$ دارند برای بعضی ثابت که ممکن است بستگی به $1/\varepsilon$ داشته باشد. برای یک $\mathrm {OPT} (L)$ به صورت دلخواه بزرگ، این الگوریتم‌ها به صورت دلخواه نزدیک به $\mathrm {OPT} (L)$ می‌شوند. با این حال، این به قیمت افزایش (شدید) پیچیدگی زمانی در مقایسه با رویکردهای هیوریستیک‌ است.

جستارهای وابسته[ویرایش]

منابع[ویرایش]

↑ Martello, Silvano; Toth, Paolo (1990), "Bin-packing problem" (PDF), Knapsack Problems: Algorithms and Computer Implementations, Chichester, UK: John Wiley and Sons, ISBN 0471924202
↑ Korte, Bernhard; Vygen, Jens (2006). "Bin-Packing". Combinatorial Optimization: Theory and Algorithms. Algorithms and Combinatorics 21. Springer. pp. 426–441. doi:10.1007/3-540-29297-7_18. ISBN 978-3-540-25684-7.
↑ Barrington, David Mix (2006). "Bin Packing". Archived from the original on 2019-02-16. Retrieved 2016-02-27.
↑ ^۴٫۰ ^۴٫۱ Coffman Jr., Edward G.; Csirik, János; Galambos, Gábor; Martello, Silvano; Vigo, Daniele (2013), Pardalos, Panos M.; Du, Ding-Zhu; Graham, Ronald L. (eds.), "Bin Packing Approximation Algorithms: Survey and Classification", Handbook of Combinatorial Optimization (به انگلیسی), New York, NY: Springer, pp. 455–531, doi:10.1007/978-1-4419-7997-1_35, ISBN 978-1-4419-7997-1, retrieved 2021-08-08
↑ Nejoomi, A., & Dolati, A. (2022). Connected bin packing problem on traceable graphs. Iranian Journal of Numerical Analysis and Optimization, 12(1), 163-171. doi: 10.22067/ijnao.2021.67913.1010^{^{[پیوند مرده]}}
↑ Vazirani, Vijay V. "Approximation algorithms". Springer Science & Business Media, 2013.
↑ (Martello و Toth 1990، ص. 221)
↑ نجومی، احمد و دولتی، اردشیر،1399،مساله بسته‌بندی همبند: معرفی، مدلسازی و الگوریتم،سیزدهمین کنفرانس بین المللی انجمن ایرانی تحقیق در عملیات،شاهرود،https://civilica.com/doc/1124986
↑ Vazirani, Vijay V. (14 مارس 2013). الگوریتم‌های تقریبی. Springer Berlin Heidelberg. p. 74. ISBN 978-3662045657.

مشارکت‌کنندگان ویکی‌پدیا. «Bin packing problem». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲ سپتامبر ۲۰۱۶.

[1] Martello, Silvano; Toth, Paolo (1990), "Bin-packing problem" (PDF), Knapsack Problems: Algorithms and Computer Implementations, Chichester, UK: John Wiley and Sons, ISBN 0471924202

[2] Korte, Bernhard; Vygen, Jens (2006). "Bin-Packing". Combinatorial Optimization: Theory and Algorithms. Algorithms and Combinatorics 21. Springer. pp. 426–441. doi:10.1007/3-540-29297-7_18. ISBN 978-3-540-25684-7.

[3] Barrington, David Mix (2006). "Bin Packing". Archived from the original on 2019-02-16. Retrieved 2016-02-27.

[:0-4] ۴٫۰ ^۴٫۱ Coffman Jr., Edward G.; Csirik, János; Galambos, Gábor; Martello, Silvano; Vigo, Daniele (2013), Pardalos, Panos M.; Du, Ding-Zhu; Graham, Ronald L. (eds.), "Bin Packing Approximation Algorithms: Survey and Classification", Handbook of Combinatorial Optimization (به انگلیسی), New York, NY: Springer, pp. 455–531, doi:10.1007/978-1-4419-7997-1_35, ISBN 978-1-4419-7997-1, retrieved 2021-08-08

[5] Nejoomi, A., & Dolati, A. (2022). Connected bin packing problem on traceable graphs. Iranian Journal of Numerical Analysis and Optimization, 12(1), 163-171. doi: 10.22067/ijnao.2021.67913.1010^{^{[پیوند مرده]}}

[6] Vazirani, Vijay V. "Approximation algorithms". Springer Science & Business Media, 2013.

[Martello19902-7] (Martello و Toth 1990، ص. 221)

[8] نجومی، احمد و دولتی، اردشیر،1399،مساله بسته‌بندی همبند: معرفی، مدلسازی و الگوریتم،سیزدهمین کنفرانس بین المللی انجمن ایرانی تحقیق در عملیات،شاهرود،https://civilica.com/doc/1124986

[9] Vazirani, Vijay V. (14 مارس 2013). الگوریتم‌های تقریبی. Springer Berlin Heidelberg. p. 74. ISBN 978-3662045657.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]