Bug 37594

I am reviewing the subroutine _allocateWithTransportCostMatrix.

For two separate items to be allocated to the same hold it must be that
the hold have been duplicated.

Provided that the input array of hold requests does not contain any
duplicates, could it be the case that a duplicate is introduced
for example through an array indexing error?

The holds are maintained in the arrays @requests and @remaining:

    my @requests  = grep { !defined $_->{itemnumber} } @$hold_requests;
    my @remaining = ();

The idea is that if there are more requests than available items,
@requests should contain the first number of holds that could possibly
be filled with an item, while @remaining contains the rest.

But since it is possible that some items couldn't be allocated to any
of the first holds in the queue, if there are remaining items, any
holds that could not be filled will be removed from @requests and
holds in @remaining is moved to @requests and the allocation
is retried.

By inspecting the code for updates to @requests and @remaining we can
see that:

1. they are initiated such that any hold is either in @requests or in
   @remaining, never in both:

    if ( $num_tasks > $num_agents ) {
        @remaining = @requests[ $num_agents .. $num_tasks - 1 ];
        @requests  = @requests[ 0 .. $num_agents - 1 ];
        $num_tasks = $num_agents;
    }

2. Holds are removed from @requests without touching @remaining:

          Line 542:    splice @requests, $j - $j0, 1;

          Line 644:    splice @requests, $unallocated[$u], 1;

3. Holds are moved from @remaining to @requests or vice versa:

          Line 466:  push @requests, ( splice @remaining, 0, $nm );

          Line 561:  unshift @remaining, ( splice @requests, $num_agents );

Clearly none of these operations introduce duplicates.

The return value is generated from the @requests array.

The algorithm itself is supported by theoretical proof and will never
assign two agents (items) to the same task (hold, or specifically, element
in the @request array).

The perl implementation (version 0.08) was uploaded to CPAN 2008 and has
been distributed by Debian since 2009.

So, my conclusion is that it is unlikely that bug 35826 is the culprit.

I have libraries using bug 35826 applied to 23.11 in production and have not observed duplicated allocations.  But they are also not using RealTimeHoldsQueue.

*** This bug has been marked as a duplicate of bug 38126 ***