High-multiplicity bin packing
उच्च-बहुलता बिन पैकिंग बिन पैकिंग समस्या का एक विशेष मामला है, जिसमें विभिन्न वस्तु-आकारों की संख्या कम होती है, जबकि प्रत्येक आकार वाली वस्तुओं की संख्या बड़ी होती है। जबकि सामान्य बिन-पैकिंग समस्या एन. पी.-हार्ड है, उच्च-गुणन सेटिंग को बहुपद समय में हल किया जा सकता है, यह मानते हुए कि विभिन्न आकारों की संख्या एक निश्चित स्थिरांक है। समस्या परिभाषा समस्या के लिए निवेश सकारात्मक पूर्णांक हैंः डी-विभिन्न आकारों की संख्या (जिसे समस्या का आयाम भी कहा जाता है); बी-बिन क्षमता। s1,., sd-आकार। आकारों के सदिश को एस. एन. 1,., एन. डी. द्वारा दर्शाया जाता है-गुणन; एन. आई. आकार एस. आई. के साथ वस्तुओं की संख्या है। गुणन के सदिश को n द्वारा दर्शाया जाता है. n वस्तुओं की कुल संख्या को दर्शाता है, अर्थात, n = n1 +. + nd। V समस्या के विवरण में दिखाई देने वाले सबसे बड़े पूर्णांक को दर्शाता है, अर्थात, V = अधिकतम (s1,., sd, n1,., nd, B) आउटपुट एक पैकिंग है-डिब्बे में वस्तुओं का एक असाइनमेंट, जैसे कि प्रत्येक बिन में वस्तुओं का कुल आकार अधिकतम B हो, और इसके अधीन, डिब्बे की संख्या यथासंभव कम हो। उदाहरण-मान लीजिए कि d = 2, s1 = 30, s2 = 40, n1 = n2 = 5, B = 120। तो आकार के साथ n = 10 आइटम हैंः 30,30,30,30,30,40,40,40,40,40। फिर, एक संभावित पैकिंग हैः {30,30,30,30}, {40,40,40}, {30,40,40}, जो 3 डिब्बे का उपयोग करता है। विन्यास एक विन्यास वस्तुओं का एक समूह है जो एक एकल बिन में फिट हो सकता है। इसे डी पूर्णांक के वेक्टर द्वारा दर्शाया जा सकता है, जो विन्यास में विभिन्न आकारों के गुणन को दर्शाता है। औपचारिक रूप से, प्रत्येक विन्यास सी के लिए हम एक पूर्णांक सदिश एसी = एसी, 1,., एसी, डी को इस तरह परिभाषित करते हैं कि एसी ≤ एन और एसी·एस ≤ बी। उपरोक्त उदाहरण में, विन्यासों में से एक c = {30,40,40} है, क्योंकि 1 * 30+2 * 40 ≤ 120 है। एकर संबंधित सदिश एसी = (1,2) छैक। अन्य विन्यास सदिश (4,0), (3,0), (2,0), (2,1), (1,0), (1,1), (1,2), (0,1), (0,2), (0,3) हैं। अगर हमारे पास आकार 3 की केवल तीन वस्तुएँ होतीं, तो हम (4,0) विन्यास का उपयोग नहीं कर सकते थे। विन्यास रैखिक कार्यक्रम का उपयोग करके समस्या को प्रस्तुत करना संभव हैः प्रत्येक विन्यास सी के लिए, एक चर एक्ससी होता है, जो डिब्बे की संख्या को दर्शाता है जिसमें सी का उपयोग किया जाता है। उपयोग किए गए डिब्बों की कुल संख्या केवल सभी विन्यासों पर xc का योग है, जिसे 1·x द्वारा दर्शाया जाता है। प्रत्येक आकार से उपयोग की जाने वाली वस्तुओं की कुल संख्या सभी विन्यासों पर वैक्टरों का योग है c. फिर, समस्या 1·x को इस तरह से कम करना है कि सभी विन्यासों पर c·xc का योग कम से कम n हो, ताकि सभी वस्तुओं को पैक किया जा सके। एल्गोरिदम बुनियादी एल्गोरिदम मान लीजिए कि पहले सभी आइटम बड़े हैं, यानी प्रत्येक एस. आई. कुछ अंश ई> 0 के लिए कम से कम ई. बी. है। फिर, प्रत्येक बिन में वस्तुओं की कुल संख्या अधिक से अधिक 1/e है, इसलिए विन्यास की कुल संख्या अधिक से अधिक d1/e है। प्रत्येक विन्यास अधिकतम एन समय पर दिखाई देता है। इसलिए, जाँचने के लिए अधिकांश संयोजन हैं। प्रत्येक संयोजन के लिए, हमें डी बाधाओं (प्रत्येक आकार के लिए एक) की जांच करनी होगी, इसलिए रन-टाइम है, जो एन में बहुपद है जब डी, ई स्थिर हैं। इस एल्गोरिथ्म के साथ मुख्य समस्या (इस तथ्य के अलावा कि यह केवल तभी काम करता है जब आइटम बड़े होते हैं) यह है कि इसका रनटाइम एन में बहुपद है, लेकिन इनपुट की लंबाई (द्विआधारी प्रतिनिधित्व में) लॉग (वी) में रैखिक है, जो लॉग (एन) के परिमाण के क्रम की है। इनपुट आकार फिलिप्पी और एग्नेटिस में रन-टाइम बहुपद ने एक एल्गोरिथ्म प्रस्तुत किया जो समय ओ (पॉली (लॉग वी)) में अधिकतम ओ. पी. टी. + डी-2 डिब्बे के साथ एक समाधान ढूंढता है। विशेष रूप से, डी = 2 अलग-अलग आकारों के लिए, उनका एल्गोरिथ्म समय ओ (लॉग वी) में एक इष्टतम समाधान पाता है। गोमेन्स और रोथवोस ने किसी भी निश्चित डी के लिए एक एल्गोरिथ्म प्रस्तुत किया, जो सभी संख्याओं को द्विआधारी एन्कोडिंग में दिए जाने पर इष्टतम समाधान पाता है। उनका एल्गोरिथ्म निम्नलिखित समस्या का समाधान करता हैः दो डी-आयामी पॉलीटोप पी और क्यू दिए जाने पर, पी में पूर्णांक बिंदुओं की न्यूनतम संख्या ज्ञात करें जिनका योग क्यू में है। उनका एल्गोरिदम समय पर चलता है। उनके एल्गोरिदम को अन्य समस्याओं के लिए अनुकूलित किया जा सकता है, जैसे कि समान-मशीन समय-निर्धारण और विभिन्न बाधाओं के साथ असंबंधित-मशीन समय-निर्धारण। सामान्य बिन-पैकिंग समस्या के लिए कई सन्निकटन एल्गोरिदम निम्नलिखित योजना का उपयोग करते हैंः वस्तुओं को "छोटा" (ई. बी. से छोटा, कुछ अंश ई. इन. (0,1) के लिए) और "बड़ा" (कम से कम ई. बी.) में अलग करें। पहले बड़ी वस्तुओं को संभालेंः वस्तु के आकार को किसी न किसी तरह गोल करें, ताकि विभिन्न आकारों की संख्या अधिक से अधिक कुछ स्थिर रहे। छोटी वस्तुओं को लालच में आवंटित करें, उदाहरण के लिए। अगले-फिट बिन पैकिंग के साथ। अगर कोई नया डिब्बे नहीं बनाए जाते हैं, तो हमारा काम पूरा हो जाता है। यदि नए डिब्बे बनाए जाते हैं, तो इसका मतलब है कि सभी डिब्बे (शायद अंतिम को छोड़कर) कम से कम (1-ई) बी तक भरे हुए हैं। इसलिए, डिब्बों की संख्या अधिकतम ओ. पी. टी./(1-ई) + 1 ≤ (1 + 2ई) ओ. पी. टी. + 1 है। एल्गोरिदम इस बात में भिन्न होते हैं कि वे उदाहरण को कैसे गोल करते हैं। रैखिक राउंडिंग ल्यूकर और डी-ला-वेगा ने अनुकूली इनपुट राउंडिंग के विचार का आविष्कार किया। वस्तुओं को उनके आकार के अनुसार ऑर्डर करें, और उन्हें कार्डिनलिटी एनई2 के 1/ई2 समूहों में वर्गीकृत करें। प्रत्येक समूह में, आकारों को समूह में अधिकतम आकार तक ऊपर की ओर गोल करें। अब, केवल d = 1/e2 विभिन्न आकार हैं। गोल उदाहरण का समाधान मूल उदाहरण के लिए भी संभव है, लेकिन डिब्बे की संख्या आवश्यकता से अधिक हो सकती है। नुकसान की मात्रा निर्धारित करने के लिए, पिछले समूह में अधिकतम आकार तक के उदाहरण पर विचार करें (पहला समूह 0 तक गोल किया गया है)। गोल-डाउन उदाहरण डी लगभग गोल-अप उदाहरण यू के बराबर है, सिवाय इसके कि डी में कुछ एनई2 शून्य हैं जबकि यू में इसके बजाय कुछ एनई2 बड़ी वस्तुएं हैं; लेकिन उनका आकार अधिकतम बी है। इसलिए, यू को डी की तुलना में अधिक से अधिक एनई2 अधिक डिब्बे की आवश्यकता होती है। चूंकि डी को इष्टतम की तुलना में कम डिब्बे की आवश्यकता होती है, इसलिए हमें वह डिब्बे (यू) ≤ ओपीटी + एनई2 मिलता है, यानी, हमारे पास एक योगात्मक त्रुटि है जिसे ई चुनकर जितना चाहें उतना छोटा किया जा सकता है। यदि सभी वस्तुएं बड़ी हैं (कम से कम ईबी आकार की), तो ओपीटी में प्रत्येक बिन में अधिक से अधिक 1/ई वस्तुएं (कम से कम ईबी आकार की) होती हैं, इसलिए ओपीटी कम से कम एन होनी चाहिए। इसलिए, डिब्बे (यू) ≤ (1 + ई) ओपीटी। छोटी वस्तुओं को संभालने के बाद, हम अधिक से अधिक प्राप्त करते हैं। ज्यामितीय गोलाकार करमरकर और कार्प एक अधिक कुशल गोलाकार विधि प्रस्तुत करते हैं जिसे वे ज्यामितीय गोलाकार कहते हैं (डी-ला-वेगा और ल्यूकर के रैखिक गोलाकार के विपरीत)। इन नवाचारों के आधार पर, वे और में रन-टाइम बहुपद के साथ एक एल्गोरिथ्म प्रस्तुत करते हैं। उनका एल्गोरिथ्म अधिक से अधिक आकार के साथ एक समाधान ढूंढता है। सुधार इस तकनीक में बाद में कई लेखकों द्वारा सुधार किया गयाः रोथवोस ने एक एल्गोरिथ्म प्रस्तुत किया जो अधिकतम आकार के साथ एक समाधान उत्पन्न करता है। होबर्ग और रोथवोस ने अधिक से अधिक आकार के साथ एक समाधान उत्पन्न करने के लिए इस एल्गोरिथ्म में सुधार किया। एल्गोरिथ्म यादृच्छिक है, और इसका चलने का समय वस्तुओं की कुल संख्या में बहुपद है। कटिंग स्टॉक समस्या भी देखें-उच्च-बहुलता बिन-पैकिंग के समान, लेकिन लक्ष्य डिब्बे की संख्या के बजाय प्रत्येक बिन में बर्बाद जगह की कुल मात्रा को कम करना है। इसके अलावा, कुछ रूपों में, प्रत्येक आकार से वस्तुओं की संख्या निश्चित नहीं होती है, लेकिन कुछ दी गई निचली और ऊपरी सीमाओं के बीच स्थानांतरित हो सकती है। संदर्भ बिन पैकिंग