Features of the implementation of scheduling algorithms that underlie modern concepts of production planning (Advanced Planning & Scheduling, Enterprise Resource Planning, and Manufacturing Execution Systems) are considered in the article. A generalized scheduling problem is formulated and its belonging to the NP class is proved by polynomial reduction to the traveling salesman problemа. Conceptual schemes of algorithms for solving this problem at different stages of the schedule's life cycle have been developed: an algorithm without decision-making procedures; an algorithm using decision-making procedures and an algorithm with optimization of an acceptable schedule. For each type of algorithm, a place in the hierarchy of enterprise planning systems is defined, the main provisions on work efficiency in a complex production system are formulated, and the mathematical apparatus of scheduling theory is considered and some recommendations for its application are given. The interrelation of the application of analytical and heuristic procedures in finding an acceptable solution is shown.
Schedule theory is used in such subject areas as production management, traffic
management, project planning, resource management in computer systems. However, the
variety of mathematical models and scheduling methods usually poses an inevitable
problem for applied mathematicians and programmers to construct fast algorithms and
their effective software implementation, taking into account the specifics of the
problem being solved. The use of standard solutions for such purposes is extremely limited
*
and inefficient. A more promising solution is the use of an object-oriented approach,
which implies the creation of a system of classes and mechanisms for their interaction
[
To date, to solve the task of scheduling, the capabilities of information systems are
actively used, taking into account the world experience of the largest enterprises in
various industries. Such systems are based on the concept of Enterprise Resource
Planning (ERP), covering a wide range of planning and resource management tasks. Along
with ERP, systems designed to solve highly specialized tasks are widespread. Among
these systems, the following can be distinguished: Advanced Planning & Scheduling
(APS) – development of detailed plans with the ability to control and account for
changes; Manufacturing Execution System (MES) – solving tasks of operational
scheduling and scheduling; and Supply Chain Management (SCM) [
The task of scheduling is one of the main ones in scheduling theory. A characteristic feature of most problems of this class is their NP - complexity, that is, the impossibility of finding the exact solution in polynomial time. Complexity theory allows us to answer the question of whether a particular problem belongs to the class of polynomially solvable – P. The problem of the relation of the classes of problems P and NP has existed for many years, therefore heuristic algorithms are used to solve NP problems that find feasible solutions in polynomial or pseudopolynomial time.
From a mathematical point of view, the task of scheduling is formulated as the
problem of combinatorial optimization of servicing a finite set of operations in a system
containing a limited set of pieces of equipment. A lot of algorithms have been
developed that give an exact solution to classical problems in a time-limited by a polynomial
in the length of the input data. For example, these are various sorting algorithms; classic
algorithms for solving single-instrument problems of scheduling theory; schedule with
interruptions, satisfying the deadlines for an arbitrary number of machines; schedule
for two machines with a minimum total service time and others [
However, for most of the practical problems arising in industry, transport, and other specialized technical systems, algorithms for finding optimal solutions in polynomial time are unknown. This is also because such problems are difficult to formalize (or impossible), that is, mathematical models of such problems may contain several assumptions that affect the quality of the output data, or schedules.
One of the ways to solve this problem is the transition from the search for the optimal
solution to the acceptable one. The Boolean penalty function was chosen as the
objective function, for which the result can be easily interpreted into the economic indicators
of the schedule (cost) [
The development of new and modification of existing mathematical models of scheduling problems in various fields of industry, as well as algorithms for finding feasible solutions to such problems, is an actual direction in the development of scheduling theory. 2
Consider the following problem. There are many devices E = {1, …, n}. A certain fund of time corresponds to each device Hk (k E). Nomenclature are available N = {1, … , m}, on which many operations are defined R = {rij, i N, j = 1, … , pi}. Precedence relationships are defined over the entire set of operations j – 1 j. The processing time of the rij operation on the device is known as Ek – to(rijk). The “classic criteria” is the minimization of the total processing time of an item, that is:
This problem belongs to the class NP. We prove this statement using the lemma "on reducibility".
Lemma 1 (“on reducibility”) Let the tasks U, Q NP. Then the following statements are true: 1. If Q P, and the problem U polynomially reduces to the task Q, then U P. 2. If Q NP, and the problem U polynomially reduces to the task Q, then U NP.
It is known that the salesman problem NP [
Let’s represent the set E in the form of a directed graph G without loops with many vertices V = {1, 2, ... , k}. The arcs between the vertices have weights corresponding to the values of to(rijk) elements of the set R. The minimum execution time for one element corresponds to the existence of a Hamiltonian graph in the task Q. Obviously, the reduction of the sets R and E to the sets G and V is polynomial.
If the Hamilton cycle exists in the traveling salesman problem, then it follows that problem U also has an optimal solution. Therefore, if the problem Q is polynomially solvable, then the problem U P. And vice versa, if there is no polynomial algorithm for problem Q, then problem U is not solvable in polynomial time.
The relationship between the classes P and NP is opened in the theory of
NPcompleteness. However, the fact that no polynomial algorithm was found for any
NPcomplete problem indirectly confirms the strict inclusion hypothesis P NP, that is P
≠ NP [
Let’s consider the special case when it is required to find any feasible solution in task U. The optimization criteria, in this case, is not defined.
Tasks of this type are the most common in practice. The obvious solution, in this
case, is the following – it is necessary to take the operation rij and assign it to the
machine Ek from the set R at each iteration. In this case, two conditions must be taken into
account: preservation of the relations of the precedence of operations; the sum of all
operations assigned to the machine does not exceed the value Hk [
The algorithm for solving the problem is presented in Fig. 1. Here Sorting(R) – sorting procedure for multiple operations, Error – flag of an error that occurs when one of the conditions of the loop. The error occurs in two cases: when at the next iteration it is impossible to assign an operation rij to Ek; when, as a result of the assignment, the moment of execution of the operation rij+1 occurs before the completion of the processing of the operation rij.
This task can be considered as the task of assessing the possibility of performing
item N on a variety of device E in the hierarchy of production planning systems [
The method of sorting the set of input data affects the result of solving the problem.
It can find a valid or optimal (in some cases) solution on the same set of input data
using sorting. For example, the sequence EDD (requirements are served in
non-decreasing deadlines) is given an optimal solution to the problem 1 || ∑Uj. In terms of
scheduling theory, this problem has the following formulation: minimizing the number of
late requirements [
Heuristic procedures together with optimal sequences can be used to solve such problems. They are based on the knowledge of domain experts, calculations, and other empirical data. The heuristic method for sorting a set of input data is based on the following position: the elements of the set R are divided into several groups, the elements of each of which are sorted according to a certain rule. Thus:
R = (X1, X2, … , Xn) where Xi – is the setting in which operations are sorted following rule i; n – several groups/rules.
So, the work of [
Indeed, most of the time fund of the device is in lengthy operations. The other operations are more flexible, that is, characterized by shorter processing times, and can be reassigned to other machines.
Despite the relative simplicity of the implementation, the assumption made in the
formulation of the original problem significantly narrows the scope of the algorithm for
calculating the schedule without decision-making procedures. Such algorithms are
actively used in systems of the APS class, for which the main factor is the time for
constructing a schedule at very large values N [
For several other production tasks, a simple answer to the question of the existence of
an acceptable solution is not enough. Such tasks belong to the class of operational
planning and are characterized by small values of the planning horizon. To find solutions
to such problems, advanced algorithms are used. They can still apply the sorting
procedure for the input set of operations [
The choice of a vertex is determined by a set of rules that are formed during the statement of the problem. As with sorting, rules can be analytical or heuristic.
The procedure Pull is responsible for choosing the operation rij from the set R The
difference between analytical and heuristic rules is that in the second case, the
consequences of the choice are not evaluated. The heuristic rules for choosing a vertex are
based on the service time of operation rij on the device Ek. The following rules are
existed [
A large number of rules are explained by the variety of production planning tasks.
The inclusion of a rule in the Pull procedure must be justified analytically or
empirically. In practice, expert judgment and weighting methods are used for these purposes.
[
Verification of the possibility of exclusion of the considered vertex Ek is the basis of analytical rules. Consider the following example. Let it be an operation rij on an iteration of the algorithm. It is necessary to decide on the appointment of this operation on the device from the set E. As in the original statement of the problem, the duration of
According to the condition of the problem, this value can be different when moving from one machine to another.
The criteria for assigning the operation rij to the device Ek consists of the fulfillment of the condition: (1) (2) processing an operation on machines from the set E and time funds Hk are known Based on these data, it is possible to determine the amount of time required to complete the processing of a nomenclature unit Ni in an iteration l: where tsl – total processing time of a nomenclature unit Ni at an iteration l.
The more effective is the assignment, the lower the value (1). Most of the
computational work is involved in calculating and checking conditions of (2). This problem is
reduced to the task of finding a critical path on a graph [
It should be noted that in practice, analytical rules in a “pure form” are rarely used
due to the high computational complexity. The balance between the accuracy of the
algorithm and the speed of its operation is regulated using the constant C, which limits
the depth of the search. The computational complexity of the schedule calculation
algorithm with decision-making procedures is influenced by the number of rules in the
procedure Pull. At the same time, search operations are not typical for heuristic rules.
They have constant computational complexity, which is numerically equal to the
sorting time of the set R, by the selected criterion. Therefore, algorithms that use heuristic
rules in the Pull procedure are faster than algorithms based on analytical rules [
Algorithms with optimization as input receive the calculated allowable schedule, and
the algorithms considered earlier get a lot of operations [
Since optimization is carried out according to a given criterion, it is necessary to obtain an acceptable schedule at the initial iteration taking into account F. This schedule is taken as the base. If an error occurs during the next iteration, the algorithm will return the base schedule as a result. To limit the computational complexity of the algorithm, the number of optimization operations is introduced, denoted as n. The larger is the n value, the more accurate the output schedule can be. It is impossible to guarantee a direct proportional dependence of the number of iterations n on the quality of the schedule because of the convergence of heuristic algorithms that are used to solve the optimization problem.
CalculateSchedule procedure solves the optimization problem taking into account
the criterion F, passed as an argument. As a result, the order of rijk assignments in the
Schedule is changed. In addition to solving the optimization problem, it solves the
problem of choosing the initial operation (a return point).
The return point is the vertex on the graph from which the search for the best path in
terms of the problem is started. For large R, the analytic problem of finding a return
point by exhaustive search has complexity n! which does not apply to practical
problems. In particular, the iterative transition method to the previous vertex (branch and
bound method) and the method of returning to the initial vertex also do not provide an
acceptable speed. The following heuristic approaches to determining the return point
are proposed in the literature [
At each iteration, the schedule is calculated for the current set of Schedule assignments, taking into account criteria F. The graphic meaning of the solution is the following. Many assignments are represented as a directed graph with vertices rijk. Starting at some vertex marked with a return point, the algorithm tries to find a different sequence of assignments. If such a sequence exists, and the value of the criterion Fi is greater than the similar value of F for the previous iteration, then the solution is considered improved. This defines the task of finding the critical path.
Features of scheduling algorithms used in modern production planning systems were identified in the article. Knowing the features of the functioning of the corresponding algorithms at different stages of the life cycle of the schedule makes it possible to balanced the use of limited computing power and time resources.
The described methodology for decomposing a complex problem into many simple ones can be applied by developers of production planning systems. As a further direction of research development, it is planned to develop a prototype of an information system for scheduling and synchronization based on an open architecture, which in terms of MES is a function of Operations – Details Scheduling (ODS).