बिन पैकिंग की समस्या

Not to be confused with बिन पैकिंग.

बिन पैकिंग समस्या एक अनुकूलन समस्या है, जिसमें विभिन्न आकार की वस्तुओं को सीमित संख्या में बिन में पैक किया जाना चाहिए या प्रत्येक निश्चित क्षमता के कंटेनर, इस तरह से कि उपयोग किए गए बिन की संख्या कम से कम हो। समस्या जैसे कंटेनर भरना, वजन क्षमता की कमी वाले ट्रकों को लोड करना, मीडिया में फ़ाइल बैकअप बनाना और एफपीजीए अर्धचालक चिप डिजाइन में प्रौद्योगिकी मैपिंग के कई अनुप्रयोग हैं।

कम्प्यूटेशनल रूप से, समस्या एनपी-हार्ड है, और संबंधित निर्णय समस्या - यह तय करना कि क्या वस्तुएं निर्दिष्ट संख्या में बिन में फिट हो सकती हैं -एनपी-कम्पलीट है। इसकी सबसे खराब स्थिति के बावजूद, समस्या के बहुत बड़े उदाहरणों के लिए इष्टतम समाधान परिष्कृत एल्गोरिदम के साथ उत्पादित किए जा सकते हैं। इसके अतिरिक्त, अनेक सन्निकटन एल्गोरिदम मौजूद हैं। उदाहरण के लिए, पहला फ़िट एल्गोरिथ्म एक तेज़ लेकिन अक्सर गैर-इष्टतम समाधान प्रदान करता है, जिसमें प्रत्येक वस्तु को पहले बिन में रखना शामिल होता है जिसमें वह फिट होगा। इसके लिए Θ(n log n) समय की आवश्यकता होती है, जहां n पैक किए जाने वाले वस्तु की संख्या है। वस्तुओं की सूची को पहले घटते क्रम में क्रमबद्ध करके एल्गोरिदम को और अधिक प्रभावी बनाया जा सकता है (कभी-कभी इसे प्रथम-फिट घटते एल्गोरिदम के रूप में जाना जाता है), हालाँकि यह अभी भी एक इष्टतम समाधान की गारंटी नहीं देता है और लंबी सूचियों के लिए एल्गोरिदम के चलने के समय में वृद्धि हो सकती है। हालाँकि, यह ज्ञात है कि वस्तुओं का कम से कम एक ऑर्डर हमेशा मौजूद रहता है जो फर्स्ट-फ़िट को एक इष्टतम समाधान तैयार करने की अनुमति देता है।

इस समस्या के कई रूप हैं, जैसे 2D पैकिंग, रैखिक पैकिंग, वजन के हिसाब से पैकिंग, लागत के हिसाब से पैकिंग, इत्यादि। बिन पैकिंग की समस्या को स्टॉक में कटौती की समस्या के एक विशेष मामले के रूप में भी देखा जा सकता है। जब बिन की संख्या 1 तक सीमित होती है और प्रत्येक वस्तु की मात्रा और मूल्य दोनों की विशेषता होती है, तो बिन में फिट होने वाली वस्तुओं के मूल्य को अधिकतम करने की समस्या को नैपसैक समस्या के रूप में जाना जाता है।

बिन पैकिंग का एक प्रकार जो व्यवहार में आता है वह तब होता है जब वस्तुओं को बिन में पैक करने पर स्थान साझा किया जा सकता है। विशेष रूप से, वस्तुओं का एक समुच्चय अपने अलग-अलग आकारों के योग की तुलना में एक साथ पैक किए जाने पर कम जगह घेर सकता है। इस प्रकार को वीएम पैकिंग के रूप में जाना जाता है क्योंकि जब वर्चुअल मशीन (VM) को सर्वर में पैक किया जाता है, तो वीएम द्वारा साझा किए गए पृष्ठों के कारण उनकी कुल मेमोरी आवश्यकता कम हो सकती है, जिन्हें केवल एक बार संग्रहीत करने की आवश्यकता होती है। यदि वस्तुएँ मनमाने ढंग से स्थान साझा कर सकती हैं, तो बिन पैकिंग की समस्या का अनुमान लगाना भी कठिन है। हालाँकि, यदि स्पेस शेयरिंग एक पदानुक्रम में फिट होती है, जैसा कि वर्चुअल मशीनों में मेमोरी शेयरिंग के मामले में है, तो बिन पैकिंग समस्या का कुशलतापूर्वक अनुमान लगाया जा सकता है।

व्यवहार में रुचि रखने वाली बिन पैकिंग का एक अन्य प्रकार तथाकथित ऑनलाइन बिन पैकिंग है। यहां अलग-अलग मात्रा की वस्तुओं को क्रमिक रूप से आना चाहिए, और निर्णय निर्माता को यह तय करना होगा कि वर्तमान में देखी गई वस्तु को चुनना और पैक करना है या फिर उसे पास कर देना है। प्रत्येक निर्णय बिना किसी स्मरण के होता है। इसके विपरीत, ऑफ़लाइन बिन पैकिंग अतिरिक्त वस्तु आने पर बेहतर पैकिंग प्राप्त करने की आशा में वस्तुओं को पुनर्व्यवस्थित करने की अनुमति देती है। बेशक, पुनर्व्यवस्थित की जाने वाली वस्तुओं को रखने के लिए अतिरिक्त भंडारण की आवश्यकता होती है।

औपचारिक कथन

कंप्यूटर और इंट्रैक्टेबिलिटी में गैरी और जॉनसन ने संदर्भ [SR1] के तहत बिन पैकिंग समस्या को सूचीबद्ध किया है। वे इसके निर्णय प्रकार को निम्नानुसार परिभाषित करते हैं।

उदाहरण: परिमित समुच्चय $I$ वस्तुओं का, एक आकार $s(i)\in \mathbb {Z} ^{+}$ प्रत्येक के लिए $i\in I$, एक धनात्मक पूर्णांक बिन क्षमता $B$, और एक सकारात्मक पूर्णांक $K$.

प्रश्न: क्या इसका कोई विभाजन है? $I$ असंयुक्त समुच्चय में $I_{1},\dots ,I_{K}$ इस प्रकार कि प्रत्येक में वस्तु के आकार का योग $I_{j}$ $B$ या कम है?

ध्यान दें कि साहित्य में अक्सर समकक्ष संकेतन का उपयोग किया जाता है, जहां $B=1$ और $s(i)\in \mathbb {Q} \cap (0,1]$ प्रत्येक के लिए $i\in I$. इसके अलावा, अनुसंधान ज्यादातर अनुकूलन संस्करण में रुचि रखता है, जो न्यूनतम संभव मूल्य मांगता है $K$. कोई समाधान इष्टतम होता है यदि उसमें न्यूनतम हो $K$. $K$वें-वस्तुओं के एक समुच्चय के लिए इष्टतम समाधान के लिए मूल्य $I$ द्वारा निरूपित किया जाता है $\mathrm {OPT} (I)$ या केवल $\mathrm {OPT}$ यदि मदों का समुच्चय संदर्भ से स्पष्ट है।

समस्या का एक संभावित पूर्णांक प्रोग्रामिंग सूत्रीकरण है:

minimize $K=\sum _{j=1}^{n}y_{j}$
subject to	$K\geq 1,$
	$\sum _{i\in I}s(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$ में डाल दिया जाता है

बिन पैकिंग की कठोरता

बिन पैकिंग समस्या सशक्त एनपी-पूर्णता|दृढ़तापूर्वक एनपी-पूर्णता है। इसे बिन पैकिंग में एनपी-कम्पलीट 3-विभाजन समस्या को कम करके सिद्ध किया जा सकता है।

इसके अलावा, पूर्ण सन्निकटन अनुपात से छोटा कोई सन्निकटन एल्गोरिदम नहीं हो सकता है ${\tfrac {3}{2}}$ जब तक ${\mathsf {P}}={\mathsf {NP}}$. इसे विभाजन समस्या को कम करके सिद्ध किया जा सकता है: विभाजन का एक उदाहरण दिया गया है जहां सभी इनपुट संख्याओं का योग $2T$ है, बिन-पैकिंग का एक उदाहरण बनाएं जिसमें बिन का आकार हो T. यदि इनपुट का समान विभाजन मौजूद है, तो इष्टतम पैकिंग के लिए 2 बिन की आवश्यकता होती है; इसलिए, प्रत्येक एल्गोरिदम का सन्निकटन अनुपात इससे छोटा होता है 3/2 को 3 बिन से कम लौटाना होगा, जो कि 2 बिन होने चाहिए। इसके विपरीत, यदि इनपुट का कोई समान विभाजन नहीं है, तो इष्टतम पैकिंग के लिए कम से कम 3 बिन की आवश्यकता होती है।

दूसरी ओर, बिन पैकिंग किसी भी निश्चित संख्या में बिन के लिए छद्म-बहुपद समय में हल करने योग्य है K, और किसी भी निश्चित बिन क्षमता B के लिए बहुपद समय में हल करने योग्य है।

बिन पैकिंग के लिए अनुमान एल्गोरिदम

सन्निकटन एल्गोरिदम के प्रदर्शन को मापने के लिए साहित्य में दो सन्निकटन अनुपातों पर विचार किया गया है। वस्तुओं की दी गई सूची के लिए $L$ जो नंबर $A(L)$ एल्गोरिथ्म के दौरान उपयोग किए गए बिन की संख्या को दर्शाता है $A$ सूची में लागू किया जाता है $L$, जबकि $\mathrm {OPT} (L)$ इस सूची के लिए इष्टतम संख्या को दर्शाता है। सबसे खराब स्थिति वाला प्रदर्शन अनुपात $R_{A}$ एक एल्गोरिदम के लिए $A$ परिभाषित किया जाता है।

$R_{A}\equiv \inf\{r\geq 1:A(L)/\mathrm {OPT} (L)\leq r{\text{ for all lists }}L\}.$

दूसरी ओर, स्पर्शोन्मुख सबसे खराब स्थिति का अनुपात $R_{A}^{\infty }$ परिभाषित किया जाता है।

$R_{A}^{\infty }\equiv \inf\{r\geq 1:\exists N>0,A(L)/\mathrm {OPT} (L)\leq r{\text{ for all lists }}L{\text{ with }}\mathrm {OPT} (L)\geq N\}.$

समान रूप से, $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. ऑनलाइन अनुमान, जो किसी दिए गए क्रम में वस्तुओं पर विचार करते हैं और उन्हें एक-एक करके बिन के अंदर रखते हैं। ये अनुमान इस समस्या के ऑनलाइन संस्करण पर भी लागू होते हैं।
2. ऑफ़लाइन आंकड़े, जो दी गई वस्तुओं की सूची को संशोधित करते हैं, उदा. वस्तुओं को आकार के अनुसार क्रमबद्ध करके। ये एल्गोरिदम अब इस समस्या के ऑनलाइन संस्करण पर लागू नहीं हैं। हालाँकि, उनकी छोटी समय-जटिलता के लाभ को बनाए रखते हुए उनके पास बेहतर सन्निकटन गारंटी है। ऑफ़लाइन अनुमानों की एक उप-श्रेणी स्पर्शोन्मुख सन्निकटन योजनाएँ हैं। इन एल्गोरिदम में फॉर्म की अनुमानित गारंटी होती है $(1+\varepsilon )\mathrm {OPT} (L)+C$ कुछ स्थिरांक के लिए जिस पर निर्भर हो सकता है $1/\varepsilon$. मनमाने ढंग से बड़े के लिए $\mathrm {OPT} (L)$ ये एल्गोरिदम मनमाने ढंग से करीब आ जाते हैं $\mathrm {OPT} (L)$. हालाँकि, यह अनुमानी दृष्टिकोण की तुलना में (काफी) बढ़ी हुई समय जटिलता की कीमत पर आता है।

ऑनलाइन अनुमान

बिन पैकिंग समस्या के ऑनलाइन एल्गोरिदम संस्करण में, वस्तु एक के बाद एक आते हैं और (अपरिवर्तनीय) निर्णय यह जानने से पहले किया जाता है कि किसी वस्तु को कहां रखा जाए, अगला वस्तु जानने से पहले या यहां तक ​​​​कि कोई दूसरा वस्तु होगा या नहीं। बिन-पैकिंग के लिए ऑफ़लाइन और ऑनलाइन अनुमानों के एक विविध समुच्चय का अध्ययन डेविड एस. जॉनसन ने अपनी पीएचडी में किया है। थीसिस.

एकल-श्रेणी एल्गोरिदम

ऐसे कई सरल एल्गोरिदम हैं जो निम्नलिखित सामान्य योजना का उपयोग करते हैं:

• इनपुट सूची में प्रत्येक वस्तु के लिए:
  1. यदि वस्तु वर्तमान में खुले बिन में फिट होती है, तो उसे इनमें से किसी एक बिन में डाल दें;
  2. अन्यथा, एक नया बिन खोलें और उसमें नई वस्तु डालें।

एल्गोरिदम उस मानदंड में भिन्न होते हैं जिसके द्वारा वे चरण 1 में नए वस्तु के लिए खुले बिन का चयन करते हैं (अधिक जानकारी के लिए लिंक किए गए पेज देखें):

• नेक्स्ट-फिट बिन पैकिंग (एनएफ) हमेशा एक खुला बिन रखता है। जब नई वस्तु इसमें फिट नहीं होती है, तो यह वर्तमान बिन को बंद कर देता है और एक नया बिन खोलता है। इसका लाभ यह है कि यह एक बाउंडेड-स्पेस एल्गोरिदम है क्योंकि इसे मेमोरी में केवल एक खुला बिन रखने की आवश्यकता होती है। इसका नुकसान यह है कि इसका स्पर्शोन्मुख सन्निकटन अनुपात 2 है। विशेष रूप से, $NF(L)\leq 2\cdot \mathrm {OPT} (L)-1$, और प्रत्येक के लिए $N\in \mathbb {N}$ वहाँ एक सूची मौजूद है L ऐसा है कि $\mathrm {OPT} (L)=N$ और $NF(L)=2\cdot \mathrm {OPT} (L)-2$.वस्तु के आकार के आधार पर इसके स्पर्शोन्मुख सन्निकटन अनुपात में कुछ हद तक सुधार किया जा सकता है: $R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 2$ सभी के लिए $\alpha \geq 1/2$ और $R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 1/(1-\alpha )$ सभी के लिए $\alpha \leq 1/2$. प्रत्येक एल्गोरिदम के लिए A यह एक AnyFit-एल्गोरिदम है जो इसे धारण करता है $R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{NF}^{\infty }({\text{size}}\leq \alpha )$.
• नेक्स्ट-फिट बिन पैकिंग|नेक्स्ट-के-फिट (एनकेएफ) नेक्स्ट-फिट का एक प्रकार है, लेकिन एल्गोरिदम केवल एक बिन को खुला रखने के बजाय आखिरी को रखता है। k बिन खुलते हैं और पहला बिन चुनते हैं जिसमें वस्तु फिट होती है। इसलिए, इसे k-बाउंडेड स्पेस एल्गोरिथम कहा जाता है। के लिए $k\geq 2$ एनकेएफ ऐसे परिणाम देता है जो एनएफ के परिणामों की तुलना में बेहतर होते हैं, हालांकि, बढ़ रहे हैं k से बड़े स्थिर मानों के लिए 2 अपने सबसे खराब स्थिति वाले व्यवहार में एल्गोरिदम को और बेहतर नहीं बनाता है। यदि एल्गोरिदम A एक ऑलमोस्टएनीफिट-एल्गोरिदम है और $m=\lfloor 1/\alpha \rfloor \geq 2$ तब $R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{N2F}^{\infty }({\text{size}}\leq \alpha )=1+1/m$.* फर्स्ट-फिट बिन पैकिंग|फर्स्ट-फिट (एफएफ) सभी बिन को उसी क्रम में खुला रखता है, जिस क्रम में वे खोले गए थे। यह प्रत्येक नई वस्तु को पहले बिन में रखने का प्रयास करता है जिसमें वह फिट होती है। इसका सन्निकटन अनुपात है $FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor$, और इनपुट सूचियों का एक परिवार है L जिसके लिए $FF(L)$ इस सीमा से मेल खाता है।
• बेस्ट-फिट बिन पैकिंग|बेस्ट-फिट (बीएफ), भी, सभी बिन खुले रखता है, लेकिन प्रत्येक नए वस्तु को अधिकतम लोड के साथ बिन में रखने का प्रयास करता है जिसमें वह फिट बैठता है। इसका सन्निकटन अनुपात FF के समान है, अर्थात: $BF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor$, और इनपुट सूचियों का एक परिवार है L जिसके लिए $BF(L)$ इस सीमा से मेल खाता है.
• वर्स्ट-फिट (डब्ल्यूएफ) प्रत्येक नई वस्तु को न्यूनतम लोड के साथ बिन में रखने का प्रयास करता है। यह नेक्स्ट-फ़िट जितना बुरा व्यवहार कर सकता है, और उसके लिए सबसे खराब स्थिति वाली सूची में ऐसा करेगा $NF(L)=2\cdot \mathrm {OPT} (L)-2$. इसके अलावा, यह ऐसा मानता है $R_{WF}^{\infty }({\text{size}}\leq \alpha )=R_{NF}^{\infty }({\text{size}}\leq \alpha )$. चूँकि WF एक AnyFit-एल्गोरिदम है, इसलिए ऐसा AnyFit-एल्गोरिदम मौजूद है $R_{AF}^{\infty }(\alpha )=R_{NF}^{\infty }(\alpha )$.* लगभग सबसे खराब-फिट (एडब्ल्यूएफ) प्रत्येक नई वस्तु को दूसरे सबसे खाली खुले कूड़ेदान (या यदि ऐसे दो बिन हैं तो सबसे खाली बिन) के अंदर रखने का प्रयास करता है। यदि यह फिट नहीं होता है, तो यह सबसे खाली प्रयास करता है। इसका स्पर्शोन्मुख सबसे खराब स्थिति का अनुपात है ${\tfrac {17}{10}}$.इन परिणामों को सामान्यीकृत करने के लिए, जॉनसन ने ऑनलाइन हेयुरिस्टिक्स के दो वर्ग पेश किए जिन्हें एनी-फिट एल्गोरिदम और ऑलमोस्ट-एनी-फिट एल्गोरिदम कहा जाता है:'
• AnyFit (AF) एल्गोरिथम में, यदि वर्तमान गैर-रिक्त बिन B हैं₁,...,बी_j, तो वर्तमान वस्तु को बी में पैक नहीं किया जाएगा_j+1 जब तक कि यह बी में से किसी में फिट न हो₁,...,बी_j. एफएफ, डब्ल्यूएफ, बीएफ और एडब्ल्यूएफ एल्गोरिदम इस शर्त को पूरा करते हैं। जॉनसन ने किसी भी AnyFit एल्गोरिथम A और किसी के लिए भी यह साबित कर दिया $\alpha$:

  $R_{FF}^{\infty }(\alpha )\leq R_{A}^{\infty }(\alpha )\leq R_{WF}^{\infty }(\alpha )$.

• ऑलमोस्टएनीफिट (एएएफ) एल्गोरिदम में, यदि वर्तमान गैर-रिक्त बिन बी हैं₁,...,बी_j, और इन बिन में से, बी_kसबसे छोटे भार वाला अद्वितीय बिन है, तो वर्तमान वस्तु को बी में पैक नहीं किया जाएगा_k, जब तक कि वह अपनी बाईं ओर के किसी भी बिन में फिट न हो जाए। एफएफ, बीएफ और एडब्ल्यूएफ एल्गोरिदम इस शर्त को पूरा करते हैं, लेकिन डब्ल्यूएफ नहीं करता है। जॉनसन ने यह साबित किया, किसी भी एएएफ एल्गोरिदम ए और किसी के लिए α:

  $R_{A}^{\infty }(\alpha )=R_{FF}^{\infty }(\alpha )$ विशेष रूप से: $R_{A}^{\infty }=1.7$.

परिष्कृत एल्गोरिदम

उन अनुमानों के साथ बेहतर सन्निकटन अनुपात संभव है जो AnyFit नहीं हैं। ये अनुमान आम तौर पर विभिन्न आकार श्रेणियों की वस्तुओं के लिए समर्पित खुले बिन के कई वर्ग रखते हैं (अधिक जानकारी के लिए लिंक किए गए पेज देखें):

• परिष्कृत प्रथम-फिट बिन पैकिंग |रिफाइंड-फर्स्ट-फिट बिन पैकिंग (आरएफएफ) वस्तु के आकार को चार श्रेणियों में विभाजित करता है: $\left({\frac {1}{2}},1\right]$, $\left({\frac {2}{5}},{\frac {1}{2}}\right]$, $\left({\frac {1}{3}},{\frac {2}{5}}\right]$, और $\left(0,{\frac {1}{3}}\right]$. इसी प्रकार, बिन को चार वर्गों में वर्गीकृत किया गया है। अगला वस्तु $i\in L$ सबसे पहले इसके संबंधित वर्ग को सौंपा गया है। उस वर्ग के अंदर, इसे फर्स्ट-फिट बिन पैकिंग|फर्स्ट-फिट का उपयोग करके एक बिन को सौंपा गया है। ध्यान दें कि यह एल्गोरिदम कोई भी-फिट एल्गोरिदम नहीं है क्योंकि यह इस तथ्य के बावजूद एक नया बिन खोल सकता है कि वर्तमान वस्तु एक खुले बिन के अंदर फिट बैठता है। यह एल्गोरिदम सबसे पहले एंड्रयू ची-चिह याओ द्वारा प्रस्तुत किया गया था, जिसने साबित कर दिया कि इसकी अनुमानित गारंटी है $RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5$ और सूचियों का एक परिवार प्रस्तुत किया $L_{k}$ साथ $RFF(L_{k})=(5/3)\mathrm {OPT} (L_{k})+1/3$ के लिए $\mathrm {OPT} (L)=6k+1$.
• हार्मोनिक बिन पैकिंग|हार्मोनिक-के आकार के अंतराल को विभाजित करता है $(0,1]$ एक हार्मोनिक प्रगति (गणित) पर आधारित $k-1$ टुकड़े $I_{j}:=\left({\frac {1}{j+1}},{\frac {1}{j}}\right]$ के लिए $1\leq j<k$ और $I_{k}:=\left(0,{\frac {1}{k}}\right]$ ऐसा है कि $\bigcup _{j=1}^{k}I_{j}=(0,1]$. इस एल्गोरिथम का वर्णन सबसे पहले ली और ली द्वारा किया गया था। इसमें समय की जटिलता है ${\mathcal {O}}(|L|\log(|L|))$ और प्रत्येक चरण पर, अधिकतम होते हैं k खुले बिन जिनका उपयोग संभावित रूप से वस्तुओं को रखने के लिए किया जा सकता है, यानी, यह एक है k-बाउंडेड स्पेस एल्गोरिदम। के लिए $k\rightarrow \infty$, इसका सन्निकटन अनुपात संतुष्ट करता है $R_{Hk}^{\infty }\approx 1.6910$, और यह स्पर्शोन्मुख रूप से तंग है।
• हार्मोनिक बिन पैकिंग|रिफाइंड-हार्मोनिक, हार्मोनिक-के के विचारों को रिफाइंड फर्स्ट-फिट बिन पैकिंग|रिफाइंड-फर्स्ट-फिट के विचारों के साथ जोड़ता है। यह वस्तुओं को इससे बड़ा रखता है ${\tfrac {1}{3}}$ रिफाइंड-फर्स्ट-फ़िट के समान, जबकि छोटी वस्तुओं को हार्मोनिक-के का उपयोग करके रखा जाता है। इस रणनीति का उद्देश्य उन बिन के लिए भारी अपशिष्ट को कम करना है जिनमें बड़े टुकड़े होते हैं ${\tfrac {1}{2}}$. इस एल्गोरिथम का वर्णन सबसे पहले ली और ली द्वारा किया गया था। उन्होंने ये बात साबित कर दी $k=20$ यह उसे धारण करता है $R_{RH}^{\infty }\leq 373/228$.

ऑनलाइन एल्गोरिदम के लिए सामान्य निचली सीमाएं

याओ1980 में साबित हुआ कि एसिम्प्टोटिक प्रतिस्पर्धी अनुपात से छोटा कोई ऑनलाइन एल्गोरिदम नहीं हो सकता है ${\tfrac {3}{2}}$. भूरा और लिआंग इस बाध्यता में सुधार हुआ 1.53635. बाद में, इस सीमा में सुधार किया गया 1.54014 Vliet द्वारा. 2012 में, बेकेसी और गैलाम्बोस द्वारा इस निचली सीमा में फिर से सुधार किया गया को ${\tfrac {248}{161}}\approx 1.54037$.

तुलना तालिका

Algorithm	Approximation guarantee	Worst case list $L$	Time-complexity
Next-fit (NF)	$NF(L)\leq 2\cdot \mathrm {OPT} (L)-1$	$NF(L)=2\cdot \mathrm {OPT} (L)-2$	${\mathcal {O}}(|L|)$
First-fit (FF)	$FF(L)\leq \lfloor 1.7\mathrm {OPT} (L)\rfloor$	$FF(L)=\lfloor 1.7\mathrm {OPT} (L)\rfloor$	${\mathcal {O}}(|L|\log(|L|))$
Best-fit (BF)	$BF(L)\leq \lfloor 1.7\mathrm {OPT} (L)\rfloor$	$BF(L)=\lfloor 1.7\mathrm {OPT} (L)\rfloor$	${\mathcal {O}}(|L|\log(|L|))$
Worst-Fit (WF)	$WF(L)\leq 2\cdot \mathrm {OPT} (L)-1$	$WF(L)=2\cdot \mathrm {OPT} (L)-2$	${\mathcal {O}}(|L|\log(|L|))$
Almost-Worst-Fit (AWF)	$R_{AWF}^{\infty }\leq 17/10$	$R_{AWF}^{\infty }=17/10$	${\mathcal {O}}(|L|\log(|L|))$
Refined-First-Fit (RFF)	$RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5$	$RFF(L)=(5/3)\mathrm {OPT} (L)+1/3$ (for $\mathrm {OPT} (L)=6k+1$)	${\mathcal {O}}(|L|\log(|L|))$
Harmonic-k (Hk)	$R_{Hk}^{\infty }\leq 1.69103$ for $k\rightarrow \infty$	$R_{Hk}^{\infty }\geq 1.69103$	${\mathcal {O}}(|L|\log(|L|)$
Refined Harmonic (RH)	$R_{RH}^{\infty }\leq 373/228\approx 1.63597$		${\mathcal {O}}(|L|)$
Modified Harmonic (MH)	$R_{MH}^{\infty }\leq 538/33\approx 1.61562$
Modified Harmonic 2 (MH2)	$R_{MH2}^{\infty }\leq 239091/148304\approx 1.61217$
Harmonic + 1 (H+1)		$R_{H+1}^{\infty }\geq 1.59217$
Harmonic ++ (H++)	$R_{H++}^{\infty }\leq 1.58889$	$R_{H++}^{\infty }\geq 1.58333$

ऑफ़लाइन एल्गोरिदम

बिन पैकिंग के ऑफ़लाइन संस्करण में, एल्गोरिदम सभी वस्तुओं को बिन में रखना शुरू करने से पहले देख सकता है। यह बेहतर सन्निकटन अनुपात प्राप्त करने की अनुमति देता है।

गुणात्मक सन्निकटन

ऑफ़लाइन एल्गोरिदम द्वारा उपयोग की जाने वाली सबसे सरल तकनीक है:

• इनपुट सूची को घटते आकार के अनुसार क्रमित करना;
• ऑर्डर की गई सूची पर एक ऑनलाइन एल्गोरिदम चलाएँ।

जॉनसनसाबित हुआ कि किसी भी AnyFit एल्गोरिदम ए जो अवरोही आकार द्वारा क्रमित सूची पर चलता है, उसमें <ब्लॉककोट> का स्पर्शोन्मुख सन्निकटन अनुपात होता है$1.22\approx {\frac {11}{9}}\leq R_{A}^{\infty }\leq {\frac {5}{4}}=1.25$.इस परिवार में कुछ एल्गोरिदम हैं (अधिक जानकारी के लिए लिंक किए गए पेज देखें):

• प्रथम-फिट-घटती बिन पैकिंग |फर्स्ट-फिट-डिक्रीजिंग (एफएफडी) - वस्तु को घटते आकार के आधार पर ऑर्डर करता है, फिर फर्स्ट-फिट को कॉल करता है। इसका सन्निकटन अनुपात है $FFD(I)={\frac {11}{9}}\mathrm {OPT} (I)+{\frac {6}{9}}$, और यह तंग है.
• अगला-फिट-घटता हुआ (एनएफडी) - वस्तुओं को घटते आकार के आधार पर ऑर्डर करता है, फिर नेक्स्ट-फिट बिन पैकिंग|नेक्स्ट-फिट को कॉल करता है। इसका अनुमानित अनुपात सबसे खराब स्थिति में 1.7 से थोड़ा कम है। इसका संभाव्य विश्लेषण भी किया गया है। नेक्स्ट-फ़िट एक सूची और उसके व्युत्क्रम को समान संख्या में बिन में पैक करता है। इसलिए, नेक्स्ट-फिट-इंक्रीजिंग का प्रदर्शन नेक्स्ट-फिट-डिक्रीजिंग के समान ही है।
• संशोधित प्रथम-फिट-घटती (एमएफएफडी)- आकार के आधार पर वस्तुओं को बड़े, मध्यम, छोटे और छोटे आकार के चार वर्गों में वर्गीकृत करके आधे बिन से बड़ी वस्तुओं के लिए एफएफडी में सुधार किया जाता है, क्रमशः> 1/2 बिन,> 1/3 बिन,> 1/6 बिन और छोटे आकार वाली वस्तुओं के अनुरूप। इसकी सन्निकटन गारंटी है $MFFD(I)\leq {\frac {71}{60}}\mathrm {OPT} (I)+1$.

फर्नांडीज डे ला वेगा और ल्यूकेर बिन पैकिंग के लिए एक बहुपद-समय सन्निकटन योजना प्रस्तुत की। हरएक के लिए $\varepsilon >0$, उनका एल्गोरिदम अधिकतम आकार के साथ एक समाधान ढूंढता है $(1+\varepsilon )\mathrm {OPT} +1$ और समय पर चलता है ${\mathcal {O}}(n\log(1/\varepsilon ))+{\mathcal {O}}_{\varepsilon }(1)$, जहाँ ${\mathcal {O}}_{\varepsilon }(1)$ किसी फ़ंक्शन को केवल उस पर निर्भर दर्शाता है $1/\varepsilon$. इस एल्गोरिदम के लिए, उन्होंने अनुकूली इनपुट राउंडिंग की विधि का आविष्कार किया: इनपुट संख्याओं को समूहीकृत किया जाता है और प्रत्येक समूह में अधिकतम मूल्य तक पूर्णांकित किया जाता है। यह विभिन्न आकारों की एक छोटी संख्या के साथ एक उदाहरण उत्पन्न करता है, जिसे विन्यास रैखिक कार्यक्रम का उपयोग करके बिल्कुल हल किया जा सकता है।

योगात्मक सन्निकटन

करमरकर-कार्प बिन पैकिंग एल्गोरिदम | करमरकर-कार्प बिन पैकिंग एल्गोरिदम अधिकतम आकार के साथ एक समाधान ढूंढता है $\mathrm {OPT} +{\mathcal {O}}(\log ^{2}(\mathrm {OPT} ))$, और समय बहुपद में चलता है n (बहुपद की डिग्री उच्च होती है - कम से कम 8)।

रोथवॉस एक एल्गोरिदम प्रस्तुत किया जो अधिक से अधिक समाधान उत्पन्न करता है $\mathrm {OPT} +{\mathcal {O}}(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))$ बिन.

होबर्ग और रोथवॉस अधिक से अधिक समाधान उत्पन्न करने के लिए इस एल्गोरिथम में सुधार किया गया $\mathrm {OPT} +{\mathcal {O}}(\log(\mathrm {OPT} ))$ बिन. एल्गोरिथ्म यादृच्छिक है, और इसका रनिंग-टाइम बहुपद है n.

तुलना तालिका

Algorithm	Approximation guarantee	Worst case instance
First-fit-decreasing (FFD)	$\mathrm {FFD} (I)\leq {\frac {11}{9}}\mathrm {OPT} (I)+{\frac {6}{9}}$	$\mathrm {FFD} (I)={\frac {11}{9}}\mathrm {OPT} (I)+{\frac {6}{9}}$
Modified-first-fit-decreasing (MFFD)	$\mathrm {MFFD} (I)\leq {\frac {71}{60}}\mathrm {OPT} (I)+1$	$R_{\mathrm {MFFD} }^{\infty }\geq {\frac {71}{60}}$
Karmarkar and Karp	$\mathrm {KK} (I)\leq \mathrm {OPT} (I)+O(\log ^{2}{\mathrm {OPT} (I)})$
Rothvoss	$\mathrm {HB} (I)\leq \mathrm {OPT} (I)+O(\log {\mathrm {OPT} (I)}\log \log {\mathrm {OPT} (I)})$
Hoberg and Rothvoss	$\mathrm {HB} (I)\leq \mathrm {OPT} (I)+O(\log {\mathrm {OPT} (I)})$

सटीक एल्गोरिदम

मार्टेलो और टोथ 1-आयामी बिन-पैकिंग समस्या के लिए एक सटीक एल्गोरिदम विकसित किया, जिसे एमटीपी कहा जाता है। एक तेज़ विकल्प 2002 में कोर्फ द्वारा प्रस्तावित बिन कंप्लीशन एल्गोरिदम है और बाद में सुधार हुआ. 2013 में श्रेइबर और कोर्फ द्वारा एक और सुधार प्रस्तुत किया गया। नए बेहतर बिन कंप्लीशन एल्गोरिदम को 100 वस्तुओं के साथ गैर-तुच्छ समस्याओं पर बिन कंप्लीशन की तुलना में परिमाण के पांच ऑर्डर तक तेज दिखाया गया है, और इष्टतम समाधान के रूप में 20 बिन से कम वाली समस्याओं पर बेलोव और शेइथाउर द्वारा बीसीपी (ब्रांच-एंड-कट-एंड-प्राइस) एल्गोरिदम से बेहतर प्रदर्शन करता है। कौन सा एल्गोरिदम सबसे अच्छा प्रदर्शन करता है यह समस्या के गुणों जैसे वस्तुओं की संख्या, बिन की इष्टतम संख्या, इष्टतम समाधान में अप्रयुक्त स्थान और मूल्य परिशुद्धता पर निर्भर करता है।

विभिन्न आकारों की छोटी संख्या

बिन पैकिंग का एक विशेष मामला तब होता है जब विभिन्न वस्तु आकारों की एक छोटी संख्या होती है। प्रत्येक आकार की कई अलग-अलग वस्तुएँ हो सकती हैं। इस मामले को उच्च बहुलता बिन पैकिंग भी कहा जाता है, और यह सामान्य समस्या की तुलना में अधिक कुशल एल्गोरिदम को स्वीकार करता है।

विखंडन के साथ बिन-पैकिंग

विखंडन या खंडित वस्तु बिन-पैकिंग के साथ बिन-पैकिंग बिन पैकिंग समस्या का एक प्रकार है जिसमें वस्तुओं को भागों में तोड़ने और प्रत्येक भाग को अलग-अलग बिन पर अलग से रखने की अनुमति होती है। वस्तुओं को भागों में तोड़ने से समग्र प्रदर्शन में सुधार हो सकता है, उदाहरण के लिए, कुल बिन की संख्या को कम करना। इसके अलावा, इष्टतम शेड्यूल खोजने की कम्प्यूटेशनल समस्या आसान हो सकती है, क्योंकि कुछ अनुकूलन चर निरंतर हो जाते हैं। दूसरी ओर, वस्तुओं को अलग करना महंगा पड़ सकता है। यह समस्या सबसे पहले मंडल, चक्रवर्ती और घोष द्वारा प्रस्तुत की गई थी।

वेरिएंट

समस्या के दो मुख्य रूप हैं.

1. पहले संस्करण में, जिसे आकार-बढ़ती विखंडन (बीपी-एसआईएफ) के साथ बिन-पैकिंग कहा जाता है, प्रत्येक वस्तु खंडित हो सकता है; प्रत्येक टुकड़े के आकार में ओवरहेड इकाइयाँ जोड़ी जाती हैं।
2. दूसरे संस्करण में, जिसे आकार-संरक्षण विखंडन (बीपी-एसपीएफ) के साथ बिन-पैकिंग कहा जाता है, प्रत्येक वस्तु का एक आकार और एक लागत होती है; किसी वस्तु को खंडित करने से उसकी लागत बढ़ जाती है लेकिन उसका आकार नहीं बदलता।

कम्प्यूटेशनल जटिलता

मंडल, चक्रवर्ती और घोषसाबित हुआ कि बीपी-एसपीएफ एनपी-कठोरता |एनपी-हार्ड है।

मेनकेरमैन और रोम पता चला कि बीपी-एसआईएफ और बीपी-एसपीएफ दोनों दृढ़ता से एनपी-हार्ड हैं। कठोरता के बावजूद, वे कई एल्गोरिदम प्रस्तुत करते हैं और उनके प्रदर्शन की जांच करते हैं। उनके एल्गोरिदम बिन-पैकिंग के लिए क्लासिक एल्गोरिदम का उपयोग करते हैं, जैसे नेक्स्ट-फिट बिन पैकिंग|नेक्स्ट-फिट और फर्स्ट-फिट-डिक्रीजिंग बिन पैकिंग|फर्स्ट-फिट डिक्रीजिंग, उनके एल्गोरिदम के आधार के रूप में।

बर्टाज़ी, गोल्डन और वांग के साथ BP-SIF का एक संस्करण पेश किया $1-x$ विभाजन नियम: किसी वस्तु को उसके आकार के अनुसार केवल एक ही तरीके से विभाजित करने की अनुमति है। उदाहरण के लिए, यह वाहन रूटिंग समस्या के लिए उपयोगी है। अपने पेपर में, वे वेरिएंट का सबसे खराब प्रदर्शन प्रदान करते हैं।

शचनाई, तामीर और येहेज़केली बीपी-एसआईएफ और बीपी-एसपीएफ के लिए विकसित सन्निकटन योजनाएं; एक दोहरी बहुपद-समय सन्निकटन योजना (समस्या के दोहरे संस्करण के लिए एक पीटीएएस), एक एसिम्प्टोटिक पीटीएएस जिसे एपीटीएएस कहा जाता है, और एक दोहरी एसिम्प्टोटिक fptas जिसे दोनों संस्करणों के लिए एएफपीटीएएस कहा जाता है।

एकिसि बीपी-एसपीएफ का एक प्रकार पेश किया गया जिसमें कुछ वस्तुएं विवादित हैं, और विवादित वस्तुओं के टुकड़ों को एक ही बिन में पैक करना मना है। उन्होंने साबित कर दिया कि यह वैरिएंट भी एनपी-हार्ड है।

कैसाज़ा और सेसेली बिना किसी लागत और बिना किसी ओवरहेड वाला एक संस्करण पेश किया गया है, और बिन की संख्या निश्चित है। हालाँकि, विखंडन की संख्या कम होनी चाहिए। वे सटीक और अनुमानित दोनों समाधानों के लिए गणितीय प्रोग्रामिंग एल्गोरिदम प्रस्तुत करते हैं।

संबंधित समस्याएँ

दंड के साथ फ्रैक्शनल नैपसेक समस्या की समस्या मालागुटी, मोनासी, पारोनुज़ी और पफ़र्स्की द्वारा पेश की गई थी। उन्होंने समस्या के लिए एक एफपीटीएएस और एक गतिशील प्रोग्रामिंग विकसित की, और उन्होंने अपने मॉडलों के प्रदर्शन की तुलना करते हुए एक व्यापक कम्प्यूटेशनल अध्ययन दिखाया। यह भी देखें: आंशिक कार्य शेड्यूलिंग।

बिन पर कार्डिनैलिटी बाधाएँ

बिन पैकिंग का एक प्रकार है जिसमें बिन पर कार्डिनैलिटी बाधाएं होती हैं: प्रत्येक बिन में कुछ निश्चित पूर्णांक k के लिए अधिकतम k वस्तु हो सकते हैं।

• क्राउज़, शेन और श्वेटमैन इस समस्या को इष्टतम कार्य शेड्यूलिंग के एक प्रकार के रूप में प्रस्तुत करें: एक कंप्यूटर में कुछ k प्रोसेसर होते हैं। कुछ n नौकरियाँ ऐसी हैं जिनमें इकाई समय लगता है (1), लेकिन उनकी मेमोरी आवश्यकताएँ भिन्न होती हैं। प्रत्येक समय-इकाई को एक ही बिन माना जाता है। लक्ष्य यथासंभव कम बिन (=समय इकाइयाँ) का उपयोग करना है, जबकि यह सुनिश्चित करना है कि प्रत्येक बिन में, अधिकतम k नौकरियाँ चलती हैं। वे कई अनुमानी एल्गोरिदम प्रस्तुत करते हैं जो अधिक से अधिक समाधान ढूंढते हैं $2\mathrm {OPT}$ बिन.
• केलरर और पफ़रस्की रन-टाइम के साथ एक एल्गोरिदम प्रस्तुत करें $O(n^{2}\log {n})$, वह अधिक से अधिक समाधान ढूंढ लेता है $\left\lceil {\frac {3}{2}}\mathrm {OPT} \right\rceil$ बिन. उनका एल्गोरिदम ओपीटी के लिए बाइनरी खोज करता है। प्रत्येक खोजे गए मान m के लिए, यह वस्तु को 3m/2 बिन में पैक करने का प्रयास करता है।

गैर-योगात्मक कार्य

बिन-पैकिंग मॉडल को अधिक सामान्य लागत और लोड कार्यों तक विस्तारित करने के कई तरीके हैं:

• अनिली, ब्रैमल और सिम्ची-लेवी एक सेटिंग का अध्ययन करें जहां एक बिन की लागत बिन में वस्तुओं की संख्या का एक अवतल कार्य है। इसका उद्देश्य कूड़ेदानों की संख्या के बजाय कुल लागत को कम करना है। वे दिखाते हैं कि अगली-फिट-बढ़ती बिन पैकिंग अधिकतम 7/4 का पूर्णतः सबसे खराब-मामला सन्निकटन अनुपात प्राप्त करती है, और किसी भी अवतल और मोनोटोन लागत फ़ंक्शन के लिए 1.691 का एक एसिम्प्टोटिक सबसे खराब-मामला अनुपात प्राप्त करती है।
• कोहेन, केलर, मिर्रोकनी और ज़दिमोघदाम ऐसी सेटिंग का अध्ययन करें जहां वस्तु का आकार पहले से ज्ञात नहीं है, लेकिन यह एक यादृच्छिक चर है। यह क्लाउड कम्प्यूटिंग वातावरण में विशेष रूप से आम है। हालाँकि एक निश्चित उपयोगकर्ता के लिए आवश्यक संसाधनों की मात्रा की ऊपरी सीमा होती है, अधिकांश उपयोगकर्ता क्षमता से बहुत कम उपयोग करते हैं। इसलिए, क्लाउड मैनेजर को थोड़ी सी स्मृति अति प्रतिबद्धता से बहुत फायदा हो सकता है। यह मौका बाधाओं के साथ बिन पैकिंग के एक प्रकार को प्रेरित करता है: प्रत्येक बिन में आकारों का योग अधिकतम बी होने की संभावना कम से कम पी होनी चाहिए, जहां पी एक निश्चित स्थिरांक है (मानक बिन पैकिंग पी = 1 से मेल खाती है)। वे दिखाते हैं कि, हल्की धारणाओं के तहत, यह समस्या एक सबमॉड्यूलर बिन पैकिंग समस्या के बराबर है, जिसमें प्रत्येक बिन में लोड वस्तुओं के योग के बराबर नहीं है, बल्कि इसके एक निश्चित सबमॉड्यूलर समुच्चय फ़ंक्शन के बराबर है।

संबंधित समस्याएँ

बिन पैकिंग समस्या में, बिन का आकार निश्चित होता है और उनकी संख्या बढ़ाई जा सकती है (लेकिन यथासंभव छोटी होनी चाहिए)।

इसके विपरीत, मल्टीवे संख्या विभाजन' समस्या में, बिन की संख्या निश्चित होती है और उनका आकार बढ़ाया जा सकता है। उद्देश्य एक ऐसा विभाजन ढूंढना है जिसमें बिन का आकार लगभग बराबर हो (मल्टीप्रोसेसर शेड्यूलिंग|'मल्टीप्रोसेसर शेड्यूलिंग' समस्या या 'न्यूनतम मेकस्पैन' समस्या नामक संस्करण में, लक्ष्य विशेष रूप से सबसे बड़े बिन के आकार को कम करना है)।

'उलटा बिन पैकिंग' समस्या में, बिन की संख्या और उनके आकार दोनों निश्चित हैं, लेकिन वस्तुओं का आकार बदला जा सकता है। इसका उद्देश्य वस्तु आकार वेक्टर में न्यूनतम गड़बड़ी प्राप्त करना है ताकि सभी वस्तुओं को निर्धारित संख्या में बिन में पैक किया जा सके।

अधिकतम संसाधन बिन पैकिंग समस्या में, लक्ष्य उपयोग किए गए बिन की संख्या को अधिकतम करना है, ताकि, बिन के कुछ ऑर्डर के लिए, बाद के बिन में कोई भी वस्तु पहले वाले बिन में फिट न हो। दोहरी समस्या में, बिन की संख्या तय की जाती है, और लक्ष्य बिन में रखी गई वस्तुओं की कुल संख्या या कुल आकार को कम करना है, ताकि कोई भी शेष वस्तु बिना भरे बिन में फिट न हो।

'बिन कवरिंग समस्या' में, बिन का आकार नीचे से सीमित है: लक्ष्य उपयोग किए गए बिन की संख्या को अधिकतम करना है ताकि प्रत्येक बिन में कुल आकार कम से कम एक दी गई सीमा हो।

'उचित अविभाज्य कार्य आवंटन' समस्या ('निष्पक्ष वस्तु आवंटन' का एक प्रकार) में, वस्तु कार्यों का प्रतिनिधित्व करते हैं, और अलग-अलग लोग होते हैं जिनमें से प्रत्येक प्रत्येक कार्य के लिए एक अलग कठिनाई-मूल्य का श्रेय देता है। लक्ष्य प्रत्येक व्यक्ति को उसके कुल कठिनाई-मूल्य की ऊपरी सीमा के साथ कार्यों का एक समुच्चय आवंटित करना है (इस प्रकार, प्रत्येक व्यक्ति एक बिन से मेल खाता है)। इस समस्या में भी बिन पैकिंग से लेकर कई तकनीकों का उपयोग किया जाता है। गिलोटिन काटना की समस्या में, वस्तुएं और बिन दोनों एक-आयामी संख्याओं के बजाय दो-आयामी आयताकार होते हैं, और वस्तुओं को एंड-टू-एंड कट्स का उपयोग करके बिन से काटा जाना होता है।

स्वार्थी बिन पैकिंग समस्या में, प्रत्येक वस्तु एक खिलाड़ी है जो इसकी लागत को कम करना चाहता है। बिन पैकिंग का एक प्रकार भी है जिसमें जिस लागत को कम किया जाना चाहिए वह बिन की संख्या नहीं है, बल्कि प्रत्येक बिन में वस्तुओं की संख्या का एक निश्चित अवतल कार्य है।

अन्य प्रकार द्वि-आयामी बिन पैकिंग हैं, त्रि-आयामी बिन पैकिंग, डिलिवरी के साथ बिन पैकिंग,

संसाधन

• BPPLIB - सर्वेक्षण, कोड, बेंचमार्क, जनरेटर, सॉल्वर और ग्रंथ सूची की एक लाइब्रेरी।

कार्यान्वयन

• ऑनलाइन: 1डी और 2D बिन पैकिंग के लिए अनुमानों का दृश्य
• पायथन: prtpy पैकेज में विभिन्न संख्या-विभाजन, बिन-पैकिंग और बिन-कवरिंग एल्गोरिदम के लिए कोड शामिल हैं। बिनपैकिंग पैकेज में दो विशिष्ट बिन पैकिंग समस्याओं को हल करने के लिए लालची एल्गोरिदम शामिल हैं।
• सी++: बिन-पैकिंग पैकेज में विभिन्न लालची एल्गोरिदम के साथ-साथ परीक्षण डेटा भी शामिल है। OR-tools package में C++ में बिन पैकिंग एल्गोरिदम, Python, C# और Java में रैपर्स शामिल हैं।
• सी: परिणामों और छवियों के साथ सी में 7 क्लासिक अनुमानित बिन पैकिंग एल्गोरिदम का कार्यान्वयन
• PHP: PHP क्लास किसी दिए गए आकार सीमा से अधिक के बिना फ़ाइलों को पैक करने के लिए
• हास्केल: एफएफडी और एमएफएफडी सहित कई बिन पैकिंग अनुमानों का कार्यान्वयन।
• सी: एफपार्ट: फाइलों को पैक करने के लिए ओपन-सोर्स कमांड-लाइन टूल (सी, बीएसडी-लाइसेंस प्राप्त)
• सी#: बिन पैकिंग और कटिंग स्टॉक सॉल्वर
• जावा: कैपर्फ - कटिंग और पैकिंग एल्गोरिदम रिसर्च फ्रेमवर्क, जिसमें कई बिन पैकिंग एल्गोरिदम और परीक्षण डेटा शामिल हैं।