In discrete idealization, a mathematical model of the assignment of the pairs of non-interchangeable tasks between the agents is formulated. The model describes, in particular, the state of the water transport logistics system at the decision-making moment during planning the usage of a group of heterogeneous cargo ships. Within the framework of the formulated model, the concept of “biassignment” is introduced and optimization problem of bi-assignment with a minimax criterion is posed, which generalizes the classical assignment problem. For the task and its practically significant refinements, the intractability is proved. Solving algorithms implementing the concept of dynamic programming and the branch-and-bound scheme are constructed. Examples of the numerical implementation of the bi-assignment synthesis are given. The developed model and algorithm are implemented in the logistics management support system in the Kazan river port.
The classical assignment problem (AP) (linear balanced assignment problem) – a problem of optimal, in one sense or another, assignment of the finite n-element collection of tasks between the same number of agents was first formulated in 1952 by Votaw, D. F., Jr. and Orden, A. in [1].
Subsequently, the AP served as the basis for setting various modifications and applied interpretations, including flexible production systems, determining the location of production facilities and so on.
A detailed analysis of the models and varieties of the assignment problem is presented, for example, in the overview chapters of [2, 3].
The development and research of algorithms for solving AP also have a long history since the early work of Kuhn H.W. [4] describing the method for solving the AP named by the author "Hungarian method".
This method and the method of potentials, as well as their modifications developed in recent years, are the main regular methods for synthesizing exact solutions of the AP [5, 6].
By these methods, the AP is solved in polynomial time of the size of the input. Among the numerous approaches developed for the synthesis of approximate solutions of the AP we note the algorithms developed on the basis of the heuristic concepts [7, 8].
Nowadays, due to the intensive development and integration in everyday practice of digital support management applications, in particular, in the operational planning of logistics and production and transportation processes [9], there is a need for advanced models for the distribution of discrete resources.
One of these extensions relates to the pair distribution of non-interchangeable resources (tasks) between the agents considered in the article.
As an example, we will point to the production and transport system [10], in which a selected group of non-identical river cargo ships is used for transporting sand and gravel mixture (SGM) to specified storage (consumption) points, loaded in a single technological cycle by floating hydro-mechanized mining complexes (HMC) on largescale area of riverbed deposits. In such a system, up to 10 – 15 HMC units can be involved, and the same number of ships arrives daily for loading.
At the end of the development session of the next operational plan for the functioning of the system under consideration, it should be unambiguously determined: • to which HMC unit from the number of riverbed deposits located at the area, each specific ship should be sent for loading SGM; • which unloading destination should be assigned to each specific ship after loading the SGM.
For the automated formation of operational plans for the operating of the production and transportation system, effective in the conditions of a current operating environment, the computer control support complex should include both a digital modeling system module and tools for solving the corresponding optimization problem of ship allocation between the HMC for loading SGM and ships distribution at SGM unloading points.
As a second example, we will mention the problem of paired distribution of highspeed passenger ship destinations along routes for mass transportation in megacities, regional and island agglomerations.
The purpose of this article is to develop a mathematical model for the distribution of pairs of non-interchangeable tasks between the agents, formulate an optimization problem with a minimax criterion, construct decision-making algorithms acceptable for practical use, and consider the computational complexity of the problem and its special cases.
It is in this way that the material of the article is presented, which includes six sections, two appendixes and References.
In the next (second) section a mathematical model for the pair use of discrete resources of the type in question is formulated, and the general problem of bi-assignment with a minimax criterion is stated, generalizing AP with a minimax criterion (Linear bottleneck assignment problem).
This problem is denoted in the article as GBAP (generalized bi-assignment problem).
The third section of the article is devoted to the construction of a discrete dynamic programming algorithm [11, 12], which allows one to synthesize exact solutions of the GBAP posed in the second section; an estimate of its computational complexity is given here [13] and, as an illustration, the result of the implementation of the algorithm on the numerical data of the example is given.
In the fourth section, an algorithm for the synthesis of optimal and suboptimal biassignments in the process of iterative synthesis of the solution of GBAP according to the branch-and-bound scheme is constructed.
The fifth section is devoted to two practically significant special cases of the GBAP, including taking into account the laboriousness of tasks and the productivity of agents; it is established that all these problems are intractable [9], algorithms of polynomial computational complexity cannot be built for them.
The sixth section of the article is Conclusion
Appendix 1 and 2 contains step-by-step implementations of the constructed dynamic programming algorithms and branches and boundaries for the example of GBAP given in the third section. 2
Let there be a set of agents I = {1, 2, … , n} and two sets of tasks P = {p1, p2, … , pn} and Q = {q1, q2, … , qn}. Each agent must be assigned to one of the tasks of the set P and one of the tasks of the set Q. Each of the tasks must be completed in full by only one agent.
The (nn)-matrices A = {aij} and B = {bij} of numerical estimates are assumed to be given, where aij is the cost of execution of the task pj by the agent i, bij is the cost of the execution of the task qj by the same agent, i = 1, n , j = 1, n .
Let us introduce the following notation: π1 = {π1(i), i = 1, n } is the set of assignments of agents to tasks from the set P, π2 = {π2(i), i = 1, n } is the set of assignments of agents to tasks from the set Q.
Both the assignment π1 and the assignment π2 are a bijection of the set I = {1, 2, … , n} to itself (permutation).
The equality π1(i) = j means the appointment of agent i to task pj. Similarly, the equality π2(i) = j means the appointment of agent i to task qj.
We denote pairs of the form < π1(i), π2(i) > as bi-assignment; it is supposed that when implementing bi-assignment < π1(i), π2(i) >, each agent i, first starting from time 0 performs task with the number π1(i), and then immediately proceeds to task with the number π2(i), i = 1, n .
In a general form, a GBAP with a minimax criterion is written as follows:
min (max[a1 () + b2 () ])
1, 2
(
If matrices A and B set the processing time of the task by the agents, then solving
(
It is easy to see that (
Let i be a natural constant not exceeding n, W1, W2 be arbitrary i-element subsets of {1, 2, … , n}.
By Z(i, W1, W2) we denote the subproblem of the problem (
According to the concept of dynamic programming [12], the state of the process of the pair distribution of the tasks of the sets P, Q between the agents of the set I at step i is uniquely determined by the triple (i, W1, W2), where i is a natural constant not exceeding n, restricting the assignment to agents with numbers 1, 2, ..., i, and W1, W2 arbitrary i -element subsets of the sets of indices of the tasks P, Q, respectively, available for distribution.
The optimal criterion value in the problem Z(i, W1, W2) is denoted by B(i, W1, W2).
B(i, W1, W2) is the Bellman function for problem (
B(1, {j}, {k}) = a1j + b1k; j, k N.
According to the optimality principle, for solving problem (
, Bopt(n, I, I) = min(max[(an + bn ), B(n-1, (I \ }, I \ ))]),
, where (α, β) are arbitrary pairs of indices from the set W1W2.
The implementation of the computational algorithm along these relations, denoted below by DP, begins with the determination of the quantities B(1, {j}, {k}) for all singleton sets W1 и W2.
Next, sequentially in increasing order of parameter i for all possible sets W1 and W2,
the values of the Bellman function B(i, W1, W2), i = 1, n − 1 are determined by formula
(
The value B(n, I, I) determined by relation (
In the process of executing the DP algorithm for each triple (i, W1, W2) of the
values of the arguments of the Bellman function, we should fix the pair (α, β) on which
the minimum of the right-hand side of relations (
Relations (
We specify below a phased implementation of the described synthesis algorithm for
solving problem (
Stage 1. The initial triple (1, {j}, {k}) and empty lists G and G* are initialized. By
the formula (
Stage 2. For values of i satisfying the inequality i < n, we calculate the values of the
Bellman function B(i, W1, W2) by the formula (
Stage 3. By the formula (
Stage 4. An element corresponding to the triple (z, V1, V2) is selected from the list G. The entry (z, α*, β*) is added to the list G*; for z = n, n -1, … , 2, the operations z = z-1, V1 = V1 \ α*, V2 = V2\ β* are performed.
Stage 5. Ending the DP algorithm: the list G* contains the optimal solution to
problem (
The complexity of the DP algorithm is determined by the number of calculated values of the Bellman function and is determined by the value О(4n).
As an illustration, we present the result of executing the DP algorithm on the
numerical data of problem (
The implementation of the branch-and-bound paradigm [14] consists in constructing a fragment of the variant tree sufficient to determine the optimal solution. The vertices of this tree correspond to states (i, , 2 ), where i is the number of assigned agents, 1 1 , 2 are the subsets of the sets P and Q that determine the assignments of agents {1, 2, ... , i}; in particular, the root of the variant tree corresponds to the triple (0, {ø}, {ø}).
The algorithm, hereinafter referred to as WG, for the implementation of the computational procedure according to the branch-and-bound scheme is completely determined by defining the methods for:
a) obtaining upper bounds UB for the values of minimax criterion (
To obtain an upper bound of the minimax criterion (
The bi-assignment < 1* (i), *2 (i) > ** thus formed provides an upper bound for UB in the root of the variant tree.
It is easy to see that, as a lower bound of LB at the root, we can take the quantity determined by the formula max[min a + min b] .
The above methods for obtaining bounds of UB and LB at the root induce procedures for finding the upper and lower bounds in the vertices obtained at all subsequent intermediate vertices of the variant tree.
The smallest of the UB bounds obtained during the calculation is called the record Rec; initially, the record values are assumed to be +∞, while the in WG algorithm execution process, the record value decreases.
The branching procedure consists in assigning the next agent to tasks from the sets P and Q, respectively, and pruning out the subsets of feasible solutions that knowingly do not contain optimal solutions.
When branching for agent i, all tasks pj and qk are considered, for which previous agents of the current branch were not assigned. Thus, we obtain (n − i + 1)(n − i + 1) new vertices.
Branching at the vertices in which the LB bound exceeds the existing record value is not performed as impractical.
As an example, on the numerical data of problem (
The result of applying this operator is a pair of numerical values corresponding to
the lower bound LB and the upper bound UB of the minimax criterion values (
The root of the decision tree corresponds to the state (0, {ø}, {ø}); the result of applying the operator to this state according to the procedures described above is the pair {53, 107}, the current record Rec becomes 107.
To evaluate the performance of the software implementation of the WG algorithm in comparison with the performance of the software implementation of the DP algorithm, computational experiments were performed on a test data set.
For each dimension n = 10 – 13, a hundred problems were solved, determined by the square matrices of numerical estimates A and B of the corresponding dimension.
The integer values of the elements of the matrices aij, bij were generated in a pseudo-random manner according to the uniform distribution law on the interval [0, 99].
The duration of the test run of each algorithm was measured to the nearest second. The experimental results are shown in table 1.
In production and transport applications, in the presence of strict regulatory
restrictions on the duration of solving problem (
In this context, the principal advantage of the WG algorithm is the ability to terminate it as soon as the set time limit for the task has been exhausted. In this case, an estimate of the deviation of the obtained approximate value of the minimax criterion from its optimal value will be known.
As a concretization, we introduce GBAPhw in which each of the available 2n tasks is characterized by the labor consumption of h, so task pj has labor consumption of h(pj), task qj – h(qj); each agent i is characterized by performance wi. With that, the elements of the matrices of numerical estimates А and В are calculated by the formulas aij = h(pj) / wi , bij = h(qj) / wi, i = 1, n , j = 1, n .
Under these conditions, for GBAP and GBAPhw problems, the following recognition problems corresponding to them can be distinguished.
Problem 1: with the initial GBAP data and the additional constant T, it is asked if there is a bi-assignment, implementation of which executes the entire set of available tasks no later than the time instant T.
Problem 2: with the initial data GBAPhw and additionally indicated constant T, the restriction is established by analogy with problem 1.
The computational complexity of GBAP is no less than the computational complexity of GBAPhw, Problem 1 and Problem 2; the computational complexity of GBAPhw and Problem 1 is no less than the computational complexity of Problem 2.
It is easily shown that Problem 2 in polynomial time can be reduced to the problem “matching with weight restrictions,” which, in turn, is NP-complete [13].
Thus, the intractability of both the general problem of bi-assignment and the particular modifications considered in this section is established; according to the accepted hypothesis about the distinction of the classes of problems P and NP, it is not possible to construct decisive algorithms of polynomial computational complexity for these problems. 6
The article proposes a mathematical model of the assignment between the agents of pairs of non-interchangeable tasks. The model describes, in particular, the state of the production and transport system at the decision-making moment when planning the usage of a group of heterogeneous cargo ships.
In the framework of the formulated model, the concept of “bi-assignment” is introduced and bi-assignment problem with a minimax criterion, which generalizes the classical assignment problem, is posed. The intractability of the task and its practically meaningful special cases is proved.
Solving algorithms, implementing concepts of dynamic programming and branches and bounds, are constructed.
As an example, the result of a phased implementation of bi-assignment synthesis for a problem with square matrices numerical estimates of fourth-order is given.
For practically significant for industrial transport applications values of dimension n = 10 – 13, the results of massive computational experiments on a comparative evaluation of the performance of developed algorithms are presented.
The results obtained demonstrate the importance of the developed algorithms for use, for example, in digital systems of support planning of the distribution of highspeed passenger ships along routes for mass transportation in megacities, regional and island agglomerations.
Prospects for further research are to modify the proposed model for a wider range of applied problems, including those requiring multi-criteria formulation [15].
In terms of mathematical models and the general problem of bi-assignment, characterized by increased dimensions and, accordingly, requiring practically unacceptable calculation time for their implementation, it is advisable to focus on the development of algorithms based on metaheuristic concepts [16], as well as oriented to supercomputer technologies for the implementation of computational processes [17, 18].
Acknowledgments. This paper has been prepared as a result of studies financially supported by the Russian Foundation for Basic Research, project no 15-07-03141.
Volga State Academy of Water Transport, no. 53. VSUWT publishing house,
N. Novgorod, pp. 25-31 (2017).
16. Blum, C., Roli, A.: Metaheuristics in combinatorial optimization: Overview and
conceptual comparison. ACM Computing Surveys, no 35(
doi:https://doi.org/10.1016/j.parco.2005.04.005 18. Fedosenko Yu., Reznikov M.: A Model of FPGA Massively Parallel Calculations for Hard Problem of Scheduling in Transportation Systems. In: Battiti, R. et al. (Eds): Learning and Intelligent Optimization. LION 2017, LNCS, vol. 10556, pp. 370-375 (2017). doi:https://doi.org/10.1007/978-3-319-69404-7_33