Volume 15, No 4, 2008, P. 57-73

UDC 519.8
I. A. Rykov
On comparison of the strip packing problem with a certain project scheduling problem

Abstract:
Comparison of some particular case of the resource-constrained project scheduling problem with the strip packing problem is performed. The upper bound for the optima relation of these problems is improved. An example with the optima 5 and 4 and the strip width 8 is constructed. It is shown that this example is minimal, i.e., there exist no example with optima 5 and 4 and with less width of the strip. 
Illustr. 11, bibl. 9. 

Keywords: combinatorial optimization, project scheduling, strip packing.

Rykov Ivan Aleksandrovich ¹
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: rykov@ledas.com