SOME QUESTIONS OF METRIZATION OF THE SOLUTION SPACE OF THE SCHEDULING PROBLEM

Yu. Ya. Tarnopolsky

(Presented by the scientific-technical seminar of the Department of Automated Control Systems and the Control Laboratory)

Finding the best schedule for the operation of equipment is the central problem of the theory of control of discrete production. To this end, in the traditional formulation one considers the scheduling problem, in which an optimal schedule, in the sense of the chosen criterion, is found for processing \(n\) parts on \(m\) machines. The combinatorial possibilities of such a problem grow exponentially with the growth of its dimensions \((n \times m)\). Thus, for example, to find an optimal schedule by the method of complete enumeration it would be necessary to examine \((n!)^m\) variants of plans.

If we assume that the parts have identical technological routes without repetition of operations, then any feasible plan is determined by the order in which the parts are processed on each of the \(m\) machines. Any order of parts on the \(j\)-th machine \((j = 1,\overline{m})\) is determined by some permutation \(P_j\) of \(n\) elements (the numbers of the parts), and each schedule by a set of \(m\) such permutations.

Let \(S\) denote the set of all permutations of \(n\) elements, and let \(V\) be the set of sets of permutations \((P_1, P_2, \ldots, P_m)\), where \(P_j \in S\) \((j = 1,\overline{m})\). Then there exists a one-to-one correspondence between the set \(V\) and the set of all feasible plans, and the scheduling problem reduces to the optimization of some functional \(F(v)\) \((v \in V)\) on the set of sets of permutations \(V\).

The search for an optimal set \(v\) in a combinatorial space of this type requires a certain ordering of this space in order to distinguish its small neighborhoods and to choose a direction of motion. For this purpose, a metric is introduced on \(V\) in some way. Then, for optimizing the functional \(F(v)\) in the metric space, the method of statistical optimization [1] may be applied. For definiteness, suppose that \(\min F(v)\) is sought. Consider a method for searching for a local minimum of the functional in our problem.

For a given initial point \(v_0\), from its \(\varepsilon\)-neighborhood, \(K\) points are chosen at random, at which the values of \(F(v)\) are computed. Suppose the minimum of the \(K\) values of the functional is attained at the point \(v_1\). Then, if \(F(v_0) \leq F(v_1)\), \(v_0\) may be regarded as a point of local minimum, or an additional investigation may be carried out. If \(F(v_0) > F(v_1)\), then we take \(v_1\) as the new initial point, and the process described is repeated again for \(v_1\).

The application of the method of statistical optimization with a sufficiently large number of steps can guarantee the attainment of a local optimum with probability close to one. However, the effectiveness of optimization by such a method depends essentially on how a metric is introduced in the space \(V\).

As is known, the effectiveness of statistical search increases as the amount of additional information about the behavior of the function under study increases. In developing methods for searching for an extremum for analytic functions, the concept of continuity is of the greatest importance. By analogy, for discrete functions, if close points of the combinatorial space \(V\) correspond to close values of the functional, then the speed of attaining the optimum should, in all probability, be higher than in a “blind” search (the Monte Carlo method). In this connection there arises the problem of choosing a metric in the space \(V\) that ensures sufficient search efficiency. Such a metric, in our opinion, should ensure a good ordering of the combinatorial search space, corresponding to that definition of continuity which is used for ordinary analytically specified functions.

Indeed, if one takes a smooth function of a continuous argument, divides the domain of definition into \(N\) intervals, numbers these intervals arbitrarily, and, according to the numbering, constructs a new function with \(N-1\) discontinuities, then as \(N \to \infty\) we obtain a certain equivalent of the discontinuous function of a discrete argument considered by us. For such an example, our problem consists in finding a metric (a method of numbering the intervals) that restores, on the average, the original form of the function. In this connection we shall define a certain statistical equivalent of the property of continuity for a function of a discrete argument. We shall call this property, which gives important information about the behavior of a function of a discrete argument, the property of statistical continuity.

In what follows, for simplicity, we shall consider the set of permutations \(S\), since a metric specified on this set naturally induces a metric in \(V\).

Suppose that a metric is specified in some way in \(S\). Denote by \(Q(p)\) a neighborhood of the point \(p\). We shall call the neighborhood \(Q(p)\) nonminimal if there exists a neighborhood \(Q_1(p) \subset Q(p)\). Here \(\subset\) denotes strict inclusion.

Definition. A function \(F\), defined on the space \(S\), will be called statistically continuous at the point \(p \in S\) if for every nonminimal neighborhood \(Q_1(p)\) there exists a neighborhood \(Q_2(p) \subset Q_1(p)\) such that

\[ DF[Q_2(p)] \leq DF[Q_1(p)], \]

where \(DF[Q(p)]\) denotes the variance of \(F\) on the set \(Q(p)\).

It is easy to see that all functions of a continuous argument possess the property of statistical continuity. For functions of a discrete argument, the presence of statistical continuity can be established experimentally. Investigations carried out by the author showed that, for the space \(V\), the detection of the property of statistical continuity is essentially connected with the choice of a metric in this space. Statistical continuity may fail to be established for all points of \(V\). Metrics that ensure the best ordering, that is, a large percentage of points in the space with statistical continuity, are the best from the standpoint of organizing statistical search.

The property of statistical continuity gives additional information about the space \(V\), which makes it possible to organize an effective search for an extremum by adapting to this space.

If sufficiently large samples of values \(F(v)\), obtained with the aid of test scheduling problems, are available, then, without resorting to an actual verification of search methods using various metrics, it is possible—by using the property of statistical continuity—to check the relative effectiveness of such metrics.

Let us consider several metrics convenient for organizing a search. Page’s metric (metric \(\Pi\)). In E. S. Page’s paper [2] a metric is introduced for the solution space of the one-route, one-dimensional scheduling problem. As a measure of the closeness of two permutations \(p_1\) and \(p_2\), the number of violations of the grouping arrangement of the elements of one permutation relative to the other is taken. This quantity is an analogue of the distance between permutations and is denoted by \(\pi(p_1, p_2)\).

Let, for example, \(p_1=(1,2,3,4,5,6)\), and \(p_2=(4,5,6,1,2,3)\); then \(\pi(p_1,p_2)=1\).

It is not difficult to establish that the distance \(\pi(p_1,p_2)\) satisfies the known axioms of a metric:

1) \(\pi(p_1,p_2)\ge 0\) — (the identity axiom),

2) \(\pi(P_1,P_2)=\pi(P_2,P_1)\) — (the symmetry axiom),

3) \(\pi(p_1,p_2)+\pi(p_2,p_3)\ge \pi(p_1,p_3)\) — (the triangle axiom).

In [2] the notion of the \(K\)-neighborhood of a certain permutation \(p_0\) is introduced as the set of permutations for which \(\pi(p_0,p_i)\le K\), \((K=1,n-1)\). The \(K\)-neighborhood is denoted by \(U(p,K)\).

A random search in the neighborhood \(U(p_0,K)\) is organized as follows. From the set of permutations \(S\), an initial permutation \(p_0\) and a number \(K\) are chosen at random. \(K-1\) random numbers \(\xi_i\) are generated in the interval \([0,1]\), and these are arranged in increasing order. Next the numbers \(U_i=(n+1)\xi_i\) are formed (with range \(0\le U_i\le n+1;\ i=1,K-1\)), by means of which the initial permutation is partitioned into \(K\) groups. The natural numbers falling in the first interval \([0,U_1]\) indicate the position numbers of the elements of the first group of the permutation; those falling in the second interval—the second group, and so on. If the group numbers are denoted by natural numbers, then to each permutation of these numbers \((\alpha_1,\alpha_2,\ldots,\alpha_k)\) there corresponds a certain permutation \(p_i\) from the set \(S\) such that \(p_i\in U(p,K)\). By obtaining and randomly rearranging the \(K\)-groups of the initial permutation, we form random samples from the neighborhood \(U(p_i,K)\), which are used at each step of the search.

This method is called the “chain” Monte Carlo method. In [2] this method is studied in comparison with the ordinary Monte Carlo method (the blind-search method). The experiments were carried out for test problems of size \(20\times 10\) and \(30\times 5\). To achieve approximately identical results, the chain method requires 5–6 times fewer trials.

In [3] it is shown that the “chain” search method gives better results in comparison with a number of heuristic methods. In the opinion of the authors of [3], this phenomenon is explained by the higher degree of orderliness of the search.

Lexicographic metric (metric \(\gamma\)). The authors of [4] proposed a metric establishing a one-to-one correspondence between the set of permutations \(S\) and the interval of the natural sequence \(R=\{1,2,\ldots,n!\}\). The paper derives formulas for determining the number \(N(p)\) of a permutation in the sequence of permutations ordered lex-

lexicographic method, and of finding a permutation \(p\) from a given number \(N(p)\).

The distance between two permutations is given by the formula

\[ r(p_1,p_2)=|N(p_1)-N(p_2)| \]

and satisfies the axioms of a metric.

To find \(N(p)\), the entire set of permutations of \(n\) objects ordered lexicographically is subdivided into classes from the first to the \((n-1)\)-st order. Each class of the \((n-1)\)-st order contains one permutation; a class of the \((n-2)\)-nd order contains two permutations; a class of the \((n-3)\)-rd order contains \(3!\) permutations; and, finally, a class of the first order contains \((n-1)!\) permutations.

On the basis of such a partition, a formula has been derived for determining the number of a permutation:

\[ N(p)=(l_1-1)(n-1)!+(l_2-1)(n-2)!+ \]
\[ +(l_{n-2}-1)2!+(l_{n-1}-1)+1, \tag{1} \]

where \(l_k\) \((K=\overline{1,n})\) denotes the number of the class of order \(K\) in the class of order \((K-1)\).

To compute \(N(p)\) from the arrangement of \(n\) objects in the permutation \(p=(\alpha_1,\alpha_2,\ldots,\alpha_n)\), all objects are renumbered, and at the same time the natural sequence of numbers from one to \(n\) is written down. In this case \(l_k\) is the number of the number \(\alpha_k\) in the sequence \(1,2,\ldots,n\), if \(\alpha_1,\alpha_2,\ldots,\alpha_{k-1}\) are not counted.

To find the permutation from a given number \(N(p)\), the method of successive division is applied to formula \(N(p)\):

\[ N(p)-1=(l_1-1)(n-1)!+q_1, \]
\[ q_1=(l_2-1)(n-2)!+q_2, \]
\[ \cdots \tag{2} \]
\[ q_{n-3}=(l_{n-2}-1)2!+q_{n-2}, \]
\[ q_{n-2}=l_{n-1}-1. \]

In these formulas, \(q_1\) is the remainder from dividing \(N(p)-1\) by \((n-1)!\), and \(q_i\) \((i=2,\overline{n-2})\) is the remainder from dividing \(q_{i-1}\) by \((n-i)!\). We shall take \(l_1-1=l_2-1=\cdots=l_{n-2}-1=0\) if \(N(p)-1<(n-1)!\), \(q_1<(n-2)!\), \(\ldots\), \(q_{n-3}<2!\), respectively. The latter follows from the fact that in the computations we do not go beyond the set of integers.

On the basis of relations (2), the values \(l_k\) \((K=\overline{1,n-1})\) are determined:

\[ l_1=\left[\frac{N(p)-1}{(n-1)!}\right]+1 \]
\[ l_2=\left[\frac{q_1}{(n-2)!}\right]+1 \]
\[ \cdots \tag{3} \]
\[ l_{n-2}=\left[\frac{q_{n-1}}{2}\right]+1 \]
\[ l_{n-1}=q_{n-2}+1. \]

In these expressions the square brackets denote the integer part of a number.

Having constructed the direct dependence \(N(p)\) and the inverse dependence \(N^{-1}(p)\) between a permutation and its number in the natural sequence of numbers, one can easily organize a statistical search for the best solution as follows. Let us represent, by a point \(M\) in a rectangular coordinate system,

some schedule defined by a set of permutations \(v=(p_1,p_2,\ldots,p_m)\). The coordinate components of this point \(M\) will be, respectively, the quantities \(N(p_1), N(p_2),\ldots,N(p_m)\). The search space in a rectangular coordinate system is an \(m\)-dimensional parallelepiped with attached boundaries \([a_1,b_1; a_2,b_2;\ldots; a_m,b_m]\), where \(a_k=1\); \(b_k=n!\) \((k=\overline{1,m})\). Having chosen at random in the search space some initial point \(M_0\) and having determined for it the value \(F(M_0)\), we find in its \(\varepsilon\)-neighborhood \([\gamma(M_0,M)\leqslant \varepsilon]\), by random selection, \(K\) points. Each of these points \(M_q\) is characterized by a set of coordinates \(\{N_j^q\}\) \((j=\overline{1,m};\ q=\overline{1,K})\), which after the transformation \(N^{-1}(p)\) is converted into a set of permutations \(v_q\). Next the functional \(F(v_q)\) is computed, and the search continues according to the scheme described above.

Inverse metric (the \(\rho\) metric). In [5] a metric is considered in which the distance between permutations \(p_1\) and \(p_2\) is defined as the number of all inversions of the permutation \(p_2\) relative to \(p_1\). The distance from \(p_1\) to \(p_2\) satisfies the axioms of a metric and is denoted by \(\rho(p_1,p_2)\). The authors of [5] showed that the distances \(\rho(p_1,p_2)\) run through all integer values from \(0\) to

\[ \frac{n(n-1)}{2}. \]

With the aid of the introduced metric, a system of neighborhoods is defined in the space \(V\). Let \(v_0=(p_{01},p_{02},\ldots,p_{0m})\) be an arbitrary set of permutations, and let \(K\) be an integer \(0<K\leqslant \dfrac{n(n-1)}{2}\). We shall call the \(K\)-neighborhood of \(v_0\) the set of all those sets of permutations \(v=(p_1,p_2,\ldots,p_m)\) for which the condition is satisfied for all \(i=\overline{1,m}\).

In [5] a one-to-one correspondence is established between all permutations of the symbols \(1,2,\ldots,n\) and all integer vectors of the form \((a_1,a_2,\ldots,a_{n-1})\), where \(0\leqslant a_i\leqslant n-i\) \((i=1,n-1)\). The vector \((a_1,a_2,\ldots,a_{n-1})\) corresponding to the permutation \(p=(\alpha_1,\alpha_2,\ldots,\alpha_n)\) is called the index \(I\) of this permutation. The coordinates of the vector \((a_1,a_2,\ldots,a_{n-1})\) are determined from the components of the permutation \(p\) according to the following algorithm:

\[ \begin{aligned} &1)\quad a_1=\alpha_1-1,\\ &2)\quad a_i=l_i-1\quad (i=\overline{1,n-1}), \end{aligned} \tag{4} \]

where \(l_i\) is the number of the integer \(\alpha_i\) in the sequence \(1,2,\ldots,n\), if \(\alpha_1,\alpha_2,\ldots,\alpha_{i-1}\) are not counted.

It is assumed here that the zero of the space is the permutation \(p_0=(1,2,\ldots,n)\).

It is not difficult to note that, in a permutation with index \((a_1,a_2,\ldots,a_{n-1})\), the first element of the permutation forms \(a_1\) inversions, the second forms \(a_2\) inversions, and so on. Hence it may be concluded that the number of inversions of a permutation with index \((a_1,a_2,\ldots,a_{n-1})\) is equal to \(\sum_{i=1}^{n-1} a_i\). Next, the concept of an \(r\)-sphere with center at a certain permutation \(p_0\) is introduced as the set of all permutations \(p\in S\) having the property \(\rho(p_0,p)=r\). Each \(r\)-sphere contains as many permutations as there are distinct representations of the number \(r\) in the form of the sum

\[ r=\sum_{i=1}^{n-1} a_i\ (0\leqslant a_i<i) \]

taking into account the order of the summands.

Denote by \((r,q)\) the number of decompositions of the number \(r\) into the sum

\[ r=\sum_{i=1}^{q} a_i \]

with the order of the summands taken into account. Then the numbers \((r,q)\) can be determined from the following recurrence relation:

\[ (r,q)=(r-1,q)+(r,q-1)-(r-q-1,q-1). \tag{5} \]

The introduced concepts of the \(r\)-neighborhood index and of the number \((r,q)\) are used to organize an equiprobable selection of some permutation \(p\) from the \(K\)-neighborhood of any permutation \(p_0\). In doing so one may restrict oneself to the \(K\)-neighborhood of zero, since any permutation \(p=(a_1,a_2,\ldots,a_n)\), together with some of its \(K\)-neighborhoods, can be mapped topologically into zero with its \(K\)-neighborhoods by establishing the correspondence \(a_i \leftrightarrow i\) \((i=1,n)\).

Let us determine the number of permutations in some \(K\)-neighborhood. Since a \(K\)-neighborhood in the metric \(\rho\) consists of \(K\) \(r\)-circles \((0<r\le k)\), and each \(r\)-circle, in turn, consists of \((r,n-1)\) permutations, in all there are

\[ \sum_{r=1}^{k} (r,n-1) \]

permutations in the \(K\)-neighborhood. Among these permutations there are

\[ \sum_{r=1}^{k-a_1} (r,n-2) \]

such that their index begins with \(a_1\). In turn, among the latter there are

\[ \sum_{r=1}^{k-a_1-a_2} (r,n-3) \]

permutations whose index has \(a_2\) in the second position. Continuing this reasoning, one may conclude that the set of permutations whose indices begin with the numbers \(a_1,a_2,\ldots,a_i\) consists of the following number:

\[ \sum_{r=1}^{k-a_1-a_2-\cdots-a_i} (r,n-i-1). \]

To ensure equiprobable selection of permutations from the \(K\)-neighborhood of the zero permutation, the following algorithm is used:

1. The interval \([0,1]\) is divided into \(K_1\) parts in the ratio

\[ \sum_{r=1}^{K_1-1}(r,n_1):\sum_{r=1}^{K_1-2}(r,n_1):\ldots:\sum_{r=1}^{1}(r,n_1), \]

where \(K_1=K,\ n_1=n-1\).

1. Some value \(\xi_0\) of a random variable uniformly distributed on \((0,1)\) is generated. If \(\xi_0\) belongs to the \(i\)-th interval of the segment \((0,1)\), then we set \(a_j=i-1\).

2. Transition is made to stage 1, setting \(K_{j+1}=K_j-a_j,\ n_{i+1}=n_j-1\) \((j=1,n-1)\). By repeating stages 1 and 2 we obtain \(a_{j+1}\), and so on.

3. After the index \((a_1,a_2,\ldots,a_j,\ldots,a_{n-1})\) has been constructed, we find the permutation corresponding to it by means of the algorithm (4) given above.

On the basis of the algorithm considered, any scheme for statistical search for the best plan can easily be implemented.

In constructing the metrics \(\gamma\) and \(\rho\), an attempt was made to eliminate some shortcomings of the metric \(\pi\) proposed by Page. Compared with the metric \(\pi\), the metrics \(\gamma\) and \(\rho\) have a number of advantages, which reduce to the following:

1. The maximum distances between points of the space \(S\) for the metrics \(\pi\), \(\rho\), and \(\gamma\) are \(n-1\), \(\dfrac{n(n-1)}{2}\), and \(n!\), respectively. Thus, in the metrics \(\rho\) and \(\gamma\), each point of the space has a larger set of \(K\)-neighborhoods, which provides greater detailing of the combinatorial space and, consequently, makes it possible to organize the statistical search better.

2. In the metric \(\rho\), the closeness of permutations depends not only on the number of breaks, as is the case in the metric \(\pi\), but also on how far the broken parts are separated from one another and on how many elements of the permutation have changed their mutual arrangement. These properties of the metric \(\rho\) make it possible to take better account of the features of the scheduling problem from the point of view of organizing a directed search for an optimal schedule.

3. A known advantage over the other metrics is possessed by the metric \(\gamma\), which gives the greatest detailing of the space \(S\). At the same time, its drawback in comparison with the metric \(\rho\) is the dependence of the distance \(\gamma(p_1,p_2)\) on the order in which the parts are numbered.

To compare the metrics, Fig. 1 gives curves obtained by calculation for \(n=6\), characterizing the number \(M\) of permutations lying in the \(r\)-neighborhood of a certain permutation \(p_0\), as a function of the metrics used. It is seen from Fig. 1 that the coarsest detailing of the permutation space is given by the metric \(\pi\), and the finest by the metric \(\gamma\). With search step \(r=1\), all the metrics are practically equivalent, but already for \(r=3,4\) the use of the metric \(\pi\) is unrealistic. The use of the metrics \(\rho\) and \(\gamma\) makes it possible to traverse equivalent regions considerably faster than with the metric \(\pi\), which substantially increases the efficiency of the search.

Studies carried out on a computer confirmed the effectiveness of the metric \(\gamma\) in comparison with the metric \(\pi\). An optimal schedule was sought for a test scheduling problem of size \(m \times n \times l = 6 \times 6 \times 6\) (\(l\) is the number of operations of each part) under the most general assumptions. It was found that the number of infeasible schedules per one feasible schedule for the metric \(\pi\) was 5–6 times greater than for the metric \(\gamma\) for the same \(K\)-neighborhoods (\(K=2\)). This indicates that the efficiency of search using the metric \(\gamma\) is 5–6 times greater than when using the metric \(\pi\).

At present, programs for computers are being developed that will make it possible to carry out an experimental verification of the metric \(\rho\).

In conclusion, it is necessary to note that, in our opinion, studies in the field of metrization of combinatorial spaces are very promising for the construction of optimal schedules for the scheduling problem in its most general form.

LITERATURE

1. L. A. Rastrigin. Statistical Search Methods. Moscow, “Nauka,” 1968.

2. E. S. Page. On Monte-Carlo Methods in Congestion Problems. J. Oper. Res., 13, 2, 1965.

3. S. E. Oskolkova, I. O. Oskolkov. Application of certain heuristic methods to the solution of scheduling problems. Avtomatika i telemekhanika, 2, 1968.

4. D. I. Golenko, Yu. Ya. Tarnopol’skii. Optimization of schedules by directed search methods. Kibernetika, 6, 1970.

5. D. I. Golenko, Yu. Ya. Tarnopol’skii, Ya. N. Yaroker. An algorithm of statistical optimization for the scheduling problem. Collection of scientific works of the MDNTP seminar. Moscow, 1969.