مسئله بسته‌بندی: تفاوت میان نسخه‌ها

محتوای حذف‌شده محتوای افزوده‌شده

درخط

نسخهٔ ‏۱۰ مهٔ ۲۰۲۳، ساعت ۰۸:۲۴

مساله بسته بندی کلاسیک (انگلیسی: Bin packing problem)، (BPP) (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 وجود ندارد ^[۸].

جستارهای وابسته

منابع

↑ 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

مشارکت‌کنندگان ویکی‌پدیا. «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

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

نسخهٔ ‏۱۰ مهٔ ۲۰۲۳، ساعت ۰۸:۲۱ ویرایش Markiddi (بحث \| مشارکت‌ها) ۳۸ ویرایش‌ها اصلاح مقدمه. ترجمه قبلی یک ترجمه نادرست و غیر تخصصی با گوگل ترانسلیت بود. برچسب‌ها: ویرایش همراه ویرایش از وبگاه همراه → تفاوت قدیمی‌تر		نسخهٔ ‏۱۰ مهٔ ۲۰۲۳، ساعت ۰۸:۲۴ ویرایش خنثی‌سازی Markiddi (بحث \| مشارکت‌ها) ۳۸ ویرایش‌ها افزودن منابع تحقیقاتی برچسب‌ها: ویرایش همراه ویرایش از وبگاه همراه تفاوت جدیدتر ←
خط ۱:		خط ۱:

	مساله بسته بندی کلاسیک {{lang-en\|Bin packing problem}})، (BPP) به دلیل کاربردهای بسیار زیاد و ساختار ترکیبیاتی خوب آن به طور گسترده ای در مقالات تحقیق در عملیات، علوم کامپیوتر و مهندسی صنایع مورد توجه قرار گرفته است <ref>[https://ijnao.um.ac.ir/article%2040635.html 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]</ref>. از دیدگاه نظری این مساله می‌تواند زیر مساله تعداد زیادی از مسائل بهینه‌سازی ترکیبیاتی (مانند مساله مسیریابی خودرو) باشد. این مساله اولین بار در سال 1971 میلادی توسط [[https://findingaids.princeton.edu/catalog/ENG027_c0038 اولمان ]] معرفی گردید. در مساله بسته بندی یک بعدی مجموعه‌ای متنهاهی از اشیاء وزن‌دار باید در کمترین تعداد ممکن از بسته‌های با ظرفیت یکسان قرار داده شود <ref>Vazirani, Vijay V. "Approximation algorithms". Springer Science & Business Media, 2013.</ref>.		مساله بسته بندی کلاسیک ({{lang-en\|Bin packing problem}})، (BPP) (BPP) <ref>{{citation\|last1=Martello\|first1=Silvano\|title=Knapsack Problems: Algorithms and Computer Implementations\|url=https://archive.org/details/knapsackproblems0000mart\|year=1990\|chapter=Bin-packing problem\|chapter-url=http://www.or.deis.unibo.it/kp/Chapter8.pdf\|location=Chichester, UK\|publisher=John Wiley and Sons\|isbn=0471924202\|last2=Toth\|first2=Paolo\|url-access=registration}}</ref><ref>{{cite book\|last1=Korte\|first1=Bernhard\|title=Combinatorial Optimization: Theory and Algorithms\|last2=Vygen\|first2=Jens\|publisher=Springer\|year=2006\|isbn=978-3-540-25684-7\|series=Algorithms and Combinatorics 21\|pages=426–441\|chapter=Bin-Packing\|doi=10.1007/3-540-29297-7_18\|chapter-url=https://books.google.com/books?id=UnYwgPltSjwC&q=Bin-Packing&pg=PA449}}</ref><ref>{{cite web\|last=Barrington\|first=David Mix\|year=2006\|title=Bin Packing\|url=https://people.cs.umass.edu/~barring/cs311/disc/11.html\|url-status=dead\|archive-url=https://web.archive.org/web/20190216134619/https://people.cs.umass.edu/~barring/cs311/disc/11.html\|archive-date=2019-02-16\|access-date=2016-02-27}}</ref><ref name=":0">{{Citation\|last1=Coffman Jr.\|first1=Edward G.\|title=Bin Packing Approximation Algorithms: Survey and Classification\|date=2013\|url=https://doi.org/10.1007/978-1-4419-7997-1_35\|work=Handbook of Combinatorial Optimization\|pages=455–531\|editor-last=Pardalos\|editor-first=Panos M.\|place=New York, NY\|publisher=Springer\|language=en\|doi=10.1007/978-1-4419-7997-1_35\|isbn=978-1-4419-7997-1\|access-date=2021-08-08\|last2=Csirik\|first2=János\|last3=Galambos\|first3=Gábor\|last4=Martello\|first4=Silvano\|last5=Vigo\|first5=Daniele\|editor2-last=Du\|editor2-first=Ding-Zhu\|editor3-last=Graham\|editor3-first=Ronald L.}}</ref> به دلیل کاربردهای بسیار زیاد و ساختار ترکیبیاتی خوب آن به طور گسترده ای در مقالات تحقیق در عملیات، علوم کامپیوتر و مهندسی صنایع مورد توجه قرار گرفته است <ref>[https://ijnao.um.ac.ir/article%2040635.html 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]</ref>. از دیدگاه نظری این مساله می‌تواند زیر مساله تعداد زیادی از مسائل بهینه‌سازی ترکیبیاتی (مانند مساله مسیریابی خودرو) باشد. این مساله اولین بار در سال 1971 میلادی توسط [[https://findingaids.princeton.edu/catalog/ENG027_c0038 اولمان ]] معرفی گردید. در مساله بسته بندی یک بعدی مجموعه‌ای متنهاهی از اشیاء وزن‌دار باید در کمترین تعداد ممکن از بسته‌های با ظرفیت یکسان قرار داده شود <ref>Vazirani, Vijay V. "Approximation algorithms". Springer Science & Business Media, 2013.</ref>.

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