Конференции ИВТ СО РАН

Тезисы докладов

The generalization of a problem of cutting a rectangle into smaller equal rectangles: cutting a rectangular sheet $(A,B)$ into $x$ rectangles $(a,b)$ and $y$ rectangles $(c,d)$ is considered. Denote this problem as $((A,B),x(a,b),y(c,d))$. We shall designate the set of feasible solutions of this problem as

$$ frac {A, B} {a, b, c, d} = {(x, y)in Z^2_+ | parbox {31ex} {there exists cutting pattern for} ((A, B); x (a, b), y (c, d)) }. $$

The generalization of the theorem of cite{1} allows to decompose the set of feasible solutions of this problem.

egin{theorem} If vertices of a knapsack polygon are known for both sides of a rectangular sheet $(A,B)$ so that $$ P_A=igoplus_{i=1}^K T_i(x_i,y_i), P_B=igoplus_{j=1}^L T_j(u_j,v_j) $$ then the following formula for the convex hull of feasible solutions holds: egin{equation}label{eq:formco} cofrac {A, B} {a, b, c, d} = igoplus_{i=1}^Kigoplus_{j=1}^L T_{ij}(x_iu_j,y_iv_j), end{equation} where $T(x,y)$ denotes a right triangle with vertices $(0,0),(0,x),(y,0)$, $igoplus$ is the Minkowski sum of sets. end{theorem}

The quadratic time algorithm for constructing the convex hull of the set of feasible solutions is proposed. The received algorithm for constructing the convex hull $co( frac {A, B} {a, b, c, d}) $ allows to remove the restriction $ab=cd$ in Problem 1 from cite{2}, i.e. Problem 1 cite{2} in the general case also belongs to $mathcal{P}$. It is an open problem whether the decision problem $(m,n)in frac{A,B}{a,b,c,d}$ belongs to $mathcal{P}$.

egin{thebibliography}{5} ibitem[1]{1}{Arslanov M.Z.}, Continued fractions in optimal cutting a rectangular sheet into equal small rectangles, emph{European Journal of Operational Research} extbf{125} (2000), 239--248.

ibitem[2]{2}Girlich, E., Tarnowski, A.G., On polynomial solvability of two multiprocessor scheduling problems, emph{Mathematical Methods of Operations Research} extbf{50} (1999), 27--51.

ibitem[3]{3} Tarnowski, A.G., Advanced polynomial time algorithm for guillotine generalized pallet loading problem. In emph{ International Scientific Collection: Decision making under conditions of uncertainty (cutting-packing problems)}, Ufa State Aviation Technical University, 1997, 93--124. end{thebibliography}

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск