Қорапқа орналастыру мәселесі

Кіріспе

Математикалық және есептеулік мәселе.

Қоқыс жәшігін толтыру мәселесі – әртүрлі өлшемдегі заттарды шектеулі сандағы қоқыс жәшіктеріне немесе контейнерлерге, әрқайсысы белгілі сыйымдылыққа ие, қолданылатын қоқыс жәшіктерінің санын ең азайту мақсатымен орналастыру мәселесі. Бұл мәселенің көптеген қолданыс аймақтары бар, мысалы, контейнерлерді толтыру, салмақ сыйымдылығы шектеулі жүк көліктеріне жүк тиеу, медиа файлдарын резервтік көшірмелеу және FPGA жартылай өткізгіш чиптерін жобалаудағы технологиялық картаны жасау. Есептеу тұрғысынан, бұл мәселе NP-қиын, ал сәйкес шешімді табу мәселесі – заттарды белгіленген сандағы контейнерлерге сыйыстыруға бола ма, жоқ па, дегенді анықтау – NP-толық. Ең жаман жағдайдағы қиындығына қарамастан, мәселенің өте үлкен мысалдары үшін күрделі алгоритмдерді қолдану арқылы оңтайлы шешімдерді табуға болады. Сонымен қатар, көптеген жуықтау алгоритмдері бар. Мысалы, бірінші сәйкестік алгоритмі әр затты оған сыятын алғашқы қоқыс жәшігіне орналастыруды қамтитын жылдам, бірақ көбінесе оңтайлы емес шешімді ұсынады. Ол Θ(n log n) уақытты қажет етеді, мұнда n – буып-түюге жататын заттар саны. Алгоритмді заттар тізімін алдымен төмендеу ретімен сұрыптау арқылы әлдеқайда тиімді етуге болады (кейде бірінші сәйкестік төмендеу алгоритмі деп аталады), бірақ бұл әлі де оңтайлы шешімге кепілдік бермейді және ұзақ тізімдер үшін алгоритмнің жұмыс уақытын ұзартуы мүмкін. Дегенмен, заттардың кемінде бір рет дұрыс реттелген орналасуы бірінші сәйкестік алгоритмімен оңтайлы шешім табуға мүмкіндік беретіні белгілі. Бұл мәселенің көптеген түрлері бар, мысалы, 2D-қаптама, сызықтық қаптама, салмақ бойынша қаптама, құны бойынша қаптама және т.б. Қоқыс жәшігін толтыру мәселесін кесу қоры мәселесінің ерекше жағдайы ретінде қарастыруға болады. Егер қоқыс жәшіктерінің саны 1-ге шектелген болса және әр зат көлемімен де, құнымен де сипатталса, қоқыс жәшігіне сыятын заттардың құнын барынша арттыру мәселесі рюкзак мәселесі деп аталады. Практикада жиі кездесетін қаптаманың бір түрі – заттарды қоқыс жәшігіне орналастырғанда олар орынды бөлісе алады. Атап айтқанда, бірнеше затты бірге жинағанда олардың жеке өлшемдерінің қосындысынан кем орынды алады. Бұл нұсқа VM-қаптамасы деп аталады, себебі виртуалды машиналарды (VM) серверде қаптағанда, олардың жалпы жад талаптары VM-дармен бөлісетін беттерге байланысты азаюы мүмкін, оларды тек бір рет сақтау жеткілікті. Егер заттар кеңістікті кез келген тәсілмен бөлісе алса, қоқыс жәшігін толтыру мәселесін тіпті жуықтау да қиын. Алайда, егер кеңістікті бөлісу иерархиялық болса, яғни виртуалды машиналарда жадты бөлісу сияқты, қоқыс жәшігін толтыру мәселесін тиімді жуықтауға болады. Практикалық тұрғыдан қызығушылық тудыратын қоқыс жәшігін толтырудың тағы бір түрі – онлайн қоқыс жәшігін толтыру. Бұл жерде әртүрлі көлемдегі заттар тізбектей келіп түседі деп күтіледі, ал шешім қабылдаушы ағымдағы затты таңдап, қаптамаға салуға, немесе оны жіберіп жіберуге шешім қабылдауы керек. Әр шешім қайта қарастырылмайды. Керісінше, офлайн қоқыс жәшігін толтыру қосымша заттар келгеннен кейін жақсырақ қаптама алу үшін заттарды қайта орналастыруға мүмкіндік береді. Бұл, әрине, қайта орналастырылатын заттарды сақтауға арналған қосымша жадты қажет етеді.

The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in media, and technology mapping in FPGA semiconductor chip design. Computationally, the problem is NP hard, and the corresponding decision problem, deciding if items can fit into a specified number of bins, is NP complete. Despite its worst case hardness, optimal solutions to very large instances of the problem can be produced with sophisticated algorithms. In addition, many approximation algorithms exist. For example, the first fit algorithm provides a fast but often non optimal solution, involving placing each item into the first bin in which it will fit. It requires Θ(n log n) time, where n is the number of items to be packed. The algorithm can be made much more effective by first sorting the list of items into decreasing order (sometimes known as the first fit decreasing algorithm), although this still does not guarantee an optimal solution and for longer lists may increase the running time of the algorithm. It is known, however, that there always exists at least one ordering of items that allows first fit to produce an optimal solution. There are many variations of this problem, such as 2D packing, linear packing, packing by weight, packing by cost, and so on. The bin packing problem can also be seen as a special case of the cutting stock problem. When the number of bins is restricted to 1 and each item is characterized by both a volume and a value, the problem of maximizing the value of items that can fit in the bin is known as the knapsack problem. A variant of bin packing that occurs in practice is when items can share space when packed into a bin. Specifically, a set of items could occupy less space when packed together than the sum of their individual sizes. This variant is known as VM packing since when virtual machines (VMs) are packed in a server, their total memory requirement could decrease due to pages shared by the VMs that need only be stored once. If items can share space in arbitrary ways, the bin packing problem is hard to even approximate. However, if space sharing fits into a hierarchy, as is the case with memory sharing in virtual machines, the bin packing problem can be efficiently approximated. Another variant of bin packing of interest in practice is the so called online bin packing. Here the items of different volume are supposed to arrive sequentially, and the decision maker has to decide whether to select and pack the currently observed item, or else to let it pass. Each decision is without recall. In contrast, offline bin packing allows rearranging the items in the hope of achieving a better packing once additional items arrive. This of course requires additional storage for holding the items to be rearranged.

Қорапты толтырудың қаттылығы

Қоқыс жәшігін толтыру мәселесі күшті NP-толық. Бұл күшті NP-толық 3-бөлу мәселесін қоқыс жәшігін толтыруға келтіру арқылы дәлелдеуге болады. Барлық кіріс сандарының қосындысы S болғанда, 3-бөлу мәселесінің бір мысалын қарастырып, қораптың көлемі T болатын қоқыс жәшігін толтыру мәселесінің мысалын құрастырамыз. Егер кіріс сандарының тең бөлінісі болса, онда ең жақсы толтыру үшін 2 қорап қажет; демек, жақындастыру қатынасы 2-ден кіші болған кез келген алгоритм 3-тен кем қорапты қайтаруы керек, яғни 2 қорапты қайтаруы керек. Керісінше, егер кіріс сандары тең бөлінбесе, онда ең жақсы толтыру үшін кем дегенде 3 қорап қажет болады. Екінші жағынан, қоқыс жәшігін толтыру, кез келген белгілі бір K қорап саны үшін псевдополиномиалдық уақытта, ал кез келген белгілі бір B қорап сыйымдылығы үшін полиномиалдық уақытта шешіледі.

Қосылмалы шамалау

Кармаркар Карп қора жинау алгоритмі ең көп дегенде өлшемі бар шешімді табады және n-ге қатысты полиномдық уақытта жұмыс істейді (полиномның дәрежесі жоғары, кем дегенде 8). Ротвос ең көп дегенде контейнерлерді пайдаланатын шешім жасайтын алгоритм ұсынды. Хоберг пен Ротвос бұл алгоритмді жетілдіріп, ең көп дегенде контейнерлерді пайдаланатын шешім жасауға қол жеткізді. Алгоритм кездейсоқтандырылған, ал оның жұмыс істеу уақыты n-ге қатысты полиномдық.

Әр түрлі өлшемдер саны аз

Қоқыс жәшігін толтырудың ерекше жағдайы, егер әр түрлі өлшемдегі заттардың саны d болса туындайды. Әрбір өлшемде көптеген бірдей заттар болуы мүмкін. Бұл жағдай жоғары көптікпен қоқыс жәшігін толтыру деп аталады және ол жалпы мәселеге қарағанда тиімдірек алгоритмдерге ие.

Фрагментациямен қорапқа салу

Фрагментациямен қорапты толтыру немесе фрагменттеуге болатын объектілерді қорапқа толтыру – бұл қорапты толтыру мәселесінің бір түрі, онда заттарды бөліктерге бөлуге және әр бөлікті жеке-жеке қорапқа салуға рұқсат етіледі. Заттарды бөліктерге бөлу жалпы өнімділікті жақсартуға, мысалы, қолданылатын қораптардың жалпы санын азайтуға мүмкіндік береді. Сонымен қатар, ең оңтайлы кесте табу есептеу жағынан жеңілдеуі мүмкін, себебі кейбір оңтайландыру айнымалылары үздіксіз болады. Бірақ заттарды бөлуге жұмсалатын шығын да болуы мүмкін. Бұл мәселені алғаш рет Мандал, Чакрабари және Гоузе ұсынған.

Нұсқалар

Мәселе екі негізгі нұсқада қарастырылады. Бірінші нұсқа, өлшемін ұлғайтатын фрагментациямен қорапты толтыру (BP SIF) деп аталады, онда әрбір зат фрагменттерге бөлінуі мүмкін; әрбір фрагменттің өлшеміне қосымша бірліктер ескеріледі. Екінші нұсқа, өлшемін сақтайтын фрагментациямен қорапты толтыру (BP SPF) деп аталады, онда әрбір заттың көлемі мен құны болады; затты фрагменттеу оның құнын арттырады, бірақ көлемін өзгерте алмайды.

Есептеу күрделілігі

Мандал, Чакрабари және Гоузе BP SIF және BP SPF екеуі де күшті NP-қатты екенін көрсетті. Қаттылығына қарамастан, олар бірнеше алгоритмдер ұсынады және олардың өнімділігін зерттейді. Олардың алгоритмдері негіз ретінде буып жинаудың классикалық алгоритмдерін, мысалы, келесіге сәйкес келетін және біріншіге сәйкес келетін азайту алгоритмдерін пайдаланады. Бертацци, Голден және Ван BP SIF-тың бөлу ережесі бар түрін енгізді: заттың мөлшеріне сәйкес бір затты тек бір жолмен бөлуге рұқсат етіледі. Бұл, мысалы, көлік маршрутын жоспарлау мәселесі үшін пайдалы. Олар өз мақалаларында осы түрдің нашар жағдайдағы өнімділік шегін келтіреді. Шахнай, Тамир және Егезекили BP SIF және BP SPF үшін жуықтау схемаларын жасады: екілік PTAS (мәселенің екі түрі үшін PTAS), APTAS деп аталатын асимптотикалық PTAS және екі түр үшін AFPTAS деп аталатын екілік асимптотикалық FPTAS. Екичи BP SPF-тың кейбір заттары қақтығысқа түсетін түрін енгізді, онда қақтығысқан заттардың бөліктерін бірге бірге жинауға тыйым салынады. Олар осы түрдің де NP-қатты екенін дәлелдеді. Кассасса және Чезелли шығын мен қосымша шығынсыз, ал контейнерлер саны белгілі бір түрін енгізді. Дегенмен, бөлулер санын азайту қажет. Олар нақты және жуықталған шешімдер үшін математикалық бағдарламалау алгоритмдерін ұсынады.

Қатысушы мәселелер

Жазалармен бөлінетін рюкзак проблемасын Малагути, Моначи, Паронуцци және Пферши ұсынды. Олар бұл проблема үшін FPTAS және динамикалық бағдарлама әзірледі, сондай-ақ модельдерінің тиімділігін салыстыратын кең ауқымды есептеу зерттеуін жүргізді. Қосымша қараңыз: Бөлінетін жұмыс жоспарлау.

Бөлінуге болатын нысандар өлшемдерімен өнімділік

Қоқыс контейнерлерін толтырудың маңызды ерекше жағдайы – заттардың мөлшері бөлінетін тізбек құрайтын жағдай (немесе факторланған). Бөлінетін заттар мөлшерінің ерекше жағдайы компьютерлік жүйелерде жадты бөлу кезінде кездеседі, онда заттардың мөлшерінің бәрі 2-нің дәрежесі болып табылады. Егер заттардың мөлшері бөлінсе, қоқыс контейнерлерін толтыруға арналған кейбір эвристикалық алгоритмдер оңтайлы шешімді табады.

Қоймаларға қойылатын кәріздік шектеулер

Қораптарды толтырудың бір түрі бар, онда қораптарға кардиналдық шектеулер қойылады: әрбір қорапта ең көп дегенде k зат болуы мүмкін, мұнда k – белгілі бір тұрақты бүтін сан. Краузе, Шен және Шветман бұл мәселені оңтайлы тапсырмаларды жоспарлаудың бір түрі ретінде қарастырады: компьютерде k процессор бар. Бірлік уақытқа (1) орындалатын, бірақ әртүрлі жад көлемі қажет болатын n тапсырма бар. Әрбір уақыт бірлігі жеке қорап ретінде қарастырылады. Мақсат – мүмкіндігінше аз қорапты (= уақыт бірліктерін) пайдалану, сонымен бірге әрбір қорапта ең көп дегенде k тапсырма орындалуын қамтамасыз ету. Олар ең көп қорапты пайдаланатын бірнеше эвристикалық алгоритмдерді ұсынады. Келлер және Пферши орындалу уақыты бар, ең көп қорапты пайдаланатын алгоритмді ұсынады. Олардың алгоритмі OPT-ны екілік іздеу арқылы анықтайды. Әрбір ізделінетін m мәні үшін ол заттарды 3m/2 қорапқа орналастыруға тырысады.

Қатысушы мәселелер

Қоқыс жәшіктерін толтыру мәселесінде жәшіктердің мөлшері белгілі және олардың санын арттыруға болады (бірақ мүмкіндігінше азайту керек). Керісінше, көп жолды санды бөлу мәселесінде жәшіктердің саны белгілі, ал олардың мөлшерін арттыруға болады. Мақсат – жәшіктердің мөлшері мүмкіндігінше тең болатын бөлінуді табу (мультипроцессорлық кестелеу мәселесі немесе ең аз мерзімдік мәселе деп аталатын түрінде мақсат – ең үлкен жәшіктің мөлшерін азайту). Кері қоқыс жәшіктерін толтыру мәселесінде жәшіктердің саны мен мөлшері белгілі, бірақ заттардың мөлшерін өзгертуге болады. Мақсат – барлық заттарды белгіленген жәшіктерге орналастыру үшін заттардың мөлшер векторын ең аз өзгерту. Максималды ресурсты қоқыс жәшіктерін толтыру мәселесінде мақсат – пайдаланылған жәшіктердің санын барынша арттыру, яғни жәшіктердің белгілі бір реті бойынша кейінгі жәшіктегі ешбір зат бұрынғы жәшікке сыймауы керек. Двойной (қос) мәселеде жәшіктердің саны белгілі, ал мақсат – жәшіктерге салынған заттардың жалпы санын немесе жалпы мөлшерін азайту, сонда қалған заттар толтырылмаған жәшікке сыймайды. Қоқыс жәшігін жабу мәселесінде жәшік мөлшері төменнен шектелген: мақсат – әр жәшіктегі жалпы мөлшер кем дегенде белгілі бір шекті құрауы үшін пайдаланылған жәшіктердің санын барынша арттыру. Әділ бөлінбейтін шаруаларды бөлу мәселесінде (әділ бөлудің бір түрі) заттар шаруаларды білдіреді, ал әр шаруаның қиындығын әртүрлі бағалайтын әртүрлі адамдар бар. Мақсат – әр адамға шаруалар жиынтығын бөлу, олардың жалпы қиындық деңгейіне жоғары шек қойылады (осылайша, әр адам жәшікке сәйкес келеді). Бұл мәселеде қоқыс жәшіктерін толтырудан алынған көптеген техникалар қолданылады. Гильотинамен кесу мәселесінде заттар мен "жәшіктер" бір өлшемді сандар емес, екі өлшемді тіктөртбұрыштар болып табылады және заттар жәшіктен шетінен шетке кесу арқылы кесілуі керек. Өзімшіл қоқыс жәшіктерін толтыру мәселесінде әр зат өзінің бағасын азайтуға тырысатын ойыншы. Сондай-ақ, жәшіктерді толтырудың бір түрі бар, онда азайтылуға тиіс шығын жәшіктердің саны емес, әр жәшіктегі заттар санының белгілі бір қисық функциясы. үш өлшемді жәшіктерді толтыру, жеткізіліммен жәшіктерді толтыру.

In the bin packing problem, the size of the bins is fixed and their number can be enlarged (but should be as small as possible). In contrast, in the multiway number partitioning problem, the number of bins is fixed and their size can be enlarged. The objective is to find a partition in which the bin sizes are as nearly equal is possible (in the variant called multiprocessor scheduling problem or minimum makespan problem, the goal is specifically to minimize the size of the largest bin). In the inverse bin packing problem, both the number of bins and their sizes are fixed, but the item sizes can be changed. The objective is to achieve the minimum perturbation to the item size vector so that all the items can be packed into the prescribed number of bins. In the maximum resource bin packing problem, the goal is to maximize the number of bins used, such that, for some ordering of the bins, no item in a later bin fits in an earlier bin. In a dual problem, the number of bins is fixed, and the goal is to minimize the total number or the total size of items placed into the bins, such that no remaining item fits into an unfilled bin. In the bin covering problem, the bin size is bounded from below: the goal is to maximize the number of bins used such that the total size in each bin is at least a given threshold. In the fair indivisible chore allocation problem (a variant of fair item allocation), the items represent chores, and there are different people each of whom attributes a different difficulty value to each chore. The goal is to allocate to each person a set of chores with an upper bound on its total difficulty value (thus, each person corresponds to a bin). Many techniques from bin packing are used in this problem too. In the guillotine cutting problem, both the items and the "bins" are two dimensional rectangles rather than one dimensional numbers, and the items have to be cut from the bin using end to end cuts. In the selfish bin packing problem, each item is a player who wants to minimize its cost. There is also a variant of bin packing in which the cost that should be minimized is not the number of bins, but rather a certain concave function of the number of items in each bin. three dimensional bin packing, bin packing with delivery,

Ресурстар

BPPLIB – сараптамалар, кодтар, өлшемдер, генераторлар, шешушілер және библиография кітапханасы.