Method for merging, within a logistical warehouse, k incoming flows of payloads into one outgoing flow

Abstract

Method for merging, within a logistical warehouse, k incoming flows of payloads, transported respectively by k FIFO conveyor lanes α.sub.i with i∈{1, . . . , k} into one outgoing flow of payloads transported by a collector conveyor. The k lanes are distributed along the collector and numbered a.sub.1 to a.sub.k. Δ.sub.i is a time-related distance between the lanes a.sub.i and a.sub.k. A control system obtains a set L having n payloads distributed on the k lanes and having to be injected into the collector to form an exit sequence; computes a date t.sub.0 at which the first payload σ.sub.1 of the exit sequence σ passes in front of the lane a.sub.k; and computes n dates of injection of the n payloads into the collector, as a function of t.sub.0; and commands the collector and the k alleys, for an injection of the n payloads into the collector in compliance with the injection dates.

Claims

1. A method for merging, within a logistical warehouse, k incoming flows of payloads, transported respectively by k conveyors called lanes α.sub.i with i∈{1, . . . , k}, into one outgoing flow of payloads transported by another conveyor called a collector: the logistical warehouse being such that the k lanes are of a “first-in-first-out” type, distributed along the collector and numbered a.sub.1 to a.sub.k in one sense of movement of the collector, and Δ.sub.i is a time-related distance between the lanes a.sub.i, and a.sub.k expressed in time units corresponding each to one time span of the collector, the method being executed at least once by a control system, a given execution being performed at an instant Tb and comprising: obtaining a set L comprising n payloads distributed at the instant Tb on the k lanes and having to be injected into the collector to form an exit sequence σ, each of the n payloads being identified by a single sequence number within the exit sequence σ, each of the k lanes containing an ordered set, ordered in a rising order of sequence numbers, of h.sub.i, payloads having to be injected one by one into the collector; computing a date t.sub.0 at which the first payload σ.sub.1 of the sequence a passes in front of the lane a.sub.k; computing a date of injection into the collector of each of the n payloads of the set L according to the following formula: T(u)=t.sub.0+σ(u)−1 −Δ.sub.i, with: u=α.sub.i(j)∈L, a payload of the set L and coming from the j.sup.th position in the lane a.sub.i, i∈{1, . . . , k}, j∈{1, . . . , h.sub.i}, σ(u) is the sequence number of the payload u in the exit sequence σ; commanding the collector and the k lanes, for an injection of the n payloads into the collector in compliance with the n injection dates T(u), ∀u ∈L.

2. The method according to claim 1, wherein Δ.sub.i,i, is a time-related distance between the lanes a.sub.i, and a.sub.i, expressed in time units each corresponding to a time span of the collector, and further comprising: for each payload u=α.sub.i(j)∈L coming from a lane a.sub.i, computing the dates of passage of the payload in front of the lanes a.sub.i to a.sub.k, the date of injection T(u) of the payload into the collector being known; for each lane a.sub.i, i∈{1, . . . , k}, obtaining a set V.sub.i each containing a date of passage of one of the payloads in front of the lane a.sub.i; for each controlled disturbing payload p of a disturbing flow controlled by a controller situated along the collector and before a lane a.sub.g(p) in the sense of movement of the collector, with g(p)∈{1, . . . , k}, a.sub.g(p) being also the first lane, in the sense of movement of the collector, in front of which the controlled disturbing load passes: a) initializing t with the date δ.sub.1−Δ.sub.1, with δ.sub.1 representing the possible date of arrival of the first controlled disturbing load in front of the lane a.sub.k if this load is not put on hold; b) computing the dates t+Δ.sub.1,g(p), t+Δ.sub.1,g(p)+1, . . . , t+Δ.sub.1,l(p) of passage of the controlled disturbing load in front of the lanes a.sub.g(p) to a.sub.l(p), with a.sub.l(p) being the last lane, in the sense of the movement of the collector, in front of which the controlled disturbing load passes; c) if none of the dates t+Δ.sub.1,g(p), t+Δ.sub.1,g(p)+1, . . . , t+α.sub.1,l(p) belongs respectively to the sets V.sub.g(p), V.sub.g(p)+1, . . . , V.sub.l(p), computing a fictitious date of passage start.sub.p of the controlled disturbing load p in front of the lane a.sub.1, with the following formula: start.sub.p=t; d) if one of the dates t+Δ.sub.1,g(p), t+Δ.sub.1,g(p)+1, . . . , t+Δ.sub.1,l(p) belongs respectively to one of the sets V.sub.g(p), V.sub.g(p)+1, . . . , V.sub.l(p), incrementing t by one unit and reiterating b), c) and d) with the new value of t; commanding the controller, for an injection at the date start.sub.p+Δ.sub.1,g(p) of each controlled disturbing load p before the lane a.sub.g(p).

3. A method for merging, within a logistical warehouse, k incoming flows of payloads, transported respectively by k conveyors called lanes α.sub.i with i∈{1, . . . , k}, into one outgoing flow of payloads, transported by another conveyor called a collector, the logistical warehouse being such that: the k lanes are of a “first-in-first-out” type, distributed along the collector and numbered a.sub.1 to a.sub.k in one sense of movement of the collector, and Δ.sub.i is a time-related distance between the lanes a.sub.i and a.sub.k expressed in time units each corresponding to one time span of the collector, the method being executed at least once by a control system, a given execution being done at an instant Tb and comprising: obtaining a set comprising n payloads distributed at the instant Tb on the k lanes and having to be injected into the collector to form an exit sequence σ, each of the n payloads being identified by a single sequence number within the exit sequence σ, each of the k lanes containing an ordered set, in a rising order of sequence numbers, of h.sub.i payloads having to be injected one by one into the collector; for each lane a.sub.i, i∈{1, . . . , k}, obtaining a set U.sub.i of dates not valid for an injection of one of the payloads of the lane a.sub.i into the collector because of a non-controlled disturbing load or another obstruction of a time span of the collector; in not taking account of the sets U.sub.i, i∈{1, . . . , k}, computing a date t.sub.0 at which the first payload σ.sub.1 of the exit sequence a passes in front of the lane a.sub.k; for the first payload σ.sub.1 of the exit sequence a, in assuming that the first payload σ.sub.1 comes from the lane a.sub.i: a) initializing t with t.sub.0; b) if none of the dates t, t−Δ.sub.k-1, t−Δ.sub.k-2, . . . , t−Δ.sub.i belongs respectively to the sets U.sub.k, U.sub.k-1, U.sub.k-2, . . . , U.sub.i, computing a date of injection of the first payload σ.sub.1=α.sub.i(j); into the collector with the following formula: T(u)=t−Δ.sub.i, with u=σ.sub.1=α.sub.i(j); c) if one of the dates t, t−Δ.sub.k-1, t−Δ.sub.k-2, . . . , t−Δ.sub.i belongs respectively to one of the sets U.sub.k, U.sub.k-1, U.sub.k-2, . . . , U.sub.i, incrementing t by one unit and reiterating b) and c) with the new value of t ; for each following payload σ.sub.c of the exit sequence σ, c∈{2, . . . , n}, in assuming that the following payload a comes from the lane a: a′) incrementing t by one unit, with t used to compute the date of injection of the preceding payload σ.sub.c-1; b′) if none of the dates t, t−Δ.sub.k-1, t−Δ.sub.k-2, . . . , t−Δ.sub.i belongs respectively to the sets U.sub.k, U.sub.k-1, U.sub.k-2, . . . , U.sub.i, computing a date of injection of the following payload σ.sub.c into the collector with the following formula: T(u)=t−Δ.sub.i, with u=σ.sub.c=α.sub.i(j); c′) if one of the dates t, t−Δ.sub.k-1, t−Δ.sub.k-2, . . . , t−Δ.sub.i belongs respectively to one of the sets U.sub.k, U.sub.k-1, U.sub.k-2, . . . , u.sub.i, incrementing t by one unit and reiterating b′) and c′) with the new value of t; commanding the collector and the k lanes for an injection of the n payloads into the collector in compliance with the n injection dates T(u),∀u∈L.

4. The method according to claim 3, wherein the commanding the collector and the k lanes for an injection of the n payloads into the collector in compliance with the n injection dates T(u),∀u∈L, is preceded by: computing t.sub.min according to the following formula: t.sub.min=min{T(u),∀u ∈L}; if t.sub.min>0, modifying the n injection dates according to the following formula: T(u)=T(u)−t.sub.min∀u∈L.

5. The method according to claim 3, wherein Δ.sub.i,i, is a time-related distance between the lanes a.sub.i and a.sub.i′ and expressed in time units each corresponding to a time span of the collector and the method furthermore comprises: for each payload u=α.sub.i(j)∈L coming from a lane a.sub.i, computing the dates of passage of the payload in front of the lanes a.sub.i to a.sub.k, the injection date T(u) of the payload into the collector being known; for each lane a.sub.i, i∈{1, . . . , k}, obtaining a set V.sub.i containing, on the one hand, each date of passage of one of the payloads in front of the lane a.sub.i and, on the other hand, the set U.sub.i of dates not valid for an injection of one of the payloads of the lane a.sub.i into the collector; for each controlled disturbing load p of a disturbing flow controlled by a controller situated along the collector and before a lane a.sub.g(p) in the sense of movement of the collector, with g(p)∈{1, . . . , k}, a.sub.g(p) also being the first lane, in the sense of movement of the collector, in front of which the controlled disturbing load passes: a) initializing t with the date δ.sub.1−Δ.sub.1, with δ.sub.1 representing the possible date of arrival of the first disturbing load in front of the lane a.sub.k if this load is not put on hold; b) computing dates t+Δ.sub.1,g(p), t+Δ.sub.1,g(p)+1, . . . , t+Δ.sub.1,l(p) of passage of the controlled disturbing load in front of the lanes a.sub.g(p) to a.sub.l(p), with a.sub.l(p) being the last lane, in the sense of movement of the collector, in front of which the controlled disturbing load passes; c) if none of the dates t+Δ.sub.1,g(p), t+Δ.sub.1,g(p)+1, . . . , t+Δ.sub.1,l(p) belongs respectively to the sets V.sub.g(p), V.sub.g(p)+1, . . . , V.sub.l(p), computing a fictitious date of passage start.sub.p of the controlled disturbing load pin front of the lane a.sub.1, with the following formula: start.sub.p=t; d) if one of the dates t+Δ.sub.1,g(p), t+Δ.sub.1,g(p)+1, . . . , t+Δ.sub.1,l(p) belongs respectively to one of the sets V.sub.g(p), V.sub.g(p)+1, . . . , V.sub.l(p), incrementing t by one unit and reiterating b), c) and d) with the new value of t; commanding the controller for an injection at the date start.sub.p+Δ.sub.1,g(p) of each controlled disturbing load p before the lane a.sub.g(p).

6. The method according to claim 1, wherein the date to is computed with the following formula: $t_0=\underset{u=a_i\left(j\right)\in L^{\prime }}{\max }\left\{{\Delta }_i+1-\sigma \left(u\right)\right\},$ with: u=α.sub.i(j)∈L′, a payload of a set L′ comprising payloads placed in first position of the lanes situated, according to the sense of movement of the collector, from the lane a.sub.1 up to the lane a.sub.i1 containing the first payload σ.sub.1 of the exit sequence σ.

7. The method according to claim 1, wherein the method is executed iteratively, each new execution being carried out at a new instant Tb computed with the following formula:Tb=T(u.sub.last)−Δ.sub.1+Δ.sub.i.sub.last, with u.sub.last=α.sub.i.sub.last(J.sup.last) a last payload coming from the (j.sup.last).sup.th position in the lane α.sub.i.sub.last, of the exit sequence σ of a preceding execution at a preceding instant Tb.

8. The method according to claim 1, wherein the method is executed iteratively, each new execution being carried out at a new instant Tb defined as an instant at which no load of the exit sequence σ of a preceding execution at a preceding instant Tb is situated in a portion of the collector going from the first lane a.sub.1 to the lane α.sub.i.sub.1 containing the first load of the exit sequence σ of the new execution at the new instant Tb.

9. The method according to claim 1, it wherein the method is executed iteratively, each new execution being carried out at a new instant Tb computed with the following formula: Tb=Max(Tb+1, T(u.sub.last)−Δ.sub.1 +Δ.sub.i.sub.last), with: u.sub.last=α.sub.i.sub.last(j.sup.last) being a last payload, coming from the (j.sup.last).sup.th ) position in the lane α.sub.i.sub.last, of the exit sequence σ of a preceding execution at a preceding instant Tb, and (Tb+1) being obtained by an incrementing, by one unit, of the preceding instant Tb.

10. The method according to claim 3, wherein the date to is computed with the following formula: $t_0=\underset{u=a_i\left(j\right)\in L^{\prime }}{\max }\left\{{\Delta }_i+1-\sigma \left(u\right)\right\},$ with: u=α.sub.i(j)∈L′, a payload of a set L′ comprising payloads placed in first position of the lanes situated, according to the sense of movement of the collector, from the lane a.sub.1 up to the lane a.sub.i1 containing the first payload σ.sub.1 of the exit sequence σ.

11. The method according to claim 3, wherein the method is executed iteratively, each new execution being carried out at a new instant Tb computed with the following formula:Tb=T(u.sub.last)−Δ.sub.1+Δ.sub.i.sub.last, with u.sub.last=α.sub.i.sub.last(j.sup.last) a last payload coming from the (j.sup.last).sup.th position in the lane α.sub.i.sub.last, of the exit sequence σ of a preceding execution at a preceding instant Tb.

12. The method according to claim 3, wherein the method is executed iteratively, each new execution being carried out at a new instant Tb defined as an instant at which no load of the exit sequence a of a preceding execution at a preceding instant Tb is situated in a portion of the collector going from the first lane a.sub.1 to the lane a.sub.i.sub.1 containing the first load of the exit sequence σ of the new execution at the new instant Tb.

13. The method according to claim 3, wherein the method is executed iteratively, each new execution being carried out at a new instant Tb computed with the following formula: Tb=Max(Tb+1,T(u.sub.last)−Δ.sub.1+Δ.sub.i.sub.last), with: u.sub.last=α.sub.i.sub.last(j.sup.last) being a last payload, coming from the (j.sup.last).sup.th position in the lane α.sub.i.sub.last, of the exit sequence a of a preceding execution at a preceding instant Tb, and (Tb+1) being obtained by an incrementing, by one unit, of the preceding instant Tb.

Description

4. LIST OF FIGURES

(1) In the following description, given by way of an indicative and non-exhaustive example, reference is made to the appended drawings, of which:

(2) FIG. 1 shows an existing method for the insertion of loads in a given sequential order;

(3) FIG. 2 is an image of two lanes (conveyors), one collector and one load (box);

(4) FIG. 3 is a drawing of two lanes (conveyors), one collector and one load (box);

(5) FIG. 4 is a drawing of the system under study in lanes

(6) FIG. 5 is a drawing of the system with identification of the loads by their sequential number;

(7) FIG. 6 shows a departure point and an injection point;

(8) FIG. 7 shows coinciding points without loss with respect to the general configuration;

(9) FIG. 8 shows a slicing of the collector into spans (positions or slots);

(10) FIG. 9 shows the desired exit sequence expected in the slicing of the collector;

(11) FIG. 10 shows the time unit associated with the collector span relative to the duration of injection of a load;

(12) FIG. 11 shows distances as integer values between the injection flows;

(13) FIG. 12 shows distances between the injection flows that are not required to be integer values;

(14) FIG. 13 is a drawing of the collector with injection points placed consecutively at each span;

(15) FIG. 14 shows an example of collector with four-lane that are placed consecutively according to span of the collector;

(16) FIG. 15 is a Gantt chart related to the job shop and retrieving data to be computed by formula;

(17) FIG. 16 show an example of a collector with four lanes that are placed in any unspecified manner;

(18) FIG. 17 is a Gantt chart related to the job shop with any unspecified distances between the lanes;

(19) FIG. 18 shows an example of a collector and two lanes with the identifiers of the loads;

(20) FIG. 19 shows an example of a collector and two lanes with the sequential order number identifiers;

(21) FIG. 20 shows an example of a collector and two lanes with sequence number identifiers;

(22) FIG. 21 shows an image of the collector at the instant 0;

(23) FIG. 22 shows an image of the collector at the instant 1;

(24) FIG. 23 shows an image of the collector at the instant 2;

(25) FIG. 24 shows an image of the collector at the instant 3;

(26) FIG. 25 shows an example of a FIFO list associated with three lanes;

(27) FIG. 26 shows an achievable sequence, expected on the collector;

(28) FIG. 27 shows the first load of the flow attached to the injection point, forming part of the FIFO list;

(29) FIG. 28 shows the first load of the flow not attached to the injection point, not forming part of the FIFO list;

(30) FIG. 29 shows loads on continuous hold behind a first load forming part of the FIFO list;

(31) FIG. 30 shows loads on continuous hold behind a first load not forming part of the FIFO list;

(32) FIG. 31 shows an example of a work batch;

(33) FIG. 32 shows a computation of the dates of injection and processing of the batch 1;

(34) FIG. 33 shows the processing of a batch in progress;

(35) FIG. 34 shows the end of processing of the batch 1 and the formation of the batch 2;

(36) FIG. 35 shows the end of processing of the batch 2 and its application;

(37) FIG. 36 is a chart of the algorithm in the general case with non-controlled disturbing flow;

(38) FIG. 37 shows an example of a disturbing flow: grey-colored loads returning to the PTS;

(39) FIG. 38 shows an example of a collector with four unspecified lanes with non-controlled disturbing flow;

(40) FIG. 39 is a Gantt chart with non-controlled disturbing flow forming spaces;

(41) FIG. 40 is a chart of algorithm 4;

(42) FIG. 41 shows an example of a collector with four lanes placed in any unspecified way with controlled disturbing flow;

(43) FIG. 42 is a Gantt chart of the injections showing the spaces to be used for the disturbing loads;

(44) FIG. 43 is a Gantt chart when choosing the placing of the disturbing loads;

(45) FIG. 44 shows a structure of a control system according to one particular embodiment of the invention;

(46) FIG. 45 is a chart of the algorithm 5;

(47) FIG. 46 is a flowchart of a method of merging k incoming flows into one outgoing flow, according to a first particular embodiment based on the algorithm 2;

(48) FIG. 47 is a flowchart of a method of merging k incoming flows into one outgoing flow, according to a second particular embodiment based on the algorithm 3 (illustrated in FIG. 36);

(49) FIG. 48 is a flowchart of a method of merging k incoming flows into one outgoing flow, according to a third particular embodiment based on the algorithm 4 (illustrated in FIG. 40);

(50) FIG. 49 is a flowchart of a method of merging k incoming flows into one outgoing flow, according to a fourth particular embodiment based on the algorithm 5 (illustrated in FIG. 45);

(51) FIG. 50 shows an example of an application.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

5. Control System Parameters

(52) As mentioned further above, the system under study is formed by a drain-off system (a conveyor called a collector), several other conveyors (called lanes) and loads. The system is dynamic, and the loads are transported by the lanes, injected into the collector and then transported by the collector. In a first stage, we shall consider the state of this system in freezing the position of each load present in it at a given instant. We shall define the frozen sub-systems of this system to be able to compute future dates of injection of certain loads. This corresponds to the resolution of the static problem. Section 7 shall examine the way to control and steer this system dynamically.

(53) FIG. 2 is an image illustrating two lanes (conveyors) 2.sub.1, 2.sub.2, one collector 1 and one load (box or carton) 6. FIG. 3 is a modelized view of the elements appearing in the image of FIG. 2 (and keeps the same numerical references).

5.1 Notations

(54) The table here below is a summary of the notations.

(55) TABLE-US-00001 TABLE 1 k Number of injection flows (incoming flows) of the system a.sub.i, k lanes (conveyors) each transporting i ∈ {1, . . . , k} an ordered set of loads at a given instant h.sub.i, Number of loads present on the lane i ∈ {1, . . . , k} (conveyor) a.sub.i $n=\underset{i=1...k}{\Sigma }{h}_i$ Total number of loads to be injected into the collector L Set of loads to be injected into the collector u = a.sub.i(j), Load u ∈ L, coming from the j.sup.th i ∈ {1, . . . , k}, position in the lane a.sub.i j ∈ {1, . . . , h.sub.i} σ Desired exit sequence, ordering all the loads of L σ(u), Position of the load u in the exit u ∈ L sequence σ.sub.c c.sup.th load of the sequence σ, belonging to L set u = a.sub.i(j) to σ.sub.c signifies the computation of u, i, j for the load σ.sub.c L′ Set of loads placed in first position of the lanes situated between the lane a.sub.1 and the lane containing the first load of the sequence σ (i.e. σ.sub.1) T.sub.D (u), Departure date of the load u, u ∈ L coinciding with the departure point, namely the instant at which the load must leave its lane (conveyor) T(u), Date of injection of the load u into u ∈ L the collector, coinciding with the injection point at which the load arrives physically on the collector Pt.sub.i, Time needed to travel the distance i ∈ {1, . . . , k} between the departure point and the injection point for a load of the lane a.sub.i The <<span>> Time unit corresponding to the sub- division (or slicing) of the collector into time spans (also called time positions or time slots) The date 0 Date as which we can start injecting the loads into the collector (date taking the form of the first unoccupied location on this collector) The date t.sub.0 Date at which the first load of the desired exit sequence passes in front of the lane a.sub.k Δ.sub.i, Distance in “spans” between the lane a.sub.i and i ∈ {1, . . . , k} the lane a.sub.k Δ.sub.i,j, Distance in “spans” between the lane a.sub.i and i ∈ {1, . . . , k − 2}, the lane a.sub.j j ∈ {1, . . . , k − 1}
5.1.1 Notations on Lanes of the Conveying System

(56) For a configuration of the system at a given instant, each lane will comprise an ordered set of loads. Let k be the number of lanes in our system, each lane being numbered α.sub.1 to α.sub.k in the sense of movement of the collector. These lanes respectively possess a number h.sub.i of loads represented by a First-In-First-Out (FIFO) list that has to be injected one by one into the collector.

(57) An example is given in FIG. 4. The sense of movement of the collector 1 is from right to left, this direction being indicated by the arrow. Each lane is numbered and comprises ordered loads which will have to be injected one by one, from bottom to top, into the collector. In this example, we therefore have k=3 with h.sub.1=2, content of α.sub.1={id11, id12}, h.sub.2=3, content of α.sub.2={id21, id22, id23} and h.sub.3=4, content of a.sub.3={id31, id32, id33, id34}.

(58) 5.1.2 Notations of Loads to be Injected

(59) There are n loads (boxes, bins, containers, etc.) in all to be injected into the collector, coming from the different injection flows. Let L denote the set of these loads and u=α.sub.i(j) a load u belonging to L, coming from the j.sup.th position in the lane α.sub.i.

(60) In addition, let σ be the exit sequence in which these loads must be ordered once they are all injected into the collector. The function ø(u) gives the position of the load u in this sequence. Each load can thus be identified by a single “sequence” number between 1 and n, corresponding to its position in the desired exit sequence (σ). This is how we will identify the loads here below. It can be noted that, in this case, it is easy to verify if the sequence is achievable: it is enough for each lane to have an ordered list of loads identified by sequence numbers in rising order that are not necessarily consecutive.

(61) Let us now specify the set L′, specially grouping together the first loads awaited in the final exit sequence, placed at the first position of the lanes α.sub.1, α.sub.2, . . . , α.sub.i.sub.1 with i.sub.1 being the lane number containing the first load of this sequence σ. This set brings together all the loads that can be the first load of the sequence to be injected into the collector. Indeed, a load in first position in a lane placed upstream to the lane comprising the first load of the sequence is likely to be injected first, while at the same time being situated behind the first load in the final flow of the collector. However, a load in first position in the lanes downstream from the lane comprising the first load will never be injected before this first load into the collector.

(62) FIG. 5 shows a diagram equivalent to that of FIG. 4 in taking the achievable sequence σ={id21, id31, id22, id11, id23, id32, id33, id34, id12}. In this example, n=9, therefore each load has a unique sequence number enabling it to be identified while at the same time speedily knowing its desired position in the sequence σ. FIG. 5 immediately makes it possible to see that the chosen sequence is achievable, indeed content of α.sub.1={4,9}, content of α.sub.2={1,3,5} and content of α.sub.3={2,6,7,8}. In addition, we have the particular set L.sub.i.sub.1={id11, id21}={4,1}.

(63) 5.1.3 Departure Dates and Injection Dates

(64) It may be recalled that each lane corresponds to an injection flow at a given instant, represented as a FIFO column attached to the collector. However, in the warehouse, it can happen that the load awaiting injection is at a distance from the collector. Let departure point denote the place at which this load awaits the order to depart from its lane (conveyor), illustrated by a point attached to the FIFO column, and let injection point denote the space of the collector that is the first to be touched by the load in the course of being really injected into this collector, illustrated by a dot attached to the collector in FIG. 6.

(65) In the diagrams of the system in lanes, these two points (dots) coincide and are represented in black in FIG. 7. In reality, these points are often different, and the duration needed for a load of the flow i to pass from one point to the other is called Pt.sub.i (see FIG. 6). The departure date T.sub.D of the load when it must leave its lane (conveyor) is linked to its date of injection T into the collector (coinciding with the injection point) by the following simple formula: T.sub.D=T−Pt.sub.i. Consequently, without loss in terms of general description here below, we shall present solely the computations of the injection dates.

5.2 Data Structure

(66) 5.2.1 Sub-Dividing the Drain-Off System (Collector): Time Unit (Time Span)

(67) The drain-off system (or collector) will be considered as a system with time spans (like a sorter) also called slots or positions.

(68) FIG. 8 illustrates the sub-division into time spans (positions or slots) of the collector.

(69) Thus, our goal of obtaining a maximum throughput with an ordered outgoing flow amounts to filling the spans of the collector as can be seen in FIG. 9.

(70) We shall consider a time unit corresponding to this time span that sub-divides the collector, according to its speed of movement. A time unit, called a “time span”, corresponds to the duration needed for a point of the collector to move exactly by the physical distance corresponding to one position. The distance defined for this position corresponds to the size of a load plus a security distance. This security distance must be adjusted according to the needs of those skilled in the art and in order to comply with the following condition (illustrated in FIG. 10).

(71) The time unit must obligatorily be greater than the time taken by a load to be injected into the collector from the time when a part of the load touches the collector up to the time when the entire load is placed accurately on the collector (i.e. in its flow).

(72) 5.2.2 Distance from the Injection System

(73) As illustrated in FIG. 11, Δ.sub.i is defined as corresponding to the number of time spans of the collector (drain-off system) between the lane α.sub.i and the last lane α.sub.k, as can be seen in the following figures with k=3. As illustrated in FIG. 12, it is possible for this number not to be an integer. Δ.sub.k=0.

(74) The time distance between two lanes a.sub.i and a.sub.j is denoted as Δ.sub.i,j, the second index being the lane relative to which operation is situated.

(75) 5.2.3 Associated Job Shop Model

(76) The following table is a summary of the notations of the Job Shop model

(77) TABLE-US-00002 TABLE 2 {J.sub.u, u ∈ Set of n jobs associated with a {1, . . . , n}} Job Shop model. The u.sup.th load of the sequence σ is denoted as σ.sub.u = a.sub.i (j), occupies the j.sup.th place of the lane a.sub.i and is associated with the job J.sub.u {M.sub.1, . . . , M.sub.k} Set of k machines of the Job Shop model. The lane a.sub.i is associated with the machine M.sub.i. {o.sub.u,i, o.sub.u,{i + 1}, List of k − i consecutive operations associated . . . o.sub.u,k} with the job J.sub.u, it being known that the u ∈ {1, . . . ,n}, operation o.sub.u,i must be carried out on σ.sub.u = a.sub.i (j) the machine M.sub.i.

(78) For each exit sequence σ, we model the system as a unit-job Job Shop model, with n jobs and k machines. Each load of the sequence σ.sub.u (u.sup.th load of this sequence) is associated with a job J.sub.u and each lane α.sub.i is associated with a machine M.sub.i. Each job J.sub.u associated with a load contained in the lane α.sub.i must follow an ordered list of k−i+1 unit operations {o.sub.u,i, o.sub.u,{i+1}, . . . , o.sub.u,k}. An operation denoted as o.sub.u,i is a unit job of the job J.sub.u to be performed specifically on the machine M.sub.i. A job can be assigned to only one machine at a time and a machine can carry out only one operation at a time.

(79) We shall try to schedule these jobs on the machines in complying with the sequential order given by their respective list of operations. The goal is to schedule them in order to minimize the total duration of execution of all these jobs.

6. DETERMINING THE DATE OF INJECTION OF EACH LOAD, FOR A COLLECTOR PROCESSING ONLY THE INJECTION FLOWS

(80) In this part, we shall consider a collector processing only the injection flows. The collector is entirely vacant and ready to retrieve the injection flows. Only the merger of these injection flows must be controlled to accurately inject their loads in order to have a final flow that is fluid, continuous and corresponds to the desired exit sequence.

(81) 6.1 Solution for Consecutively Well-Distributed Lanes

(82) In order to simplify matters, we shall assume that the injection flows are distributed consecutively on the collector in such a way that a time interval is needed for a load on the collector to pass from one injection zone to the next as can be seen in FIG. 13. This simplified case corresponds to Δ.sub.i,i+1=1, for all i∈{1, . . . , k−1}.

(83) 6.1.1 Modelling the System as a Job Shop Scheduling

(84) We shall explain the modelling of the system as a problem of Job Shop scheduling in this particular case.

(85) Each of then loads is associated with a job J.sub.u, u∈{1, . . . , n}, with numbering in accordance with the sequence number of the load. Thus, if σ.sub.u corresponds to the u.sup.th load in the sequence σ, then its associated job is J.sub.u. The operations of these jobs must be processed by a set of k machines {M.sub.1, . . . , M.sub.k}. An operation can be allotted to only one machine at a time. Each machine is associated with a lane (i.e. an injection flow) that can carry out only one operation at a time. It may be recalled that these lanes are numbered {α.sub.1, . . . , α.sub.k}, from upstream to downstream (i.e. according to the sense of conveyance of the collector).

(86) Thus, a load σ.sub.u being injected into the collector from the lane α.sub.i will pass in front of each lane a.sub.j with j in {i, i+1, . . . , k}. This mechanism is represented by the fact that each job associated with a load of the lane α.sub.i is composed of k−i+1 unit operations {o.sub.u,i, o.sub.u,{i+1}, . . . , o.sub.u,k} to be processed consecutively without waiting. Each operation has to be scheduled on a specific machine. Thus, if the operation o.sub.u,i (processed by the machine M.sub.i) starts at the instant t, the operation o.sub.u,{i+1} (processed by the machine M.sub.{i+1}) starts at the instant t+1, etc., and finally the operation o.sub.u,k (processed by the machine M.sub.k) starts at the instant t+k−i.

(87) If the starting instant of the first operation o.sub.u,i of this job corresponds to the date of injection into the collector, the starting instants of the following operations (c.-à-d. {o.sub.u{i+1}, . . . , o.sub.u,k}) represent the instants at which the load is in front of the following lanes.

(88) It can be noted that each job is composed of at least one operation on the last machine M.sub.k (since each load passes in front of at least the last lane α.sub.k). The sequence of the operations scheduled on the machine M.sub.k corresponds exactly to the order in which the loads will pass in front of the last lane and their departure date corresponds to the instant when these loads will pass in front of this last injection lane. This is why, if the load u is before the load v in the given exit sequence, the last operation of u must begin before the last operation of v on M.sub.k.

(89) The goal of not having space on the collector amounts to not having idle time between the operations of the machine M.sub.k.

(90) 6.1.2 Principle of the Algorithm Enabling the Injection Dates to be Attained

(91) The scheduling problem proposed here above can be resolved by the following algorithm. To begin with, assuming that the first load of the sequence comes from the lane α.sub.i, the operations {o.sub.1,i, o.sub.1,{i+1}, . . . , o.sub.1,k} associated with this job start at the instants t, t+1, . . . t+k−i. Then, the operations of the job corresponding to the next load of the sequence will be scheduled first of all by executing the operation to be processed on the machine M.sub.k. This operation o.sub.u,k will be scheduled just after the previous operation programmed on M.sub.k (without idle time). In assuming that this operation begins at the instant t, the operation on the machine M.sub.{k-1} (if it exists) is scheduled at the instant t−1, and so on and so forth, until all the operations are programmed. This procedure is applied iteratively to each of the following jobs of the given sequence.

(92) The real dates of injection into the collector are deduced directly from the start of the first operation of each job. The time unit used is the one defined here above (“the time span” of the collector).

(93) 6.1.3 Computation of Dates of Injection by Formula

(94) Now that we have described how the algorithm for resolving the scheduling problem works, we shall deduce the formula used to compute the injection dates.

(95) The notations used in the formula here below are those of the summary table discussed further above.

(96) Let us fix the origin of the time at the earliest date of injection of the very first load or loads injected into the collector. In the present system, the unoccupied location that will receive this load is therefore placed just in front of the lane of this load at the instant 0. Thus, we will compute the date

(97) $t_0=\underset{u=a_i\left(j\right)\in L^{\prime },1\le i\le k,1\le j\le h_i}{\max }\left\{k+1-i-\sigma \left(u\right)\right\}$
corresponding to the earliest date at which the first load of the sequence passes in front of the lane a.sub.k.

(98) Proof: Let 0 be the date at which the injection of the load starts. Let t.sub.0 be the date at which the first load of the sequence (i.e. σ.sub.1) passes in front of the lane a.sub.k. We note that the first load injected into the collector is necessarily a load at the head of a lane, in a lane situated from the lane a.sub.1 to the lane of σ.sub.1. Let L′⊂L be this sub-set of loads.

(99) Therefore, for any load u=α.sub.i(j)∈L′, we know that if it were to be injected at the date x, it would pass in front of the lane α.sub.k at the date x+k−i. We have x≥0 since we cannot inject the load before the date 0. Now, by definition of t.sub.0, the load u will pass in front of the lane α.sub.k at the date t.sub.0+σ(u)−1=x+k−i. That is, t.sub.0+σ(u)−1−k+i=x≥0.

(100) From this, we deduce that for all u=α.sub.i(j)∈L′, t.sub.0≥k+1−i−σ(u). We search for the earliest date enabling the verification of all these constraints, therefore:

(101) $t_0=\underset{u=a_i\left(j\right)\in L^{\prime }}{\max }\left\{k+1-i-\sigma \left(u\right)\right\}$

(102) The algorithm 1 here below gives the dates of injection T(u), i.e. the dates of entry of each load u into the collector. The time unit used is the “time span” defined further above. The algorithm 1 gives the formula for computing these injection dates should the flows get injected at each consecutive location on the collector (see FIG. 14).

(103) TABLE-US-00003 Algorithm 1: Computation of the dates of injection without disturbing flow in one particular case Require: σ, k, L′, a.sub.i(j), h.sub.i, ∀i ∈ {1, . . . , k}, ∀j ∈ {1, . . . , h.sub.i} $t_0=\underset{u=a_i\left(j\right)\in L^{\prime }}{\max }\left\{k+1-i-\sigma \left(u\right)\right\}$ for all i ∈ {1, . . . , k}do  for all j ∈ {1, . . . , h.sub.i}do set u = a.sub.i(j) T(u) = t.sub.0 + σ(u) − 1 − (k − i)  end for end for return T(u), ∀u ∈ L
6.1.4 Example

(104) In scheduling, the Gantt chart is a very useful tool for viewing, in time, the operations composing a job. This tool will enable us to graphically represent the progress of the work of each machine and visually show us the solution provided to our problem. In addition, we can see the link between the results obtained by the algorithm enabling the injection dates to be attained and the associated formula.

(105) Let us take the configuration of the system as follows (see FIG. 14): k=4 lanes comprising two or three loads. Each load is identified by a unique sequence number by means of the exit sequence σ=(1,2,3,4,5,6,7,8,9). This is an achievable sequence.

(106) In this simplified case, we can represent the Job Shop solution in a Gantt chart such that each row corresponds to one machine. The fact that each load passes by the machines consecutively is represented by the fact that each load sequence number appears in consecutive boxes from left to right in the table (see FIG. 15). In addition, the first appearance of each load indicates its date of injection given by the formula in locking the time scale to the instant 0 defined further above. It may be recalled that the date 0 corresponds to the instant of the first possible load injection. We can even place the date t.sub.0 according to its definition and find it by computation. It is recalled that t.sub.0 is the date at which the first load of the sequence (σ.sub.1) passes in front of the lane k=4, namely the number 1 when the operation of the job 1 is carried out by the machine M.sub.4.

(107) We find the desired sequence, without vacant space, on the machine M.sub.4 and the date of injection of each load is given by the reading of the box of the first appearance (from left to right) of the sequence number giving the identification of this load.

(108) 6.2 Solution for Lanes with any Unspecified Distribution

(109) Now that the simplified case has been seen, let us consider the general case of the collector that processes only the injection flows. The flows therefore no longer get injected consecutively at each time span of the collector but are distributed in any unspecified way. The distances between lanes are known. It is the travel time between the point of injection of the lane α.sub.i and the last lane α.sub.k that is of particular interest to us. It will be denoted Δ.sub.i=Δ.sub.i,k (as defined further above).

(110) 6.2.1 Computation of the Dates of Injection by Formula

(111) The algorithm 2 here below takes account of this notion of any unspecified time distance between lanes and thus responds to the general case of the collector dedicated to injection flows.

(112) Let us again consider the date 0 as being the date of the first possible injection. This time, a load u of the lane i injected at the date x arrives in front of the lane a.sub.k at the date x+Δ.sub.i. Thus, we obtain the earliest date at which the first load of the sequence passes in front of the lane α.sub.k by the formula

(113) $t_0=\underset{u=a_i\left(j\right)\in L^{\prime }}{\max }\left\{{\Delta }_i+1-\sigma \left(u\right)\right\}.$

(114) TABLE-US-00004 Algorithm 2: Computation of dates of injection without disturbing flow in a general case Require: σ, k, L′, a.sub.i(j), Δ.sub.i, h.sub.i, ∀i ∈ {1, . . . , k}, ∀j ∈ {1, . . . , h.sub.i} $t_0=\underset{u=a_i\left(j\right)\in L^{\prime }}{\max }\left\{{\Delta }_i+1-\sigma \left(u\right)\right\}$ for all i ∈ {1, . . . , k}do  for all j ∈ {1, . . . , h.sub.i}do set u = a.sub.i(j) T(u) = t.sub.0 + σ(u) − 1 − Δ.sub.i  end for end for return T(u), ∀u ∈ L

(115) FIG. 46 presents a flowchart of the method for merging k incoming flows into one outgoing flow, according to a first particular embodiment based on the algorithm 2. The method is executed at least once by the control system. A given execution is performed at an instant Tb and comprises the following steps: obtaining (step 461) a set L comprising n payloads distributed at the instant Tb on the k lanes and having to be injected into the collector to form an exit sequence σ, each of the n payloads being identified by a single sequence number within the exit sequence σ, each of the k lanes containing an ordered set, ordered in a rising order of sequence numbers, of h.sub.i payloads having to be injected one by one into the collector; computation (step 462) of a date t.sub.0 at which the first payload σ.sub.1 of the exit sequence σ passes in front of the lane a.sub.k; computation (step 463) of a date of injection on the collector for each of then payloads of the set L according to the following formula: T(u)=t.sub.0+σ(u)−1−Δ.sub.i, with: u=α.sub.i(j)∈L, a payload of the set L and coming from the j.sup.th position in the lane a.sub.i, i∈{1, . . . , k}, j∈{1, . . . h.sub.i}, σ(u) being the sequence number of the payload u in the exit sequence σ; commanding (step 464) the collector and the k lanes for an injection of the n payloads into the collector in keeping with the n injection dates T(u),∀u∈L.
6.2.2 Example

(116) Let us take an example similar to that of paragraph 6.1.4 in setting aside the lanes this time.

(117) Let us take the configuration of the system as follows (see FIG. 16): k=4 lanes comprising two or three loads. Each load is identified by a unique sequence number as a function of the exit sequence σ=(1,2,3,4,5,6,7,8,9). This is an achieveable sequence. We know the distance from each lane to the last one: Δ.sub.1=12, Δ.sub.2=7, Δ.sub.3=4 and Δ.sub.4=0.

(118) FIG. 17 gives the representation of the solution in the form of a Gantt chart. This time, two consecutive machines must be spaced out by as many rows as there are “time spans” between the two corresponding consecutive lanes. This is why the solution is given by a table with 13 (=Δ.sub.1+1) rows. By computation, we have

(119) $t_0=\underset{u\in \left\{1,2\right\}}{\max }\left\{{\Delta }_i+1-\sigma \left(u\right)\right\}=\max \left(7,11\right)=11,$
which we find actually by definition at the instant 11 on the graph.

(120) Here, for ease of comprehension, we give an example with inter-lane distances that are integer values but it is possible to take non-integer values in numbers of “time spans”.

(121) 6.3 Description of One Particular Embodiment

(122) 6.3.1 List of Elements to be Grouped Together

(123) Each injection flow (incoming flow) is represented by a lane containing a list of loads in a FIFO order. The number of lanes can vary from 2 to k, and the list of the lane i contains h.sub.i loads (h.sub.i can be zero). There are, in all, n loads to be merged into collector. Let us take for example (see FIG. 18): k=2, h.sub.1=h.sub.2=5 and n=10.

(124) In addition, staying with the general case, we shall take the resolutions of this general case with Δ.sub.1=1 and Δ.sub.2=0.

(125) 6.3.2 Building of a Default Sequence

(126) When the final sequence of the loads on the collector is of no importance, it is enough to define, in any unspecified way an achievable sequence that sets the order of the loads.

(127) We can design different ways of defining a “default” exit sequence: Remove, in alternation, one load from each lane, σ=(id.sub.5, id.sub.10, id.sub.4, id.sub.9, id.sub.3, id.sub.8, . . . , id.sub.6) Remove the loads as a function of their arrival in the injection flow, Remove the first load from each lane drawn randomly, etc.
6.3.3 a Sequence Given by a Disorder Minimizing Computation

(128) FIG. 19 illustrates an example of a sequence (σ′=(8,4,5,2,7,6,1,9,3,10)) resulting from a disorder minimizing computation. The numbers indicated are not sequence numbers within the final sequence but sequential order numbers relative to customer orders to be picked.

(129) This sequence σ′ can be seen as a given exit sequence for the algorithm which computes the injection dates. This sequence is obligatorily achievable and minimizes the disorder. We obtain a maximum throughput with a minimum disorder for the outgoing flow from the collector.

(130) Since it is always possible to assign a single sequence number from 1 to n to all the loads, corresponding to their position in the final sequence σ, we shall display the loads with these sequence numbers to identify them and characterize them entirely (cf. FIG. 20). FIGS. 19 and 20 are equivalent. The exit sequence σ=(1,2,3,4,5,6,7,8,9,10) truly makes it possible to see the rising order of loads on each injection flow (proof of feasibility of the sequence).

(131) Let us keep this configuration to continue the study of the example.

(132) 6.3.4 Building of t.sub.0

(133) In the present example, L′ brings together the loads numbered 1 and 5.

(134) We search for the maximum between {Δ.sub.2+1−σ(1), Δ.sub.1+1−σ(5)}, and we obtain t.sub.0=0.

(135) 6.3.5 Computation of the Injection Dates (by Formula)
T(1)=t.sub.0+σ(1)−1−Δ.sub.2=0
T(2)=t.sub.0+σ(2)−1−Δ.sub.2=1
T(3)=t.sub.0+σ(3)−1−Δ.sub.2=2
T(4)=t.sub.0+σ(4)−1−Δ.sub.2=3
T(5)=t.sub.0+σ(5)−1−Δ.sub.1=3
T(6)=t.sub.0+σ(6)−1−Δ.sub.1=4
T(7)=t.sub.0+σ(7)−1−Δ.sub.1=5
T(8)=t.sub.0+σ(8)−1−Δ.sub.1=6
T(9)=t.sub.0+σ(9)−1−Δ.sub.1=7
T(10)=t.sub.0+σ(10)−1−Δ.sub.2=9
6.3.6 Explanation of the Result in Images

(136) The dates of injection T(u) being given in the time unit (i.e. the time span of the collector), this amounts visually to seeing the collector move by one span at each time unit. If we view an image of the system at each time unit, each load u appears for the first time on the collector at the date T(u) (its injection date).

(137) The configuration of the collector at the instant 0 (cf. FIG. 2.sub.1) corresponds to the first real injection of a load, in this case the load 1 (because t.sub.1=0), even if it is not always the case. It must be noted that indeed the first load of the sequence is not obligatorily the first load to be injected into the collector.

(138) The load 2 must be injected at the instant 1, which means that it is on the collector after the movement by one step of the collector, as is shown by FIG. 22.

(139) The load 3 is injected at the instant 2, as is shown by FIG. 23.

(140) The loads 4 and 5 are injected at the date 3, as is shown by FIG. 24.

(141) And so on and so forth.

7. PROGRESS OF THE BATCHES

(142) The computation of the injection dates is done on a given state of the system. With the system developing in time, a first possibility consists in redoing this computation whenever a new load arrives at the system because it has does not yet have its definite injection date. However, instead of also regularly launching the computation algorithm, which is not advantageous for various reasons (in particular the consumption of computation resources), it is preferable to proceed by batches. This kind of batchwise operation is explained in this section.

(143) 7.1 Work Batch

(144) We would like a flow (outgoing flow) that is continuous and optimal on the collector throughout a workday. We have just seen how to define an optimal injection date (in order to arrive at our goal) on the loads present in the lanes at a given fixed instant. This goal now needs to be attained for all the loads arriving by the injection flows at any given instant. We propose to call the injection date computation algorithm at the instant needed to obtain a fluid and continuous filling of the collector. To this end, in this section, we define the way to fill the FIFO lists of each lane for the configuration of the system at a fixed instant. Then, we define what a batch is and then finally explain this succession of the processing of two batches without leaving any vacant space on the collector.

(145) 7.1.1 Filling the FIFO Lists of the Lanes

(146) In each lane, there is a list of loads with a unique sequence number for each load. These sequence numbers of the loads are obligatorily numbers that are rising by lane but not necessarily consecutive (due to the definition of the achievable sequence to be given).

(147) FIG. 25 illustrates an example of a FIFO list associated with three lanes.

(148) FIG. 26 illustrates the final achievable sequence, awaited on the collector.

(149) It may be recalled that each lane corresponds to an injection flow represented as a FIFO column attached to the collector, with its injection point defined by a black dot on the diagrams.

(150) The FIFO list of the loads taken into account in a lane for a fixed configuration of the system sets the order of the loads waiting at the injection point of this lane in accordance with the following conditions: the loads taken into account during the analysis are waiting at the injection point (represented by a black dot in the following figures) (FIG. 27: first load of the flow attached to the injection point and therefore forming part of the FIFO list; FIG. 28: first load of the flow not attached to the injection point and therefore not forming part of the FIFO list); the loads taken into account during the analysis are on “continuous” hold behind a first load forming part of the FIFO list (FIG. 29: second load on continuous hold behind a first load forming part of the FIFO list; FIG. 30: load on continuous hold behind a first load not forming part of the FIFO list).
7.1.2 Definition of Batches

(151) A work batch corresponds to the set of loads of the FIFO list of all the lanes (it is the set L of n loads). However, these loads correspond to the static photograph of our system at a given instant, complying with the rules of the preceding paragraph. The loads present in the system at this instant, which do not comply with the rules of filling of FIFO lists, will be assigned later to another batch. Once the loads of the batch are all allotted, the injection dates for this batch are computed. The injection of these loads is done as and when the time passes, in complying with the injection dates computed beforehand. The system develops in the course of time, without again calling the injection date computation algorithm, although new loads are eligible under the rules of filling of the FIFO lists or even if new loads appear in the system.

(152) All these injection dates are computed in order to succeed in placing each load of the batch at a reserved place on the conveyor, in complying with the order of the desired final sequence, while at the same time minimizing the vacant spaces. Let p designate the last place reserved for the last load of this batch given by the order of the sequence. After this place p, the collector is vacant. It is the time at which this last place p (which can be still vacant) passes below the first injection flow (first lane) that a new batch will be defined.

(153) The following batch will be built in the same way, but on a new static photo of the system at this fixed instant (with, as its first unoccupied location, the span of the collector attached to this last place p).

(154) It must be noted, in one particular implementation, that if a new batch is defined before the preceding batch has been entirely executed, the last loads of the exit sequence of the preceding batch can be considered for the new batch (following batch). In this case, if a load at the position i in the exit sequence is put back into the next batch, then so too are all the loads having positions greater than i). However, it is worthwhile to take up the loads again only if the desired final sequence has changed. In this case, the last place p considered will be the place of the last load not taken up in the next batch. For the loads that are taken up, the injection dates already defined in the preceding batch will be obsolete and replaced by dates of injection computed for the next batch.

(155) In the example illustrated in FIG. 31, the first batch will be composed of the loads: 1, 2, 3, 4, 5, 6, 7, 8, 9. The following batch could be: xx, yy or 9, xx, yy, . . . , or again 7, 8, 9, xx, yy, . . . (but not 8, xx, yy, nor 7, 9, xx, yy).

(156) 7.2 Dynamic Processing of the Batches

(157) The processing of each batch is done continuously and in series (batch1, batch2, etc.). The processing of a batch is a static computation of all the dates of injection of the loads composing this batch. The linking and the building of these batches provides a comprehensive solution to the problem of merging the incoming flows into one outgoing flow in the warehouses, which is a dynamic problem.

(158) 7.2.1 Computation of the Dates of Injection of a First Batch

(159) FIG. 32 illustrates an example of a first batch for an exit sequence σ=(1,2,3,4,5,6,7,8,9,10), with the loads 2, 6, 7 and 8 (for which the injection dates are denoted as Time 4, Time 8, Time 9 and Time 10 respectively) on the lane a.sub.3, the loads 1, 3 and 5 (for which the injection dates are denoted as Time 0, Time 2 and Time 4 respectively) on the lane a.sub.2 and the loads 4 and 9 (for which the injection dates are denoted as Time 0 and Time 5 respectively) on the lane a.sub.1.

(160) 7.2.2 Injection in Time of the Batch

(161) So long as the time span of the collector awaiting the highest sequence number (in this case n° 9, surrounded by a circle in FIGS. 32 and 33) has not arrived in front of the injection lane that is furthest upstream (i.e. the lane α.sub.1), no processing of the next batch is done. The processing of the loads of the first batch continues as and when time passes, these loads being injected at the injection date computed beforehand as can be seen in the upper part and the lower part of FIG. 33.

(162) 7.2.3 Formation of the Next Batch and Static Computation of the Future Dates of its Injection

(163) When the last marked span of the last load of the sequence of the first batch arrives before the lane α.sub.1, it is the signal for building the next batch. This batch is constituted by all the valid loads of each FIFO list of each lane according to the rules explained further above.

(164) FIG. 34 illustrates the formation of the next batch composed of six new loads that have appeared on the lanes and are numbered 1 to 6 (sequence numbers of the new exit sequence desired for the new batch).

(165) The algorithm for computing the static injection dates is applied to this new batch in considering the unoccupied part of the collector (to the right of the place reserved for the load numbered 9 of the previous batch). The injection dates are computed as a function of a time scale, the origin of which corresponds to the first injection of a load of the new batch.

(166) The configuration of the static system, taken at the “Time 5” as can be seen in FIG. 34, is given (as input data) to the algorithm. This configuration is defined as follows: k=3 lanes comprising six new loads that have appeared (belonging to the new batch). Each new load is identified by a unique sequence number as a function of the new exit sequence of this new batch: σ=(1,2,3,4,5,6). This is an achievable sequence. We know the time distances relative to the last lane: Δ.sub.1=6,Δ.sub.2=3 and Δ.sub.3=0.

(167) The date 0 is fixed by simultaneous injection of two new loads numbered 1 and 4 (into the lanes a.sub.2 and a.sub.1 respectively). Since this origin of time, the algorithm gives a date of injection T(u) for each of the six new loads u of this new batch.
L′={1,4} and t.sub.0=max{Δ.sub.1+1−σ(4),Δ.sub.2+1−σ(1)}=max{3,3}=3
T(1)=t.sub.0+σ(1)−1−Δ.sub.2=0
T(2)=t.sub.0+σ(2)−1−Δ.sub.2=1
T(3)=t.sub.0+σ(3)−1−Δ.sub.3=5
T(4)=t.sub.0+σ(4)−1−Δ.sub.1=0
T(5)=t.sub.0+σ(5)−1−Δ.sub.2=4
T(6)=t.sub.0+σ(6)−1−Δ.sub.1=2
7.2.4 Link Between the Injection Dates of a Batch and the Real Time that Elapses

(168) Each load of each batch will be given an injection date as a function of an origin of time that is well specified in relation to the static system. These injection dates must be placed at the right instant in the dynamic configuration to be consistent with the dynamic solution.

(169) A time scale common to all the batches makes it possible to link the injections of all the loads into the dynamic system. The time unit of this time scale is the “time span” of the collector, as defined further above. Let “Time” be the time derived from this common time scale, with the time 0 representing the starting date of the operations in the system.

(170) The injection dates given by the algorithm must be repositioned correctly in this common time scale. To this end, it is necessary to find the time-related correspondence, in the dynamic system, of the situation described at the date 0 of the batch. This means that it is necessary to obtain a correspondence between the date 0 of the batch and the Time of the common scale truly enabling the first injection of the load of this batch. It is then necessary to shift all the injection dates of this batch exactly this time.

(171) To this end, it is necessary to know the Time (also called “Tb”) at which the algorithm call has been launched and the (or at least one of the) first load or loads of the batch to be injected at the earliest on the collector, which shall be called σ.sub.*. The date 0 of the batch corresponds to the action of injecting this load σ.sub.*=α.sub.i(j), and it is done really by the dynamic system exactly σ(σ.sub.*)+Δ.sub.1,*time spans after the call.

(172) Returning to the present example, it is necessary to add to each injection date computed by the algorithm for the new batch (for all t u∈L,T(u)), the actual date (algorithm call date) in this case the Time 5 (i.e. Tb=5) plus the position of the first injected load of the new batch injected into the new sequence (in this case it is the load 1, hence we need to add σ(1)=1) plus the distance between the lane α.sub.1 and the one containing this first injected load (in this case Δ.sub.1,2=3). In noting that the load 4 of the new batch is also injected first into the collector (at the same time as the load 1 of the new batch), we could have chosen it and added σ(4)+Δ.sub.1,1=4; this really amounts to the same thing as adding σ(1)+Δ.sub.1,2=1+3=4.

(173) For the dynamic application, we carry out a linear transformation of the injection time as follows:
T(1)+5+4=0+5+4=9
T(2)+5+4=1+5+4=10
T(3)+5+4=5+5+4=14
T(4)+5+4=0+5+4=9
T(5)+5+4=4+5+4=13
T(6)+5+4=2+5+4=11

(174) In this case, the earliest date of the first load of the new sequence passing in front of α.sub.k will be exactly Tb+σ(u.sub.*)+Δ.sub.1−Δ.sub.i*+t.sub.0, with u.sub.*=α.sub.i*(1) the first load of the new sequence to be injected into the collector (being not necessarily the first load of the new sequence). Now, we know that t.sub.0 is a maximum attained exactly by this load u.sub.*, giving

(175) $t_0=\underset{u=a_i\left(j\right)\in L^{\prime }}{\max }\left\{{\Delta }_i+1-\sigma \left(u\right)\right\}={\Delta }_{i_{*}}+1-\sigma \left(u_{*}\right).$
Thus, we know that the first load of the new sequence will pass in front of α.sub.k at Tb+σ(u.sub.*)+Δ.sub.1−Δ.sub.i*+t.sub.0=Tb+σ(u.sub.*)+Δ.sub.1−Δ.sub.i*+Δ.sub.i*+1−σ(u*)=Tb+1+Δ.sub.1, in the common time scale.

(176) An equivalent way of giving the injection times in the common time scale is, by definition, to give the algorithm t.sub.0=Tb+1+Δ.sub.1, when we obtain knowledge of the system exactly at an instant Tb=(u.sub.last)−Δ.sub.1+Δ.sub.i.sub.last, with u.sub.last=α.sub.i.sub.last(j.sup.last) being the last load of the sequence of the preceding instant.

(177) In the above example, the instant Tb=5 corresponds exactly to the condition and we could therefore have called the algorithm with t.sub.0=Tb+1+Δ.sub.1=5+1+6=12 (rather than 3) and we could have directly had the injection times expressed in the common time scale.

(178) Ultimately, our system can be represented as is shown by FIG. 35. In the common time scale: the injection times of the loads 6, 7 and 8 of the preceding batch are denoted as Time 8, Time 9 and Time 10 respectively; and the injection times of the loads 1, 2, 3, 4, 5 and 6 of the new batch are denoted as Time 9, Time 10, Time 14, Time 9, Time 13 and Time 11 respectively.

8. DETERMINING DATES OF INJECTION OF THE LOADS FOR A COLLECTOR PROCESSING ONE OR MORE DISTURBING FLOWS

(179) We shall assume that there now exists at least one disturbing flow (of disturbing loads) already present in the collector. These disturbing loads are part of none of the injection flows (incoming flows). Therefore, they are not ordered in the desired exit sequence of the injection flows. These disturbing loads disturb the introduction of the payloads contained in the injection flows because they occupy places on the collector. It is necessary to take account of these obstructions which block the injection of the payloads from time to time. In addition, if these disturbing loads disappear from the collector between the injection lanes, that can create vacant spaces in the exit flow from the collector. Our goal is always to comply with an exit sequence in maximizing the throughput of the collector and thus minimizing these vacant spaces.

(180) To achieve this goal, we shall use non-valid lists of dates to be exploited with the modelling of the Job Shop seen further above.

(181) The following table gives new notations needed for the part that follows (summary of notations for the disturbing flows).

(182) The following table gives the new notations for the disturbing flows.

(183) TABLE-US-00005 TABLE 3 F Disturbing flow n′ Total number of disturbing loads l (p) or l.sub.p, Number of the last lane in front of which p ∈ F the disturbing load p passes g (p) or g.sub.p, Number of the first lane in front of which p ∈ F the disturbing load p passes U.sub.i, List of prohibited dates for an injection of i ∈ {1, . . . , k} a payload injection by the lane a.sub.i σ′ Ordered list of disturbing loads σ′.sub.p The p.sup.th disturbing load of the disturbing flow σ′ (u, v) Duration between the disturbing load u and the disturbing load v in the disturbing flow, in number of “spans” at a given instant t.sub.r Date of arrival of the first disturbing load of the disturbing flow in front of the lane a.sub.1, in the particular case where this load passes effectively in front of this lane (link with δ.sub.p) δ.sub.p Distance between the disturbing load p and the last lane a.sub.k at the date 0 start.sub.p Date at which the disturbing load p is injected “fictitiously” before the lane a.sub.1. (Fictitiously if g.sub.p >1 because in this case the load p will not pass before the lane a.sub.1)
8.1 Modelling of the System with a Non-Controlled Disturbing Flow

(184) The disturbing loads of the disturbing flow block the injection of a payload into the collector when they pass in front of the injection lanes. It is therefore necessary to compute the non-valid dates not valid for an injection of a payload for each lane. We now seek to compute the new dates of injection of the payloads in taking account of the non-controlled disturbing flow (over which, by definition, we assume that we have no control whatsoever). We note that there can henceforth be unoccupied spaces in the exit flow, and we shall nevertheless seek the optimal minimizing of these unoccupied spaces.

(185) 8.1.1 Creation of the List of Non-Valid Dates

(186) We can take account of a non-controlled disturbing flow, comprising disturbing loads that remain on the collector, thus passing in front of all the lanes and forming part of the final flow of the collector (mixed with the payloads of the injection flows). We can also take account of a non-controlled disturbing flow comprising disturbing loads present on the collector but disappearing between the injection lanes, thus creating unoccupied locations in front of certain lanes but not all of them. We can also take account of the case of a mixture of these types of non-controlled disturbing flows, as well as disturbing loads arriving and getting distributed between the lanes. Everything can be envisaged, and we can even take account of an unspecified obstruction on one or more spans of the collector (an obstruction being not obligatorily a disturbing load but being capable also of being a place of the collector that is damaged, reserved, etc.).

(187) In any case, the idea is to take account of the disturbing loads and/or other obstructions to compute the dates not valid for an injection of a payload of a lane. The non-valid dates are obtained by computing the instants of passage of each obstruction (i.e. each disturbing load of the disturbing flow or any other obstruction) in front of this injection lane. Let U.sub.i denote the set of non-valid dates where the lane a.sub.i cannot inject a payload because of the disturbing loads and/or any unspecified obstructions of the time spans of the collector.

(188) 8.1.2 Idea of the Solution for Lanes that are Consecutively Well Distributed

(189) This Job Shop scheduling problem, with a list of non-valid dates for each machine, can be resolved by following almost the same steps as those of the paragraph 6.2.1.

(190) Here is the approach in the particular case of lanes well distributed by conveyor spans. To begin with, assuming that the first load of the sequence comes from the lane α.sub.i, the operations {o.sub.1,i, o.sub.1,{i+1}, . . . , o.sub.1,k} associated with this job begin at the dates t, t+1, . . . t+k−i starting from a date t which makes it possible to have dates t, t+1, . . . , t+k−i respectively on each machine {M.sub.1, M.sub.{i+1}, . . . , M.sub.k} that are free (i.e. without obstruction). Then, the operations of the job corresponding to the next load of the sequence will be scheduled first of all by executing the operation to be processed on the machine M.sub.k. This operation o.sub.u,k will be scheduled just after (without idle time) the preceding operation programmed on M.sub.k. In assuming that this operation starts at a new instant t (different from the instant t defined further above for the computations related to the first load) the operation on the machine M.sub.{k-1} (if it exists) is scheduled at the instant t−1, and so on and so forth, until all the operations are programmed. If an operation cannot be carried out at these indicated dates because of an obstruction, we shall start the scheduling of the (entire) job in shifting the instant t of execution of the operation to be processed on the machine M.sub.k of a time unit (i.e. a location, span or slot). This procedure is applied iteratively to each of the following jobs of the given sequence.

(191) The real dates of injection of the payloads on the collector are deduced directly from the start of the first operation of each job. The time unit used is the one defined further above. NOTE: This method does not always give a flow without vacant spaces. The disturbing flow and/or the obstructions are non-controlled and we therefore maximize the throughput without ensuring maximality.
8.1.3 Idea of the Solution with a Non-Controlled Disturbing Flow in the General Case

(192) Based on the above paragraph, this is the approach followed in the general case to compute the real dates of injection during the merger of several flows comprising incoming flows (injection flows) and (at least) one non-controlled disturbing flow. Let us consider that we can start by scheduling the jobs from the instant 0 onwards. It must not be forgotten that it is necessary to follow a particular sequential order in the execution of the operations of the machine M.sub.k while at the same time minimizing the idle time of this machine. To begin with, let t.sub.0(≥0) denote the earliest date at which the job associated with the first load of the sequence can be assigned to the machine M.sub.k, if it did not have a disturbing flow. Let the loads be scheduled in the order given by the desired sequence without taking account of the disturbing flow, and then the date of injection is modified in following this order. Indeed, it can be noted that the scheduling of a load σ.sub.c has an impact solely on the loads σ.sub.c′ such that c′>c. For the job associated with the load u, let us first schedule its operation to be processed on the machine M.sub.k. This operation o.sub.u,k will be scheduled at t.sub.0 if it is the load σ.sub.1, else just after (without idle time) the preceding operation programmed on M.sub.k. Assuming that this operation on M.sub.k starts at the instant t, the operation on the machine M.sub.{k-1} (if it exists) is scheduled at the instant t−Δ.sub.k-1. Then the operation on the machine M.sub.{k-2} (if it exists) is scheduled at the instant t−Δ.sub.k-2, and so on and so forth until all the operations are programmed. If an operation cannot be carried out at these dates indicated during an obstruction, we shall restart the scheduling of the (entire) job in shifting the instant t of execution of the operation to be processed on the machine M.sub.k by a time unit (i.e. by one location, span or slot). This procedure is applied iteratively on each of the following jobs of the given sequence. It is necessary, if need be, to shift the date 0 and the date t.sub.0 to make them correspond to their definition. Since the shifting of the date 0 must correspond to the first possible injection of loads on the collector, it has repercussions on all the schedules (injection dates) which will be shifted in their turn.

(193) The real dates of injection of the payloads into the collector are deduced directly from the start of the first operation of each job. The time unit used is the one defined further above.

(194) NOTE: The presence of non-controlled disturbing flows does not always enable a flow without vacant space on the collector. With this method, we maximize the throughput of the collector without guarantee of maximality.

(195) 8.1.4 Algorithm in the General Case

(196) The algorithm 3 here below computes the dates of injection of the payloads in taking account of the disturbing flow that takes the form of the dates of prohibition of injection by lane.

(197) The date 0 corresponds to the first load injected into the collector at the earliest. The date t.sub.0 is always the date at which the first load of the sequence passes in front of the lane a.sub.k. The general formula for

(198) 0$i=1\mathrm{.Math.}k\text{:}{t}_0=\underset{u=a_i\left(j\right)\in L^{\prime },j\le h_i}{\max }\left\{{\Delta }_i+1-\sigma \left(u\right)\right\}$
remains valid if there is no conflict with the disturbing flow during the injection of the first load of the sequence.

(199) The algorithm 3 gives the date of injection of each load in taking account of the disturbing flow and in correcting the date t.sub.0 if necessary. The disturbing flow is taken into account by preliminary computation of the set U.sub.i, i=1 . . . k giving the dates of passage of each disturbing load of this disturbing flow in front of the lane α.sub.i. These dates are therefore prohibited dates of injection (also called dates not valid for a payload injection).

(200) In this algorithm, we use the simplified notation “u=σ.sub.c=α.sub.i(j)∈L” to define a load u corresponding to the c.sup.th load of the sequence σ, also defined by its position j in the lane α.sub.i.

(201) TABLE-US-00006 Algorithm 3: Computation of dates of injection with non-controlled disturbing flows Require: σ, Δ.sub.i, U.sub.i, i ∈ {1, . . . , k}//Give the values U.sub.i, computation to be made case by case $t_0=\underset{u=a_i\left(j\right)\in L^{\prime }}{\max }\left\{{\Delta }_i+1-\sigma \left(u\right)\right\}\text{/}\text{/}\mathrm{Theoretical}\mathrm{computation}\mathrm{of}{t}_0$ last = t.sub.0//Theoretical date of passage of σ.sub.1 in front of the lane a.sub.k for c = 1 to n do set u = a.sub.i(j) = σ.sub.c  do {//Scheduling of the load σ.sub.c in avoiding all obstructions  check = true   for all z = k to z = i,z − − do    if(last − Δ.sub.z ∈ U.sub.z) then check = false;   end for   if(check = false) then {     last = last + 1;     if(c = 1) then t.sub.0 = t.sub.0 + 1;//t.sub.0 is modified if disturbance   }end if  }while (check = false);  T(u) = last − Δ.sub.i//Final date of injection for the load σ.sub.c  last = last + 1//Theoretical date of passage of σ.sub.c+1 in front of the lane a.sub.k end for //Possible shifting of the date 0 sett.sub.min to min{T(u), ∀u ∈ L} if(t.sub.min! = 0) then      t.sub.0 = t.sub.0 − t.sub.min  for u ∈ L do      T(u) = T(u) − t.sub.min  end for end return t.sub.0, T(u), ∀u ∈ L

(202) FIG. 36 is a graph of the algorithm 3 here above.

(203) FIG. 47 presents a flowchart of a method for merging k incoming flows into one outgoing flow according to a second particular embodiment based on the algorithm 3 (illustrated in FIG. 36). The method is executed at least once by the control system. A given execution is performed at an instant Tb and comprises the following steps: obtaining (step 471) a set L comprising n payloads distributed at the instant Tb on the k lanes and having to be injected into the collector to form an exit sequence σ, each of the n payloads being identified by a single sequence number within the exit sequence σ, each of the k lanes containing an ordered set, according to a rising order of sequence numbers, of h.sub.i payloads having to be injected one by one into the collector; for each lane a.sub.i, i∈{1, . . . , k}, obtaining (step 472) a set U.sub.i of dates not valid for an injection of one of the payloads of the lane a.sub.i on the collector because of a non-controlled disturbing load or another obstruction of a time span of the collector; in not taking account of the sets U.sub.1, i∈{1, . . . , k}, computing (step 473) a date t.sub.0 at which the first payload σ.sub.1 of the exit sequence σ passes in front of the lane a.sub.k; for the first payload σ.sub.1 of the exit sequence σ, in assuming that the first payload σ.sub.1 comes from the lane a.sub.i (step 474): a) initializing t with t.sub.0; b) if none of the dates t, t−Δ.sub.k-1, t−Δ.sub.k-2, . . . , t−Δ.sub.i belongs respectively to the sets U.sub.k, U.sub.k-1, U.sub.k-2, . . . , U.sub.i, computing a date of injection of the first payload σ.sub.1 into the collector with the following formula: T(u)=t−Δ.sub.i, with u=σ.sub.1=α.sub.i(j); c) if one of the dates t, t−Δ.sub.k-1, t−Δ.sub.k-2, . . . , t−Δ.sub.i belongs respectively to one of the sets U.sub.k, U.sub.k-1, U.sub.k-2, . . . , U.sub.i, incrementing t by one unit and reiterating the steps b) and c) with the new value of t; for each following payload a of the exit sequence σ, c∈{2, . . . , n}, in assuming that the following σ.sub.c comes from the lane a.sub.i (step 475): a′) incrementing t by one unit, with t being used to compute the date of injection of the preceding payload σ.sub.c-1; b′) if none of the dates t, t−Δ.sub.k-1, t−Δ.sub.k-2, . . . , t−Δ.sub.i belongs respectively to the sets U.sub.k, U.sub.k-1, U.sub.k-2, . . . , U.sub.i, computing a date of injection of the following payload σ.sub.c on the collector with the following formula: T(u)=t−Δ.sub.i, with u=σ.sub.c=α.sub.i(i); c′) if one of the dates t, t−Δ.sub.k-1, t−Δ.sub.k-2, . . . , t−Δ.sub.i belongs respectively to one of the sets U.sub.k, U.sub.k-1, U.sub.k-2, . . . , U.sub.i, incrementing t by one unit and reiterating the steps b′) and c′) with the new value of t; computing (476) de t.sub.min according to the following formula: t.sub.min=min{T(u), ∀u∈L}; if t.sub.min>0, modification (477) of the n dates of injection according to the following formula: T(u)=T(u)−t.sub.min,∀u∈L; commanding (step 478) the collector and of the k lanes for an injection of the n payloads on the collector in compliance with the n injection dates T(u),∀u∈L
8.1.5 Description of One Particular Embodiment

(204) Let us look at a non-controlled disturbing flow already present on the collector, not taken into account by the desired sequence finally because the disturbing loads will all disappear before the last injection lane. This is the case for example in the context of FIG. 50 (PTS Intel's GTP automated system) with the management of the injection into the collector of the payloads coming from the automated system (PTS) but also that of the return of loads that arrive at this collector in order to return into the automated system (PTS) (see paragraph 2.2 in the context of this possible application).

(205) FIG. 37 illustrates this configuration with the disturbing loads (marked by a cross) of the return flow (constituting the non-controlled disturbing flow) that returns to the automated system (PTS). According to this configuration, we make two observations: no disturbing load of the return flow (and therefore of the disturbing flow) will pass in front of the last lane; and the disturbing loads leaving the collector (towards the automated system (PTS)) before the lane α.sub.1 pose no problem and will therefore not be studied. All the remaining loads will pass necessarily in front of the lane α.sub.1.
8.1.5.1 Computation of the Lists of Non-Valid Dates Induced by the Flow of Disturbing Loads

(206) Let us take a flow F of n′ disturbing loads already present in the collector and to exit the collector between the injection lanes. This disturbing flow, called a return flow, corresponds to the loads that have to return to stock in the automated system (PTS). These disturbing loads must indeed pass in front of one or more injection lanes. For each disturbing load p of this return flow (disturbing flow), g.sub.p (and l.sub.p respectively) denote the number of the first lane (and the last lane respectively) in front of which the disturbing load p passes. We shall see two methods enabling the computation of the non-valid injection dates (U.sub.i), induced by the return flow as a function of the known data.

(207) In this particular embodiment, g.sub.p=1 and l.sub.p<k, for every load p of the return flow specific to the automated system (PTS). We shall give however the general solution with the notations g.sub.p and l.sub.p. Either, in the above-mentioned specific case of a return flow, we know the date of arrival (denoted t.sub.r) of the first disturbing load of the return flow (disturbing flow) in front of the lane numbered α.sub.1 (or again the machine M.sub.1). We also know the order in which the disturbing loads of this return flow are distributed on the collector (let us call this sequence σ′) and the duration between each disturbing load and another disturbing load of this disturbing flow. Let σ′.sub.p give the p.sup.th disturbing load of the return flow and σ′(u,v) give the duration between the disturbing load u and the disturbing load v in the disturbing flow in number of “spans”.

(208) Then, the instants t.sub.r, t.sub.r+σ′(σ′.sub.1, σ′.sub.2), . . . , t.sub.r+σ′(σ′.sub.1, σ′.sub.n′) are congested for the machine M.sub.1 and form U.sub.1. For the machine M.sub.i, i=2, . . . , k, the congested dates are the U.sub.i={t.sub.r+σ′(σ′.sub.1,σ′.sub.j)+Δ.sub.i,1 if l(σ′.sub.j)≥i, ∀j=1, . . . , n′}. Another way of seeing things would be to copy the “congested” (or non-valid) dates U.sub.i of the machine M.sub.i of the disturbing loads u which are l(u)≥i+1 and add to all these instants Δ.sub.i,i+1 to obtain the list of congested dates U.sub.i+1 for the machine M.sub.i+1. Or, in a more general framework, we know the distance of each disturbing load p relative to the last lane α.sub.k of the date 0 which we shall denote δ.sub.p. With these data, we compute the values U.sub.i as follows:

(209) TABLE-US-00007   For all i ∈ {1, . . . , k} do U.sub.i = Ø; For all p ∈ F do  For all i ∈ {g.sub.p, . . . , l.sub.p} do   U.sub.i = U.sub.i ∪ {δ.sub.p − Δ.sub.i};  end for end for return U.sub.i, ∀i = 1 . . . k
8.1.5.2 Examples

(210) Let us return to the configuration of the example of paragraph 6.2.2.

(211) Let us take k=4 lanes comprising two or three payloads. Each payload is identified by a unique sequence number as a function of the exit sequence σ=(1,2,3,4,5,6,7,8,9). This is an achievable sequence. We know the distances from each lane to the last one: Δ.sub.1=12, Δ.sub.2=7, Δ.sub.3=4 and Δ.sub.4=0.

(212) As illustrated in FIG. 38, it is assumed that this time there are three time spans of the collector obstructed by disturbing loads A, B and C. We know that these disturbing loads pass in front of certain lanes and disappear from the collector thereafter. The loads A and B pass in front of the lanes a.sub.1 and a.sub.2. Finally, the load C passes in front of all the lanes a.sub.1, a.sub.2 and a.sub.3. Thus, we have l.sub.A=2, l.sub.B=2 and l.sub.c=3, as well as g.sub.A=g.sub.B=g.sub.c=1.

(213) We show a state of the system at the date 0, when the first payload of the batch will be injected into the first unoccupied place of the collector. In the diagram, an unoccupied position of the collector is vacant, and the crosses indicate the positions taken by the payloads of the preceding batch and the letters denote the disturbing loads of the disturbing flow. The position of the disturbing flow at the date 0 enables us to deduce the following pieces of information: δ.sub.A=13, δ.sub.B=14 and δ.sub.C=18.

(214) The disturbing load B obliges the payload 4 to shift in time by one position and will leave a vacant space in the final flow of the collector. Then, the disturbing flow C obliges the payload 7 to shift by yet another position, leaving a vacant space later in the final flow of the collector.

(215) FIG. 39 is a Gantt chart illustrating the solution proposed in this case. We can see that if the disturbing flow were to be controlled (and not non-controlled), the first vacant space could be filled by the lane α.sub.3 or α.sub.4 and the second vacant space solely by the lane α.sub.4. Thus, vacant spaces would be avoided, and the throughput of the final flow (outgoing flow) from the collector would be increased.

(216) 8.2 Modelling of the System with a Controlled Disturbing Flow

(217) We have seen that when the disturbing flow was non-controlled, it gave rise to vacant spaces in the final flow of the collector. It is therefore worthwhile to control the disturbing flow to avoid these vacant spaces. We could thus prioritize the loads of the injection flows over the loads of the disturbing flows and be able to make the disturbing flows pass into the unoccupied or free spaces left by the injection of the different lanes.

(218) 8.2.1 Formulation of the Problem

(219) We now assume that we can control the disturbing flow. This amounts to achieving mastery over the injection of the disturbing loads of a disturbing flow, and we must decide the date (denoted as start.sub.p) at which the disturbing load p is injected before the lane a.sub.1 so as not to disturb the outgoing flow (outgoing flow formed by the merger of the injection flows), i.e. in not creating any vacant space in the exit flow.

(220) 8.2.2 Idea of the Solution Algorithm

(221) We shall first compute the dates of injection of the payloads coming from the lanes, as if they were no disturbing flows (cf. Section 6). It is these injection dates that we shall give as the dates unavailable (U.sub.i) for a disturbing load passing in front of a lane (α.sub.i). Then, taking account of the list of non-valid dates, we shall compute the injection of the loads of the disturbing flow. To this end, in the order of arrival of the disturbing loads, we schedule each of their passages in front of the lanes at the earliest time, i.e. as soon as these dates of passage into the respective machines fall on free dates.

(222) 8.2.3 General Algorithm

(223) The algorithm 4 described in detail here below gives the injection dates of the payloads as well as the control of the disturbing flow. The loads to be injected constitute the final flow of the collector. Their injection is decided without taking account of the disturbing flow. Then, we shall determine when to let through the loads of the disturbing flow in considering this time that the injected payloads play the same role as the non-controlled flow in the algorithm 3 here above. Thus, we can use the same technique as here above with the computation of the sets

(224) V.sub.i, i=1 . . . k giving the dates of passage of each payload of the injected flow in front of the lane α.sub.t. These dates are therefore injection dates prohibited for the disturbing loads.

(225) It may be recalled that σ′.sub.p,p′ gives the distance between the disturbing loads p and p′ at the date 0 and t.sub.r gives the date, without waiting, of arrival of the 1.sup.st load of the disturbing flow in front of the lane number a.sub.1.

(226) In this algorithm, we use the simplified notation “u=σ.sub.c=α.sub.i(j)∈L” to define a load u corresponding to the c.sup.th load of the sequence σ, also defined by its position j in the lane α.sub.i.

(227) TABLE-US-00008 Algorithm 4: Computation of dates of injection of the loads of the controlled disturbing flows Require: σ, Δ.sub.i, Δ.sub.1i, i ∈ {1, . . . , k} $t_0=\underset{u=a_i\left(j\right)\in L^{\prime }}{\max }\left\{{\Delta }_i+1-\sigma \left(u\right)\right\}\text{/}\text{/}\mathrm{Theoretical}\mathrm{computation}\mathrm{of}{t}_0$ for all i ∈ {1, . . . , k} do  for all j ∈ {1, . . . , h.sub.i} do set u = a.sub.i(j) T(u) = t.sub.0 + σ(u) − 1 − Δ.sub.i    for all z ∈ {i, . . . , k}do      V.sub.z = V.sub.z ∪ {T(u) + Δ.sub.i − Δ.sub.z}    end for   end for end for set t = δ.sub.1 − Δ.sub.1//Arrival of the first disturbing load in front of a.sub.1 for all p = 1 to f do//Load identified by their place in σ.sub.f    do {    check = true     for i = g.sub.p to l.sub.p do      if(t + Δ.sub.1 − Δ.sub.i ∈ V.sub.i) then check = false; t + +; break;     end for    }while (check = false);    start.sub.p = t    t = Max (t + 1, δ.sub.p+1 − Δ.sub.1)//Possible wait for arrival of p + 1 end for return T(u), start.sub.p, ∀u ∈ L, ∀p ∈ F

(228) FIG. 40 is a diagram of the algorithm 4 here above.

(229) FIG. 48 presents a flowchart of a method for merging k incoming flows into one outgoing flow, according to a third particular embodiment based on the algorithm 4 (illustrated in FIG. 40). The method is executed at least once by the driving system. A given execution is performed at an instant Tb and comprises the following steps: for each payload u=α.sub.i(j)∈L coming from a lane a.sub.i, computing (step 481) the dates of passage of the payload in front of the lanes a.sub.i to a.sub.k, the date of injection T(u) of the payload into the collector being known; for each lane a.sub.i, i∈{1, . . . , k}, obtaining (step 482) a set V.sub.i, containing each date of passage of one of the payloads in front of the lane a.sub.i; for each controlled disturbing load p of a disturbing flow controlled by means of a control means situated along the collector and having a lane a.sub.g(p) in the sense of movement of the collector, with g(p)∈{1, . . . , k}, a.sub.g(p) being also the first lane, in the sense of movement of the collector, before which the controlled disturbing load passes (step 483): a) initializing t with the date δ.sub.1−Δ.sub.1, with δ.sub.1 representing the possible date of arrival should the first controlled disturbing load not be put on hold before the lane a.sub.k; b) computing the dates t+Δ.sub.1,g(p), t+Δ.sub.1,g(p)+1, . . . , t+Δ.sub.1,l(p) of passage of the controlled disturbing load in front of the lanes a.sub.g(p) to a.sub.l(p), with a.sub.l(p) being the last lane in the sense of movement of the collector, before which the controlled disturbing load passes; c) if none of the dates t+Δ.sub.1,g(p), t+Δ.sub.1,g(p)+1, . . . , t+Δ.sub.1,l(p) belongs respectively to the sets V.sub.g(p), V.sub.g(p)+1, . . . , V.sub.l(p), computing a fictitious date of passage start.sub.p of the controlled disturbing load p in front of the lane a.sub.1, with the following formula: start=t; d) if one of the dates t+Δ.sub.1,g(p), t+Δ.sub.1,g(p)+1, . . . , t+Δ.sub.1,l(p) belongs respectively to one of the sets V.sub.g(p), V.sub.g(p)+1, . . . , V.sub.l(p), incrementing t by one unit and reiterating the steps b), c) and d) with the new value of t; commanding (step 484) the control means for an injection on the date start.sub.p+Δ.sub.1,g(p) of each controlled disturbing load p before the lane a.sub.g(p).
8.2.4 Description of One Particular Embodiment

(230) Let us take the example common to all the previous cases to be able to compare the final solutions. Let k=4 lanes comprising two or three loads. Each load is identified by a single sequence number as a function of the exit sequence σ=(1,2,3,4,5,6,7,8,9). This is an achievable sequence. We know the distances from each lane to the last one: Δ.sub.1=12, . . . , Δ.sub.2=7, Δ.sub.3=4 and Δ.sub.4=0. The disturbing flow is composed of the loads A, B, C such that l.sub.A=2, l.sub.B=2, l.sub.C=3, g.sub.A=g.sub.B=g.sub.C=1,δ.sub.A=13, δ.sub.B=14 and δ.sub.C=18.

(231) This time, the disturbing flow is controllable. We can see in FIG. 41 the control point of this disturbing flow, represented by a vertical rectangle just before the lane a.sub.1.

(232) FIG. 42 is an illustration, in the form of a Gantt chart, of the solution without taking account of the disturbing flow (“pure injection solution”).

(233) The solution of the algorithm taking account of the disturbing flow amounts to sliding the disturbing loads into the grey boxes, left empty by the pure injection solution. The load A is allowed to pass as soon as it arrives at the control point of the disturbing flow while the load B is retained for one time unit. This wait enables the disturbing load B to be made to pass into the free spaces of the injections, just before the load 5 is injected. This is also the case with the load C and the load 8 of the sequence. FIG. 43 is an illustration, in the form of a Gantt chart, of the solution proposed to control the disturbing flow (i.e. by choosing the placing of the disturbing loads). The loads B and C no longer form a vacant space in the final flow of the collector. They have been interposed at strategic places so that the vacant space that they leave initially is then filled by an injection of a time-compatible load. Through the control of the disturbing flow, we have shown that the vacant spaces on the collector are avoidable.

(234) 8.3 Modelling the System with a Non-Controlled Disturbing Flow and a Controlled Disturbing Flow

(235) Should there be at the same time at least one non-controlled disturbing flow and at least one controlled disturbing flow, we proceed thus.

(236) We differentiate the non-controlled disturbing loads from the controlled disturbing loads as follows: Let S be the set of s non-controlled disturbing loads to be allowed obligatorily to pass without control into the injection zone of the lanes of the collector, each being identified by a unique sequence number corresponding to its position in the order of arrival (denoted as σ′.sub.s).

(237) Let δ′.sub.p designate the distance between each disturbing load p∈S and the last lane α.sub.k at the date Tb and let g′.sub.p and l′.sub.p respectively designate the number of the first and last lane in front of which the disturbing load p must pass.

(238) Finally, the sets U.sub.i, i=1 . . . k, give the dates of unavailability of passage in front of the lane α.sub.i for the payloads. Let F designate the set of f disturbing loads to be allowed to pass under control into the injection zone of the lanes of the collector, each being identified by a unique sequence number corresponding to its position in the order of arrival (denoted as σ.sub.f).

(239) Let δ.sub.p designate the distance from each disturbing load p∈F to the last lane α.sub.k at the date Tb and let g.sub.p and l.sub.p respectively denote the number of the first and last lane in front of which the disturbing load p must pass.

(240) Finally, the sets V.sub.i, i=1 . . . k, give the dates of unavailability of passage in front of the lane α.sub.i for these controlled disturbing loads.

(241) The algorithm 5 provides a detailed view here below of the dates of injection of the payloads as well as the control of the disturbing flow, in taking account of the non-controlled disturbing flow.

(242) TABLE-US-00009 Algorithm 5: Computation of the injection dates of the payloads and the loads of the controlled disturbing flow with the non-controlled disturbing flow being taken into account: Require: F, S, σ, Δ.sub.i, Δ.sub.1i, a.sub.i(j), ∀i ∈ {1, . . . , k}, ∀j ∈ {1, . . . , h.sub.i} $t_0=\underset{u=a_i\left(j\right)\in L^{\prime }}{\max }\left\{{\Delta }_i+1-\sigma \left(u\right)\right\}\text{/}\text{/}\mathrm{Theoretical}\mathrm{computation}\mathrm{of}{t}_0$ //Compute values U.sub.i:  for all p = 1 to s do    for all i ∈ {g.sub.p′, . . . , l.sub.p′} do    U.sub.i = U.sub.i ∪ {δ.sub.p′ − Δ.sub.i}//Load p in front of a.sub.i    end for  end for //Compute values T(u)  last = t.sub.0//Theoretical date of the passage of σ.sub.1 in front of the lane a.sub.k  for u = 1 to n do  set u = a.sub.i(j)  do {//Scheduling of the u.sup.th load of σ   check = true   for all z = k à z = i, z − − do     if (last − Δ.sub.z ∈ U.sub.z) then check = false;   end for   if (check = false) then {      last = last + 1;      if (u = 1) then t.sub.0 = t.sub.0 + 1;   }end if  }while (check = false);  T(u) = last − Δ.sub.i//Final date of injection for the load u    last = last + 1//Following place before a.sub.k  end for  //Possible shifting of the date 0  sett.sub.min to min {T(u), ∀u ∈ L}  if (t.sub.min! = 0) then        t.sub.0 = t.sub.0 − t.sub.min    for u ∈ L do        T(u) = T(u) − t.sub.min    end for  endif //compute values V.sub.z:  for u = 1 to n do   set u = a.sub.i(j)   for all z ∈ {i, . . . , k} do        V.sub.z = V.sub.z ∪ {T(u) + Δ.sub.i − Δ.sub.z}        end for  end for  for all z ∈ {1, . . . , k} do        V.sub.z = V.sub.z ∪ U.sub.z  end for //compute values start.sub.p:  set t = δ.sub.1 − Δ.sub.1//Arrival of the first disturbing load in front of a.sub.1  for all p = 1 to f do//Load identified by its place in σ.sub.f     do {     check = true      for i = g.sub.p to l.sub.p do       if(t + Δ.sub.1 − Δ.sub.i ∈ V.sub.i) then check = false; t + +; break;      end for     }while (check = false);     start.sub.p = t     t = Max (t + 1, δ.sub.p+1 − Δ.sub.1)//Possible wait for the arrival of p + 1  end for  return t.sub.0, T(u), ∀u ∈ L, start.sub.p, ∀p ∈ F

(243) FIG. 45 is a diagram of the algorithm 5 here above.

(244) FIG. 49 is a flowchart of a method for merging k incoming flows into one outgoing flow, according to a fourth particular embodiment based on the algorithm 5 (illustrated in FIG. 45). The method is executed at least once by the control system. A given execution is performed at an instant Tb and comprises the following steps: for each payload u=α.sub.i(j)∈L coming from a lane a.sub.i, computing (step 491) the dates of passage of the payload in front of the lanes a.sub.i to a.sub.k, the injection date T(u) of the payload into the collector being known; for each lane a.sub.i, i∈{1, . . . , k}, obtaining (step 492) a set V.sub.i, containing on the one hand each date of passage of one of the payloads in front of the lane a.sub.i and on the other hand the set U.sub.i of dates not valid for an injection of one of the payloads of the lane a.sub.i into the collector; for each controlled disturbing load p of a disturbing flow controlled through a control means situated along the collector and before a lane a.sub.g(p) in the sense of movement of the collector, with g(p)∈{1, . . . , k}, a.sub.g(p) being also the first lane in the sense of movement of the collector, before which the controlled disturbing load passes (step 493): a) initializing t with the date δ.sub.1−Δ.sub.1, with δ.sub.1 representing the possible date of arrival should the first controlled disturbing load in front of the lane a.sub.k not be put on hold; b) computing the dates t+Δ.sub.1,g(p), t+Δ.sub.1,g(p)+1, . . . , t+Δ.sub.1,l(p) of passage of the controlled disturbing load in front of the lanes a.sub.g(p) to a.sub.l(p), with a.sub.l(p) being the last lane, in the sense of movement of the collector, before which the controlled disturbing load passes; c) if none of the dates t+Δ.sub.1,g(p), t+Δ.sub.1,g(p)+1, . . . , t+Δ.sub.1,l(p) belongs respectively to the sets V.sub.g(p), V.sub.g(p)+1, . . . , V.sub.l(p), computing a fictitious date of passage start.sub.p of the controlled disturbing load p in front of the lane a.sub.1, with the following formula: start.sub.p=t; d) if one of the dates t+Δ.sub.1,g(p), t+Δ.sub.1,g(p)+1, . . . , t+Δ.sub.1,l(p) belongs respectively to one of the sets V.sub.g(p), V.sub.g(p)+1, . . . , V.sub.l(p), incrementing t by one unit and reiterating the steps b), c) and d) with the new value of t; commanding (step 494) the control means for an injection at the date start.sub.p+Δ.sub.1,g(p) of each controlled disturbing load p before the lane a.sub.g(p).

9. CONCLUSION

(245) Since the travel time is critically important to obtaining the highest possible production rate, it is very important, in logistics, to being capable of combining several incoming flows. Using all the mechanical capacities of each system and therefore maximizing the throughput of such a collector is crucial in avoiding loss of time in customer order picking for example.

(246) We have attained the optimal throughput by injecting the loads at the earliest in a synchronized manner. We have especially attained the maximum capacities of the collector when it is dedicated to the injection flows. In addition to the modelling and mathematical resolution, we have extracted a formula enabling the direct computation of the dates of injection of each load. These results are given to comply with a final exit sequence of the loads once they are all on the collector, thus making it possible to combine the optimization of a speed and of a sorting operation.

(247) We have also discussed the management of several types of flows on the collector, in using the term “disturbing flow” to denote a flow different from the injection flow. We are able to compute the dates of injection using an algorithm that takes account of this disturbing flow when it is non-controlled. However, the throughput is optimal without guarantee of maximality. Indeed, such a non-controlled disturbing flow does not make it possible to recover a space left by a disturbing flow that would have gone out of the collector between the injection lanes.

(248) We have also proposed a solution in which the disturbing flow is controlled. Another algorithm has been given to make the controlled disturbing flow pass in such a way as to prioritize the maximum throughput of the collector once all the injection lanes have passed. The control of this controlled disturbing flow enables a maximum throughput of the injection flows once on the collector when all the loads of the controlled disturbing flow disappear before the last injection lane. If not, the remaining disturbing flows are included in the final flow of the collector and inserted into the sequence without spaces.

(249) An algorithm has also been given to manage at least one non-controlled flow (obstructions that are not obligatorily disturbing loads) and, at the same time, at least one controlled flow (disturbing loads).

10. EXAMPLE OF A CONTROL SYSTEM

(250) The proposed solution is a method of merging, within a logistical warehouse, k incoming flows of payloads, transported respectively by k conveyors called lanes α.sub.i with i∈{1, . . . , k}, into one outgoing flow of payloads transported by another conveyor called a collector.

(251) The method of merger is executed by a control system. This is for example a central warehouse control system or WCS.

(252) FIG. 44 presents the structure of the control system 90 according to one particular embodiment of the invention. This control system comprises a live memory 92 (for example a RAM), a processing unit 91 equipped for example with a processor and controlled by a computer program 930 stored in a read-only memory 93 (for example a ROM or a hard disk drive).

(253) At initialization, the code instructions of the computer program are for example loaded into the live memory 92 and then executed by the processor of the processing unit 91, to implement the method of merger of the invention (according to any one of the different embodiments described here above). The processing unit 91 inputs pieces of information 94 pertaining to the incoming flows. The processor of the processing unit 91 processes the information 94 and generates at exit instructions or commands 95 used to control (command) different elements included in the system, especially the lanes, the collector, the control means, etc.

(254) This FIG. 44 illustrates only one particular way, among several possible ways, of carrying out the technique of the invention in any one of its embodiments. Indeed, the control system is obtained equally well on a reprogrammable computing machine (for example a PC computer, a DSP processor, a microcontroller, etc.) executing a program comprising a sequence of instructions, or on a dedicated computing machine (for example a set of logic gates such as an FPGA or an ASIC or any other hardware module).

(255) Should the control system be carried out with a reprogrammable computing machine, the corresponding program (i.e. the sequence of instructions) can be stored in a storage medium that it detachable (such as for example a floppy disk, a CD-ROM or a DVD-ROM) or non-detachable, this storage medium being partially or totally readable by a computer or a processor.