=Paper=
{{Paper
|id=Vol-2834/Paper5.pdf
|storemode=property
|title=Features of Constructing Scheduling Algorithms in Enterprise Planning Systems
|pdfUrl=https://ceur-ws.org/Vol-2834/Paper5.pdf
|volume=Vol-2834
|authors=Alexander A. Chernenko,Pavel Yu. Buchatskiy,Andrey V. Shopin,Semen V. Teploukhov
}}
==Features of Constructing Scheduling Algorithms in Enterprise Planning Systems==
https://ceur-ws.org/Vol-2834/Paper5.pdf
50
Features of Constructing Scheduling Algorithms in
Enterprise Planning Systems*
Alexander A. Chernenko 1 [0000-0002-8182-0005], Pavel Yu. Buchatskiy 1 [0000-0002-3161-6567],
Andrey V. Shopin 1 [0000-0001-9504-7378], Semen V. Teploukhov 1 [0000-0003-0099-0369]
1 Adyghe State University, Maykop, Russia
spiritfov@yandex.ru
butch_p99@mail.ru
ashop409@gmail.com
mentory@yandex.ru
Abstract. Features of the implementation of scheduling algorithms that underlie
modern concepts of production planning (Advanced Planning & Scheduling, En-
terprise Resource Planning, and Manufacturing Execution Systems) are consid-
ered in the article. A generalized scheduling problem is formulated and its be-
longing to the NP class is proved by polynomial reduction to the traveling sales-
man 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 proce-
dures and an algorithm with optimization of an acceptable schedule. For each
type of algorithm, a place in the hierarchy of enterprise planning systems is de-
fined, the main provisions on work efficiency in a complex production system
are formulated, and the mathematical apparatus of scheduling theory is consid-
ered 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.
Keywords: planning algorithms, scheduling systems, greedy algorithms, heuris-
tic algorithms.
1 Introduction
Schedule theory is used in such subject areas as production management, traffic man-
agement, 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 prob-
lem being solved. The use of standard solutions for such purposes is extremely limited
* Copyright 2021 for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0).
51
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
[1].
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 Plan-
ning (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 sched-
uling and scheduling; and Supply Chain Management (SCM) [2].
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 solv-
able – 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 prob-
lem 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 devel-
oped 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 [3].
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 as-
sumptions 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 objec-
tive function, for which the result can be easily interpreted into the economic indicators
of the schedule (cost) [4].
The development of new and modification of existing mathematical models of
scheduling problems in various fields of industry, as well as algorithms for finding fea-
sible solutions to such problems, is an actual direction in the development of scheduling
theory.
2 Mathematical Schedule Problem
Consider the following problem. There are many devices E = {1, …, n}. A certain fund
52
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 [5]. Let’s carry out the polynomial
reduction of the formulated problem (we denote it by U) to the traveling salesman prob-
lem using Lemma 1.
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 re-
duction 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 NP-
completeness. However, the fact that no polynomial algorithm was found for any NP-
complete problem indirectly confirms the strict inclusion hypothesis P NP, that is P
≠ NP [6].
3 Scheduling Algorithms Without Any Decision-Making
Procedures
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 ma-
chine 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 [7].
The algorithm for solving the problem is presented in Fig. 1. Here Sorting(R) – sort-
ing procedure for multiple operations, Error – flag of an error that occurs when one of
53
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 mo-
ment 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 [8, 9].
These are various workshop tasks: calculating the schedule for the workshop, shift, a
separate machine, the entire enterprise.
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-decreas-
ing deadlines) is given an optimal solution to the problem 1 || ∑Uj. In terms of sched-
uling theory, this problem has the following formulation: minimizing the number of
late requirements [10].
Heuristic procedures together with optimal sequences can be used to solve such
problems.
Fig. 1. Algorithm without any decision procedures
54
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 [11] offers the following methodology for splitting the set of opera-
tions. The initial set is divided into three subsets: large works (their number is limited
by a constant), medium (have a small total length), and small (short works). The process
of building a schedule runs from large to small jobs. At the same time, medium and
small operations are assigned to machines using a greedy algorithm. In terms of sched-
uling theory, such a technique is the most consistent with the maximum load criterion
for machines:
where Hk – actual device load Ek.
Indeed, most of the time fund of the device is in lengthy operations. The other oper-
ations 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 ac-
tively used in systems of the APS class, for which the main factor is the time for con-
structing a schedule at very large values N [12].
4 Scheduling Algorithms with Decision-Making Procedures
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 plan-
ning 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 pro-
cedure for the input set of operations [13, 14]. But in this case, the application of this
procedure can only become one of the favorable factors for reducing the computational
complexity of the combinatorial problem, but it is not a factor determining the quality
of the solution. The efficiency of scheduling calculation algorithms with decision-mak-
ing procedures, based on the name, is determined by the branching depth in the search
tree for alternative solutions (Fig. 2).
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
55
difference between analytical and heuristic rules is that in the second case, the conse-
quences 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 [15]: Shortest imminent operation (SIO), Longest remaining time (LRT), First
off – first on (FOFO), First in – first out (FIFO), Last in – first on (LIFO), and Pair
comparison (R). There are also combinations of the above rules, for example, LRT +
SIO, LRT + R, etc. Here the “+” sign plays the role of a condition. That is, if the first
rule cannot be applied, then preference is given to another, but not vice versa.
Fig. 2. Algorithm with decision procedures
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 empiri-
cally. In practice, expert judgment and weighting methods are used for these purposes.
[16].
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 itera-
tion 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
56
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:
(1)
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:
(2)
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 computa-
tional 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 [17], where the vertices are
machines from the set E, and in the arcs are values of (2).
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 al-
gorithm 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 sort-
ing 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 [18].
5 Optimization Schedule Algorithms
Algorithms with optimization as input receive the calculated allowable schedule, and
the algorithms considered earlier get a lot of operations [19]. Denote it as Schedule0.
The goal of the optimization algorithm is to find the best solution compared to Sched-
ule0, taking into account the selected optimization criteria F. Consider the algorithm for
solving this problem in the general form (Fig. 3).
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 sched-
57
ule because of the convergence of heuristic algorithms that are used to solve the opti-
mization 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 prob-
lem of choosing the initial operation (a return point).
Fig. 3. Scheduling algorithm with optimization
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 prob-
lems. In particular, the iterative transition method to the previous vertex (branch and
58
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 [20]: consider the return point as the part of the valid
Schedule solution in which only large works are assigned; taking into account that the
speed of the algorithm for calculating the schedule and the number of search vertices
are known, it should be taken as the return point for which the total time of the algorithm
will not exceed the specified value T.
At each iteration, the schedule is calculated for the current set of Schedule assign-
ments, taking into account criteria F. The graphic meaning of the solution is the fol-
lowing. 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 se-
quence 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 con-
sidered improved. This defines the task of finding the critical path.
Table 1. Characteristics of the scheduling algorithms
Algorithm without
Algorithm / Crite- Algorithm with de- Optimization algo-
any decision proce-
ria cision procedures rithm
dures
Sync frequency low high high
Planning horizon long long/short short
The degree of inter-
pretation of the re- low high high
sult
The ability to evalu-
absent present present
ate the result
The dependence of
Depending on the
time complexity on direct
absent conditions of the
the quality of the so- proportionality
task
lution
Optimization single-criteria opti- single/multi-criteria
absent
criterion mization optimization
Application area APS MES/APS MES/ERP
Algorithms with decision-making procedures, exact algorithms for finding solutions
for canonical problems of scheduling theory, “greedy” algorithms can be used to sched-
ule in the CalculateSchedule procedure.
Given the previously discussed features of the implementation of scheduling algo-
rithms, it seems possible to determine the number of criteria that characterize planning
tasks.
Conclusion
Features of scheduling algorithms used in modern production planning systems were
identified in the article. Knowing the features of the functioning of the corresponding
59
algorithms at different stages of the life cycle of the schedule makes it possible to bal-
anced 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 direc-
tion 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).
References
1. Anichkin A. S., Semenov V. A. Actual sheduling theory models and methods. Works of ISP
RSA. Vol.26. No.3. pp. 5 – 6, 2014.
2. Chernenko A. A. Features of increasing the efficiency of business processes in enterprises
of various types by using the capabilities of industrial information systems. New technolo-
gies of MSTU. Vol.4. pp. 64 – 66, 2014.
3. Lazarev A. A., Gafarov E. R. Scheduling theory. Tasks and algorithms. M.: MSU of Lo-
monosov. pp. 40 – 46, 2011.
4. Lazarev A. A. Scheduling theory. Estimates of the absolute error and the scheme for the
approximate solution scheduling theory problems. M.: MPTI. pp. 93 – 96, 2008.
5. Shkurba V. V. Calendar planning. Constructive optimization. Automation & Telemechan-
ics. Vol. 10. pp. 122 – 125, 2010.
6. Lavalle Steven M. Planning algorithms. Cambridge University Press. pp. 236 – 237, 2006.
7. Chernenko A. A. Production schedule management in the information system of operative-
calendar planning. Bulletin of the Adyghe State University. Ser. Natural-mathematical and
technical sciences. Vol.3. No.206. pp. 122–128, 2017.
8. ISA – 95.00.01 – CDV3 Enterprise – Control System Integration, Part 1: Models and Ter-
minology. Research Triangle Park, North Carolina, USA: International Society of Automa-
tion, 2008.
9. Williams Theodore J. The Purdue enterprise reference architecture. Computers in industry.
Vol.24. No.2. pp. 141 – 158, 1994.
10. Moore J. M. An n job one machine sequencing algorithm for minimizing the number of late
jobs. Manag. Sci. Vol.15. No.1. pp. 102 – 109, 1968.
11. Sevastyanov S. V. Geometry methodes and effective algorithms in scheduling theory: dis-
sertation of the doctor of physical and mathematical sciences. Novosibirsk: Sobolev RSA
Institute, 2000, pp. 37 – 41.
12. Liqing Li, Hai Lu, Sichuan Mianyang. Integrated Production Planning and Scheduling Sys-
tem Design. IEEE. pp. 732 – 734, 2017.
13. Dasgupta S., Papadimitriu H., Vazirni U. Algorithms. M.: MCIMO. pp. 106 – 108, 2014.
14. Pinedo Michael L. Scheduling: Theory, Algorithms, and Systems. Springer Science & Busi-
ness Media. pp. 209 – 212, 2008.
15. Smolyar L. I. Discrete production operative scheduling models. M.: Science. pp. 192 – 193,
1978.
16. Velychko O., Gordiyenko T. Methodologies of expert's competence evaluation and group
expert evaluation. Article in Metallurgical and Mining Industry. pp. 262 – 264, 2015.
17. Cormen Thomas H. Algorithms unlocked. The MIT Press, Cambridge, Massachusetts. pp.
237 – 237, 2013.
18. Levitin A. A. Algorithms. Introduction into development and analyse. M.: Villiams. pp. 283
– 284, 2006.
60
19. Zagidullin R. R. Engineering Planning. Stariy Oskol: TNT. Pp. 315 – 319, 2017.
20. Farkas G. A., Martinek P. Production plan scheduling on SMT manufacturing lines. IEEE
23rd International Symposium for Design and Technology in Electronic Packaging
(SIITME). pp. 103 – 104, 2017.