2
Dear Experts,
I have a real life scenario, where I need to solve a construction related problem somewhat similar to bin packing problem.The situation is as follows :
I have large number of cable reels/drums (lets say in the order of 20,000 numbers) each having varying lengths (random lengths between 200 meter to 3,000 meter) of cable in it.
I have to cut a large number of cables of different lengths (that randomly varies from 1 meter to 1000 meter).
I want to allocate the cables to these drums with two objectives viz. (a) minimize wastage or minimize total cable used for the whole allocation (b) Maximize the length of waste cables (e.g. instead of wasting two 10 meter cable, when absolutely necessary, I would try to waste one 20 meter) to increase the chance of re-usability.
I have used a dynamic algorithm (similar to solving a subset sum problem) to find the best fit for a specific cable reel/drum and get a fairly good solution.
However, this is not the most optimum solution for the following reasons :
(1) I don't know at the beginning which drum to take first for the allocation. The sequence at which I start allocation vastly affects the overall wastage.
(2) When there are multiple perfect combinations possible for zero wastage for a particular drum, choosing right combination from that for a overall optimization is my challenge.
(3) I end up making zero wastage for a drum, where I should actually keep some deliberate wastage to use up some specific cable, that will lead me to a over all minimized wastage. That means, making zero wastage for a drum is not necessarily the best solution, (especially when the cable lengths are in the order between 300 to 800 meter)
Seek your help !
Regards,
