Smudger - 10 months ago 36

SQL Question

not 100% sure on title, feel free to edit to be more generic and helpful to all users

I have an order capture 'portal' which allows for orders to be captured. Part of the order is volume or the order.

I need to now process the order so that a pallet can be built that allows for optimal useage of pallets.

As an example, a packed pallet dimension can be 1.62 cubic meters (1x1.2x1.35)

I then have the following items on the order

**Product code, qty, total volume**

1, 10, 0.5 cubic meters

2, 3, 0.2 cubic meters

3, 5, 1.2 cubic meters

4, 1, 0.15 cubic meters

5, 15, 0.6 cubic meters

I want to process this, I am assuming with a mysql transaction so that the following output is acheived:

Pallet 1: Products 1,2,5. Total Volume=1.3 cubic meters

Pallet 2: Products 3,4. Total Volume=1.35 cubic meters

So to clarify, the script will take the first pallet of 0.5 cubes and then look for the next order in the list that is closest to 0.85 to acheive the 1.35 cubic meter target. in this case it will be 0.6. total now 1.1 cubes. remaining space is now 0.25 cubes. closest item in the list is now product 2 @ 0.2 cubes. total now 1.3 cubes and no product exists that is 0.05 cubes or less so pallet is complete. next available product is now product 3 @ 1.2 cubes. so product of 0.15 or less is required. product 4 is the exact volume so add to pallet and close off.

I hope that helps clarify my requirement.

Is there a mysql transaction that can assist with this or does this need to be processed with php.

Any help with this would be appreciated, just not sure how to build this logic.

Thanks for your time as always,

mysql Table is below:

Answer

This is the classic bin packing problem, which is NP-hard (that is, we have not yet worked out whether the problem can be solved in polynomial time). Finding the *optimal* packing is tantamount to trying out every possible combination.

If you don't care about finding the optimal solution, then the greedy heuristic that you describe in your question (which is known as first fit decreasing) is a reasonable approximation; there are other heuristics which can guarantee more optimal results overall, but they get quite complicated.

You can implement FFD in PHP as follows (using PDO for database access):

```
define('PALLET_SIZE', 1 * 1.2 * 1.35);
$dbh = new PDO("mysql:dbname=$dbname", $username, $password);
$qry = $dbh->prepare('
SELECT code, qty, volume
FROM orders
WHERE order_id = :order
ORDER BY volume DESC
');
$qry->execute(array(':order' => 123));
$pallets = array();
while ($order = $qry->fetch()) {
if ($order['volume'] > PALLET_SIZE) die('item too big');
for ($i = 1; $i <= $order['qty']; $i++) { // remove this loop if not needed
$placed = false;
foreach ($pallets as &$pallet) {
if ($pallet['remaining'] >= $order['volume']) {
$pallet['remaining'] -= $order['volume'];
$pallet['items'][] = $order['code'];
$placed = true;
break;
}
}
if (!$placed) $pallets[] = array(
'remaining' => PALLET_SIZE - $order['volume'],
'items' => array($order['code'])
);
}
}
print_r($pallets);
```