On the Use of Pattern Recognition Methods for Solving Production Scheduling Problems

ON THE USE OF PATTERN-RECOGNITION METHODS FOR SOLVING PROBLEMS OF PRODUCTION SCHEDULING

S. I. Sidonskaya

(Presented by the scientific and technical seminar of the Department of Automation and Telemechanics)

Optimization problems for schedules of a size of practical interest are among the most difficult from the computational point of view because of their combinatorial nature.

Exact methods for solving combinatorial problems of this type, based on complete or “directed” enumeration of all possible variants of the solution of the problem, do not make it possible to obtain a solution to the problem in an acceptable time.

This has led to numerous attempts to develop approximate methods for solving the problem which, although they do not guarantee obtaining the optimal solution, nevertheless lead to solutions close to optimal within acceptable times. In practice, the so-called heuristic algorithms are most often applied, using various preference rules \[1, 2\]. In this connection, the problem of choosing the preference rules themselves, or their combinations, that ensure the production of schedules sufficiently close to optimal acquires special importance. In a number of authors \[1, 2, 5\], when solving scheduling problems, the problem of choosing preference rules or their combinations was solved without taking into account the features of the job portfolio for which the schedule was being drawn up. However, experience shows \[3\] that for each scheduling problem arising in production and possessing its own features in accordance with the features of the job portfolio, it is impossible to indicate a priori the advantage of choosing one or another preference function, or of choosing one or another algorithm for solving the problem in the more general case. Using the method set forth in \[4\], we shall make the choice of an algorithm for solving a scheduling problem depend on the initial data (parameters) of the problem, on the basis of applying methods of pattern-recognition theory.

In this case, the pattern to be recognized is the portfolio of orders \(\Pi(p_1p_2\ldots p_n)\), where \(p_1p_2\ldots p_n\) are features (parameters) by which the recognized patterns of scheduling problems may be distinguished from one another. Such features \(p_i\) (parameters) of the order portfolio may be the weight of orders of a certain type, the weight of urgent orders, the total number of orders, etc.

Let the machine be given a training sequence of patterns, i.e., let order portfolios \(\Pi_i(p_1^i p_2^i\ldots p_n^i)\) be given, with an indication of the class to which each of them belongs. Patterns are grouped into a class for wh—

for which the algorithm corresponding to this class is the most effective according to the chosen criterion.

The problem is to construct a program which, using a training sequence, would develop a rule making it possible to classify “unknown” portfolios of orders, generally speaking different from those included in the training sequence.

Suppose that, in the course of solving a sufficiently large number of problems determined by portfolios of orders $\{\Pi_i\}$, a set of such parameters $p_1p_2\ldots p_n$ has been found, the relationship among which makes it possible, with a certain probability, to determine an element $\in a A$ (where $A$ is the set of algorithms for solving the problem) on which the extreme value of the chosen optimality criterion is attained. In other words, suppose that it has been possible to partition the space $P$ of vectors $\{p_1p_2\ldots p_n\}$ into subspaces $P_a$, $a=\overline{1,N}$ such that

1) the subspaces of problems $B_a$ and $B_b$ solved by different algorithms $a$ and $b$ do not intersect, i.e. $P_a \cap P_b=\Phi$, if $a,b\in A$, $a\ne b$;

2) the sum of all subspaces of problems solved by different algorithms constitutes the space $P$, i.e.

$$ \bigcup_{a=1}^{N} P_a = P, $$

3) if $P(p_1p_2\ldots p_n)\in P_a$, then with the greatest probability the $a$-th algorithm attains the extremum of the optimality criterion.

Then the solution of the problem posed reduces to computing the vector $P(p_1p_2\ldots p_n)$ for an “unknown” portfolio of tasks, determining the membership of the point defined by this vector in one of the subspaces $P_a$, and drawing up a schedule according to the algorithm corresponding to the given subspace.

The indicated methodology is applied in solving the problem of optimizing calendar planning for a discrete-type enterprise engaged in testing finished products. The problem is formulated in terms of queueing theory. The enterprise is represented as a multichannel, multiphase queueing system with waiting and without losses. The input flow is formed by a set of $I$ heterogeneous jobs $B_i$, $i=\overline{1,I}$, arriving at random moments of time. Each job $B_i$ is represented by a set of operations, by the topologically ordered graph $G_i$. The assignment of each operation $(\alpha,\beta)$ of the graph $G_i$ to a specified service apparatus $j$ and the labor requirement of this operation $d(\alpha,\beta)$ are known. The service discipline is specified by some decision rule $R$, constructed on the basis of applying an additively weighted combination of local preference rules. Assumptions in the model:

1) a standard execution time is established at the enterprise for processing the $i$-th job;

2) the operating time of the system (the planning period) is strictly limited;

3) the graphs $G_i$ have a deterministic structure;

4) the assignment of requirements to apparatus is unambiguous;

5) the apparatuses are not interchangeable;

6) service is carried out without losses.

It is required to choose a queue discipline in the queueing system that would yield an extreme value of the chosen efficiency criterion.

The principal part of the mathematical model of the queueing system is the embedding block. The functions of this block

consist in the sequential embedding of requests \((\alpha,\beta)_i\) from the queue \(\{(\alpha,\beta)\}^{i_0}\) into the \(j\)-th service device, i.e., in determining the start time of service \(t^H(\alpha,\beta)_i\) of the request \((\alpha,\beta)_i\) in accordance with the topology of the tasks \(G_i\), the throughput capacity of the device \(x_j\), and the parameters of the queue \(\{(\alpha,\beta)\}^{i_0}\). The set of sought values \(\{t^H(\alpha,\beta)_i\}\) for all \((\alpha,\beta)_i \subset \{(\alpha,\beta)\}\), under the condition that the completion time of service of the request \(t^o(\alpha,\beta)_i\) is equal to

\[ t^o(\alpha,\beta)_i = t^H(\alpha,\beta)_i + \tau(\alpha,\beta)_i, \]

(where \(\tau(\alpha,\beta)_i\) is the execution time of operation \((\alpha,\beta)_i\)), is a calendar plan for executing the complex of operations \(\{(\alpha,\beta)\}\) and, consequently, the problem of the embedding block consists in finding the system operating mode that is optimal according to the given criterion. At each current moment of time it is determined whether the service device is occupied or free; a queue is formed for each free device; and for each device a request having the highest priority is selected from this formed queue and is embedded at the given moment in time for service.

The choice of the time step of modeling is made according to the method of special states [6], i.e., the behavior of the system in the modeling process is considered only at the moments when the service devices are released.

The author has developed algorithms and compiled corresponding programs for the BESM-4 computer using the most common preference rules, such as: “first come—first served” (FGFO), the shortest-operation rule (SIO), the longest-operation rule, and also their additive-weighted combination. Using these programs, a series of calendar-planning problems was computed by all algorithms included in the initial set. For each problem, with its corresponding portfolio of tasks \(P(p_1p_2\ldots p_n)\), an algorithm \(a \in A\) was found on which the extremal value of the selected efficiency criterion is attained.

One of the practical questions to be solved when using the proposed method is the question of choosing a set of features (parameters) that would characterize the recognized images sufficiently fully. Preliminary processing of the results in order to identify characteristics of tasks combined into one class (corresponding to one class) made it possible to single out three parameters of the task portfolio.

The general algorithm for solving the calendar-planning problem includes the following blocks:

1. A block for inputting initial information about the task portfolio for the planned period.
2. A block for calculating the problem parameters and constructing the vector

\[ P = P(p_1p_2\ldots p_n). \]

1. A “recognition” block (selection of the corresponding algorithm according to the vector \(P(p_1p_2\ldots p_n)\)).
2. Computation of the problem according to the selected algorithm.
3. Formation and output of the calendar plan.

The first results relating to the creation of a training sequence for the further construction of a separating plane and the application of pattern-recognition methods make it possible to conclude that the chosen method is expedient.

References

1. L. V. Kochnev. Optimization of a priority system in scheduling problems. In: Cybernetics and the University. Issue 3. Tomsk, TSU Publishing House, 1970.

2. P. L. Stepanov. Optimization of combinations of local priority rules by means of self-adjusting computer programs. In: Cybernetics and the University. Issue 4. Tomsk, TSU Publishing House, 1971.

3. T. P. Podchasova. On estimates and the choice of preference rules in calendar-planning problems. Automated Enterprise Management Systems. Issue 1. Kiev, Academy of Sciences of the Ukrainian SSR, 1968.

4. V. A. Tatarov. On the possibilities of applying pattern-recognition methods in the automation of operational production planning and control. Moscow, Academy of Sciences of the USSR, 1969.

5. G. Fisher, G. L. Thompson. Combinations of local rules for calendar planning applicable to a self-adjusting, probability-based computer program. In: Calendar Planning. Edited by J. F. Muth and G. L. Thompson. Moscow, Progress, 1966.

6. N. P. Buslenko. Modeling of Complex Systems. Moscow, Nauka, 1968.