We present a range of new practical software algorithms for quick and general decision of the variety of rectangular packing and cutting combinatorial optimization problems
Home Areas Products 3DLP 2DLP 1DSC Order Contact
Basic methods / approaches and achieved solution characteristics are as follows: 

Cutting and Packing

Generally, all described algorithms carry out (repetitively) first the statistically optimized preliminary sortings (with some additional aid of a kind of so called "Genetic algorithms"), and than a quick geometric procedure for compact arrangement of the formed queue of 2D rectangular parts (or 3D boxes) of arbitrary sizes into the 2D sheet (3D container) under the condition known as "Bottom Left" rule i.e. minimizing z, y, x - coordinates in consequence for each next part in the queue, or under any analogous rule. The developed  orthogonal arrangement technique permits to test and use some different packing heuristics. This method does not need any type of stripe-, layer-, or wall-building approaches.

In 2D case the single arrangement procedure for 40 parts takes near 6 ms with IBM / P133.  Asymptotically near optimum compact disposition of such a set requires about 400 attempts or iterations with different queue sortings.  Parts are allowed to turn.  For fixed number 20..40..80 part sets  (all parts being of uniformly distributed random sizes)  the statistically average cutting yields  94,5..94,8..95,4% are achieved.  The calculations require mean total run time 1,7..2,6..3,3 sec correspondingly, or at least 3 times less time to achieve 0.5% less efficiency (see auto run demo Y2d_nn.exe). 

For 3D case the above procedure for 16..32..64 boxes sets requires about 3,6..7,8..15 sec mean total run time (with boxes allowed to turn around any axis) to achieve average packing efficiencies 82,5..83,5..84% correspondingly (see demo Y3d_nn.exe).  Noted efficiencies are not fully optimized and may be increased by method / algorithm further adjustment or by calculation time essential increasing. 

1D Bin Packing algorithm is also available with typical packing efficiency near 99..100% achieved after less then 1 sec run time (demo Y1d_nn.exe). 

Limited Resource Scheduling (Geometric Approach) 

Above described 2D algorithm is directly suitable for the decision of a case of limited (constrained) resource scheduling optimization problem.  It means the scheduling of a number of jobs, each requiring a fixed amount of a resource (say, workers) and some fixed amount of time, - scheduling them within the total resource capacity to finish all jobs in a least possible time  (or, vice versa, to use minimum total resource amount to finish all jobs in a defined time). So initially this algorithm solves the problem of limited resource and time optimum distribution among independent jobs. Sequencing conditions may be taken into account  additionally, as well as the other constraints. 

For 3D case, including time and resources of two kinds (say, workers and equipment) corresponding case of the Multiple Resource Constrained Project Scheduling Problem requires essentially new geometrical approach: projections of any two boxes-jobs onto both vertical resource-time planes (XZ, YZ) are not allowed to overlap, since any worker or any equipment unit can not take part in two or more jobs simultaneously. 

This case is demonstrated in demo Y3dR_nn.exe - planning of a number of  jobs, each requiring a fixed amount of two kinds of resources and some fixed time, so as to finish all jobs in a least possible time.  With the present developed "Resource Packing" algorithm like above described packing procedure for 10..20..40  jobs or boxes requires about  2..4..8 sec mean calculation time to achieve average resource capacity utilization 81..84..85%.  This work is at the middle stage of the developing now. 

Free auto run demo programs for all above methods: 

Some of presented optimizers can be licensed for implementation into customer specific technology / software as exe / dll procedures. Please note that above old DOS demo programs may have problems running on very modern PCs. For up to date trial programs, please check our current software products.
Home Areas Products 3DLP 2DLP 1DSC Order Contact