High-multiplicity bin packing
ઉચ્ચ-ગુણાકાર બિન પેકિંગ એ બિન પેકિંગ સમસ્યાનો એક વિશેષ કેસ છે, જેમાં વિવિધ વસ્તુ-કદની સંખ્યા ઓછી હોય છે, જ્યારે દરેક કદની વસ્તુઓની સંખ્યા મોટી હોય છે. જ્યારે સામાન્ય બિન-પેકિંગ સમસ્યા એન. પી.-હાર્ડ હોય છે, ત્યારે ઉચ્ચ-ગુણાકાર સેટિંગને બહુપદી સમયમાં ઉકેલી શકાય છે, એમ ધારીને કે વિવિધ કદની સંખ્યા એક નિશ્ચિત અચળાંક છે. સમસ્યાની વ્યાખ્યા સમસ્યાના ઇનપુટ્સ હકારાત્મક પૂર્ણાંકો છેઃ ડી-વિવિધ કદની સંખ્યા (જેને સમસ્યાનું પરિમાણ પણ કહેવાય છે); બી-બિન ક્ષમતા. s1,., sd-કદ. કદના વેક્ટરને s. n1,., nd-ગુણાકાર દ્વારા સૂચવવામાં આવે છે; ni એ કદની વસ્તુઓની સંખ્યા છે. ગુણાકારના વેક્ટરને 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 ડબ્બાનો ઉપયોગ કરે છે. રૂપરેખાંકન એ વસ્તુઓનો સમૂહ છે જે એક જ ડબ્બામાં ફિટ થઈ શકે છે. તેને ડી પૂર્ણાંકોના વેક્ટર દ્વારા રજૂ કરી શકાય છે, જે રૂપરેખાંકનમાં વિવિધ કદના ગુણાકારને સૂચવે છે. ઔપચારિક રીતે, દરેક રૂપરેખાંકન c માટે આપણે પૂર્ણાંક વેક્ટર ac = ac, 1,., ac, d ને એવી રીતે વ્યાખ્યાયિત કરીએ છીએ કે ac ≤ n અને ac·s ≤ B. ઉપરોક્ત ઉદાહરણમાં, એક રૂપરેખાંકન 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) રૂપરેખાંકનનો ઉપયોગ કરી શક્યા ન હોત. રૂપરેખાંકન રેખીય પ્રોગ્રામનો ઉપયોગ કરીને સમસ્યા રજૂ કરવી શક્ય છેઃ દરેક રૂપરેખાંકન c માટે, એક ચલ xc છે, જે ડબ્બાની સંખ્યા દર્શાવે છે જેમાં c નો ઉપયોગ થાય છે. ઉપયોગમાં લેવાતા ડબ્બાની કુલ સંખ્યા એ તમામ રૂપરેખાંકનો પર xc નો સરવાળો છે, જે 1·x દ્વારા સૂચવવામાં આવે છે. દરેક કદમાંથી ઉપયોગમાં લેવાતી વસ્તુઓની કુલ સંખ્યા એ તમામ રૂપરેખાંકનો પર વાહકનો સરવાળો છે c. પછી, સમસ્યા એ છે કે 1·x ને એવી રીતે ઘટાડવું કે જેથી તમામ રૂપરેખાંકનો c પર AC·xc નો સરવાળો ઓછામાં ઓછો n હોય, જેથી બધી વસ્તુઓ પેક કરવામાં આવે. અલ્ગોરિધમ્સ મૂળભૂત અલ્ગોરિધમ્સ ધારો કે પહેલા બધી વસ્તુઓ મોટી છે, એટલે કે, દરેક si અમુક અપૂર્ણાંક e> 0 માટે ઓછામાં ઓછું e·B છે. પછી, દરેક ડબ્બામાં વસ્તુઓની કુલ સંખ્યા મહત્તમ 1/e છે, તેથી રૂપરેખાંકનની કુલ સંખ્યા મહત્તમ d1/e છે. દરેક રૂપરેખાંકન મહત્તમ n સમયે દેખાય છે. તેથી, તપાસવા માટે મોટાભાગના સંયોજનો છે. દરેક સંયોજન માટે, આપણે d મર્યાદાઓ (દરેક કદ માટે એક) તપાસવી પડશે, તેથી રન-ટાઇમ છે, જે n માં બહુપદી છે જ્યારે d, e અચળ હોય છે. આ અલ્ગોરિધમ સાથે મુખ્ય સમસ્યા (એ હકીકત ઉપરાંત કે તે માત્ર ત્યારે જ કામ કરે છે જ્યારે વસ્તુઓ મોટી હોય) એ છે કે તેનો રનટાઇમ એનમાં બહુપદી છે, પરંતુ ઇનપુટની લંબાઈ (દ્વિસંગી રજૂઆતમાં) લોગ (વી) માં રેખીય છે, જે લોગ (એન) ની તીવ્રતાના ક્રમમાં છે. ઇનપુટ કદ ફિલીપી અને એગ્નેટિસમાં રન-ટાઇમ બહુપદીએ એક અલ્ગોરિધમ રજૂ કર્યું જે સમય O (પોલી (લોગ V)) માં મહત્તમ ઓ. પી. ટી. + ડી-2 ડબ્બાઓ સાથે ઉકેલ શોધે છે. ખાસ કરીને, d = 2 જુદા જુદા કદ માટે, તેમનું અલ્ગોરિધમ સમય O (લોગ V) માં શ્રેષ્ઠ ઉકેલ શોધે છે. ગોમેન્સ અને રોથવોસે કોઈપણ નિશ્ચિત ડી માટે એક અલ્ગોરિધમ રજૂ કર્યું, જે શ્રેષ્ઠ ઉકેલ શોધે છે જ્યારે તમામ સંખ્યાઓ દ્વિસંગી એન્કોડિંગમાં આપવામાં આવે છે. તેમનું અલ્ગોરિધમ નીચેની સમસ્યાનું સમાધાન કરે છેઃ બે ડી-ડાયમેન્શનલ પોલીટોપ પી અને ક્યૂ આપવામાં આવે તો, પીમાં ઓછામાં ઓછા પૂર્ણાંક બિંદુઓની સંખ્યા શોધો, જેનો સરવાળો ક્યૂમાં છે. તેમનું અલ્ગોરિધમ સમયસર ચાલે છે. તેમના અલ્ગોરિધમનો અન્ય સમસ્યાઓ માટે અનુકૂળ થઈ શકે છે, જેમ કે સમાન-મશીનોના સમયપત્રક અને વિવિધ અવરોધો સાથે અસંબંધિત-મશીનોના સમયપત્રક. સામાન્ય બિન-પેકિંગ સમસ્યા માટે કેટલાક અંદાજિત અલ્ગોરિધમ્સ નીચેની યોજનાનો ઉપયોગ કરે છેઃ વસ્તુઓને "નાના" (ઇ. બી. કરતા નાના, કેટલાક અપૂર્ણાંક ઇ. (0,1) માટે) અને "મોટા" (ઓછામાં ઓછા ઇ. બી.) માં અલગ કરો. મોટી વસ્તુઓને પહેલા સંભાળોઃ વસ્તુના કદને કોઈક રીતે ગોળાકાર કરો, જેથી વિવિધ કદની સંખ્યા વધુમાં વધુ સ્થિર રહે. લોભથી નાની વસ્તુઓની ફાળવણી કરો, દા. ત. આગામી-ફિટ બિન પેકિંગ સાથે. જો કોઈ નવા ડબ્બા ન બનાવવામાં આવે, તો આપણે પૂર્ણ કરી લઈએ છીએ. જો નવા ડબ્બા બનાવવામાં આવે, તો તેનો અર્થ એ છે કે તમામ ડબ્બા (કદાચ છેલ્લા એક સિવાય) ઓછામાં ઓછા (1-ઇ) બી સુધી ભરેલા છે. તેથી, ડબ્બાની સંખ્યા મહત્તમ ઓ. પી. ટી./(1-ઇ) + 1 ≤ (1 + 2ઇ) ઓ. પી. ટી. + 1 છે. એલ્ગોરિધમ્સ તેઓ ઉદાહરણને કેવી રીતે ગોળાકાર કરે છે તેમાં અલગ પડે છે. રેખીય ગોળાકાર લ્યુએકર અને ડી-લા-વેગાએ અનુકૂલનશીલ ઇનપુટ ગોળાકારના વિચારની શોધ કરી. વસ્તુઓને તેમના કદ અનુસાર ઓર્ડર કરો અને તેમને કાર્ડિનાલિટી એનઇ 2 ના 1/ઇ 2 જૂથોમાં જૂથબદ્ધ કરો. દરેક જૂથમાં, કદને જૂથમાં મહત્તમ કદ સુધી ગોળાકાર કરો. હવે, ત્યાં માત્ર d = 1/e2 વિવિધ કદ છે. ગોળાકાર ઉદાહરણનો ઉકેલ મૂળ ઉદાહરણ માટે પણ શક્ય છે, પરંતુ ડબ્બાની સંખ્યા જરૂરી કરતાં મોટી હોઈ શકે છે. નુકસાનને માપવા માટે, અગાઉના જૂથમાં મહત્તમ કદ સુધી ગોળાકાર ઉદાહરણને ધ્યાનમાં લો (પ્રથમ જૂથ 0 સુધી ગોળાકાર છે). ગોળાકાર ઉદાહરણ D એ લગભગ ગોળાકાર ઉદાહરણ U ની બરાબર છે, સિવાય કે D માં કેટલાક ne2 શૂન્ય હોય છે જ્યારે U માં તેના બદલે કેટલીક ne2 મોટી વસ્તુઓ હોય છે; પરંતુ તેમનું કદ મહત્તમ B હોય છે. તેથી, યુ ને ડી કરતા વધુ ની2 ડબ્બાઓની જરૂર છે. ડી ને મહત્તમ કરતાં ઓછા ડબ્બાઓની જરૂર હોવાથી, આપણને તે ડબ્બા (યુ) ≤ ઓ. પી. ટી. + ની2 મળે છે, એટલે કે, આપણી પાસે એક એડિટિવ ભૂલ છે જે ઇ પસંદ કરીને આપણને ગમે તેટલી નાની બનાવી શકાય છે. જો બધી વસ્તુઓ મોટી હોય (ઓછામાં ઓછી ઇ. બી. કદની), તો ઓ. પી. ટી. માં દરેક ડબ્બા મહત્તમ 1/ઇ. વસ્તુઓ (ઓછામાં ઓછી ઇ. બી. કદની) ધરાવે છે, તેથી ઓ. પી. ટી. ઓછામાં ઓછી એન. હોવી જોઈએ. તેથી, ડબ્બા (યુ) ≤ (1 + ઇ) ઓ. પી. ટી. નાની વસ્તુઓને સંભાળ્યા પછી, આપણે મોટાભાગે મેળવીએ છીએ. ભૌમિતિક ગોળાકાર કર્મકાર અને કાર્પ વધુ કાર્યક્ષમ ગોળાકાર પદ્ધતિ રજૂ કરે છે જેને તેઓ ભૌમિતિક ગોળાકાર કહે છે (ડી-લા-વેગા અને લ્યુકેરના રેખીય ગોળાકારથી વિપરીત). આ નવીનતાઓના આધારે, તેઓ અને માં રન-ટાઇમ બહુપદી સાથે એક અલ્ગોરિધમ રજૂ કરે છે. તેમનું અલ્ગોરિધમ મહત્તમ કદ સાથે ઉકેલ શોધે છે. સુધારાઓ આ તકનીકમાં પાછળથી કેટલાક લેખકો દ્વારા સુધારો કરવામાં આવ્યો હતોઃ રોથવોસે એક અલ્ગોરિધમ રજૂ કર્યું હતું જે મહત્તમ કદ સાથે ઉકેલ ઉત્પન્ન કરે છે. હોબર્ગ અને રોથવોસે મહત્તમ કદ સાથે ઉકેલ પેદા કરવા માટે આ અલ્ગોરિધમમાં સુધારો કર્યો. અલ્ગોરિધમ રેન્ડમાઇઝ્ડ છે, અને તેનો ચાલી રહેલો સમય વસ્તુઓની કુલ સંખ્યામાં બહુપદી છે. કટિંગ સ્ટોક સમસ્યા પણ જુઓ-ઉચ્ચ-ગુણાકાર બિન-પેકિંગ જેવી જ, પરંતુ ધ્યેય ડબ્બાઓની સંખ્યાને બદલે દરેક ડબ્બાઓમાં બગાડેલી જગ્યાની કુલ માત્રાને ઘટાડવાનો છે. વધુમાં, કેટલાક પ્રકારોમાં, દરેક કદની વસ્તુઓની સંખ્યા નિશ્ચિત નથી, પરંતુ કેટલીક આપેલ નીચલી અને ઉપરની સીમાઓ વચ્ચે ખસેડી શકાય છે. સંદર્ભો બિન પેકિંગ