0

I have an ordered list that represents terminals on a fibre cable where each terminal has a number of ports (e.g. 4, 8, 12). Given a fibre optic cable that will supply a different fibre strand to each terminal port. The cable may contain 144 fibre strands numbered 1-144 in groups of 12 fibres. I want to assign the fibre strands to the terminal ports such that at any one terminal I do not need to access fibres from more than one group. I want to assign the fibres in the order of the terminals as much as possible. I want to avoid unused fibre strands as much as possible.

For example, if I have terminals A, B, C, D, E, F with respective port sizes of 12, 8, 12, 6, 6, 12 I would like the algorithm to produce the result A (1-12), B (49-56), C (13-24), D (25-30), E (31-36), F (37-48)

Can anyone suggest an ideal algorithm?

3
  • In your example, wouldn't 57-60 still count as unused, thus B would be preferred at 13-20? Does the avoiding unused fibre strands preference always outweigh the ordering preference? Also (assuming A and D fit together and B and C do also), would the order ADBC or BCAD be considered better? Jun 7, 2013 at 23:06
  • This seems to match the Cutting stock problem. Jun 7, 2013 at 23:25
  • @Dukeling it is ideal to leave unused fibres 57-60 at the end of the cable. Using 13-20 for B would mean 4 fibres unused. Jun 8, 2013 at 13:21

1 Answer 1

1

The problem is bin packing with a side of ordering. Bin packing alone is NP-hard, so the running time of the exact algorithm that I'm going to suggest is not polynomial. Hopefully it will be useful anyway.

The first step is to generate all possible groups. Here's some Python to demonstrate what I mean.

def allgroups(terminals, fibrecount=12, groupsofar=[]):
    if terminals:  # is nonempty
        terminal = terminals.pop()  # last element
        if terminal.portsize <= fibrecount:
            groupsofar.append(terminal)
            yield from allgroups(terminals, fibrecount - terminal.portsize, groupsofar)
            groupsofar.pop()  # terminal
        yield from allgroups(terminals, fibrecount, groupsofar)
        terminals.append(terminal)
    elif groupsofar:
        yield groupsofar

The second step is to generate all possible groupings with Algorithm X, and the third step is to evaluate each of the groupings via dynamic programming. You didn't say what "in the order of the terminals as much as possible" means, so I'll try to minimize inversions. Actually the exact objective doesn't matter as long as it has optimal substructure, namely, given two orderings of the same groups, one is always better than the other regardless of how the other groups are arranged.

Before running the dynamic program, count, for every pair of groups, the number of inversions if the first appears before the second. This means an outer loop iterating over the first group and an inner loop iterating over the second, counting the number of times a terminal in the first group should have appeared after a terminal in the second. Now, for each subset of groups in nondecreasing order, determine the optimal order of that subset. Because of optimal substructure, the optimal order begins with some group in the subset and ends with the optimal solution we've already computed for the remainder. Minimize over all choices of which group comes first.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.