Wyniki wyszukiwania - BazTech

1

An Experimental Study on Symmetry Breaking Constraints Impact for the One Dimensional Bin-Packing Problem

Hadj Salem Khadija, Kieffer Yann

Annals of Computer Science and Information Systems

|

2020

|

Vol. 21

317--326

EN

We consider the classical One-Dimensional Bin Packing Problem (1D-BPP), an NP-hard optimization problem, where, a set of weighted items has to be packed into one or more identical capacitated bins. We give an experimental study on using symmetry breaking constraints for strengthening the classical integer linear programming proposed to optimally solve this problem. Our computational experiments are conducted on the data-set found in BPPLib and the results have confirmed the theoretical results.

2

An algorithm for 1-space bounded cube packing

Zielonka Łukasz

Annals of Computer Science and Information Systems

|

2019

|

Vol. 18

171--175

EN

In this paper, we present a 1-space bounded cube packing algorithm with asymptotic competitive ratio 10.872.

3

Bin packing with restricted item fragmentation

Pieńkosz K.

Control and Cybernetics

|

2014

|

Vol. 43, no. 4

547--556

EN

In this paper we consider a generalization of the bin packing problem, in which it is permitted to fragment the items while packing them into bins. There is, however, a restriction that the size of each piece of the fragmented item cannot be smaller than a given parameter β An interesting aspect of such a model is that if β= 0, then the problem can be easily solved optimally. If β is large enough, meaning, in fact, that the fragmentation is not allowed, we get the classical bin packing problem, which is NP-hard in the strong sense. We present approximation algorithms for solving the problem and analyse their properties. The results of computational experiments and conclusions relating to the effectiveness of the algorithms are also presented.

4

Sposób szeregowania zadań dla jednej maszyny o ograniczonych zasobach

Cechowicz R.

Pomiary Automatyka Kontrola

|

2011

|

R. 57, nr 9

1093-1096

PL

W artykule opisano system szeregowania zadań niepodzielnych na jednej maszynie. System pozwala zoptymalizować plan produkcji poprzez ograniczenie ilości operacji transportowych i pomocniczych oraz poprzez poszukiwanie takiej kolejności realizacji zadań, dla której łączny czas wykonania będzie możliwie najmniejszy. Zastosowano zmodyfikowany algorytm genetyczny pozwalający na częściowe dostrojenie procesu do struktury danych. Testy przeprowadzone zarówno na danych dostępnych publicznie, jak i na danych pochodzących ze środowiska wytwórczego udowodniły skuteczność przyjętych rozwiązań.

EN

A system for scheduling indivisible tasks on a single, periodically accessible machine is presented in this paper. Because of the constrains existing in the environment, the scheduling problem presented here is similar to the one-dimensional bin-packing. The tasks, stacked on a palettes (Fig.1), were transported to the machine. The palette caould be replaced by another one only after completing all the tasks assigned to it. Each task was defined by an execution time Tz and an auxiliary time Tp. The transportation time To was added to the last task from each palette and to the last task executed within the machine availability period Tm (Fig.2). A modified genetic algorithm was used for the scheduling, where the parameter K defined the number of gene changeovers (representing changing the sequence of palettes and changing the sequence of tasks within a palette) during one mutation. The results obtained for the data available in public [13] and in selected publications are presented in Tab.1. It was noted that the distribution of scheduling results (fitness=Cmax) could be modified by changing the parameter K (Figs.4 and 6). The observation was proved statistically for the data from the manufacturing system by means of the median test run for the set of 500 results, 50 for each K=1..10 (χ2=19, df=9, p=0,0254<0,05). The results of the test proved that the scheduling algorithm could be tuned for speed by adjusting the value of K. Assuming that the process was random, it could be calculated that for K=5 the expected time of getting the solution Cmax<2050, expressed in the number of generations, was the shortest (assumed confidence level 0.99). The scheduling system allowed the definition of individual machine availability periods and taking into account the restrictions of the transport system (the allowed sequences of palette retrieval).

5

Analiza algorytmu sekwencyjnego dla zadania pakowania

Horzelski W.

Metody Informatyki Stosowanej

|

2009

|

nr 1 (18)

29-39

EN

The bin-packing problem in the classical approach is to arrange the list of tasks L={a1,a2,...an} of a size not exceeding 1 in the minimum number of bins of size 1, however, that none of the bins was overloaded. In dual version we need to maximized number of bins, assuming that all of them must be fully loaded (1 or more). Among the ways to do such a task is a class of sequential algorithms. From sequential algorithm is required in addition to pack the tasks in such a way that tasks placed in each container (bin) consisted of a sequence: [wzór]. In this paper is an example of sequential algorithm called S1k and carried out a full analysis of its behavior. It demonstrate the value of lower bound for efficiency factor of the algorithm [wzór] and a bound of asymptotic waste ratio of ...[wzór]. Paper presents result of the algorithm with list of tasks uniformly distributed on the (0.1]. Shows that its computational complexity is O(n) and carried out a comparison with the results achieved by the algorithm DNF.

6

Maximizing the number of unused bins

Demange M., Monnot J., Paschos V. T.

Foundations of Computing and Decision Sciences

|

2001

|

Vol. 26, No. 2

169-186

EN

We analyze the approximation behavior of some of the best-known polynomial-time approximation algorithms for bin-packing under an approximation criterion, called differential ratio, informally the ratio (n — where n is the size of the input list, is the size of the solution provided by an approximation algorithm and Beta(I) is the size of the optimal one. This measure has originally been introduced by Ausiello, D'Atri and Protasi and more recently revisited, in a more systematic way, by the first and the third authors of the present paper. Under the differential ratio, bin-packing has a natural formulation as the problem of maximizing the number of unused bins. We first show that two basic fit bin-packing algorithms, the first-fit and the best-fit, admit differential approximation ratios 1/2. Next, we show that slightly improved versions of them achieve ratios 2/3. Refining our analysis we show that the famous first-fit-decreasing and best-fit decreasing algorithms achieve differential approximation ratio 3/4: Finally, we show that first-fit-decreasing achieves asymptotic differential approximation ratio 7/9.