Algorithm for Generation of Production Plan

Radda IurevaDepartment of Control Systems and Robotics, ITMO University, St. Petersburg, Russia,

Pavel Korepanov, Department of Control Systems and Robotics, ITMO University, St. Petersburg, Russia

Arkady IvaschenkoDepartment of Control Systems and Robotics, ITMO University, St. Petersburg, Russia

Artem KremlevDepartment of Control Systems and Robotics, ITMO University, St. Petersburg, Russia

Sergey VlasovDepartment of Control Systems and Robotics, ITMO University, St. Petersburg, Russia

Yuri AndreevDepartment of Control Systems and Robotics, ITMO University, St. Petersburg, Russia

Abstract  The paper describes usage approaches of developed algorithms for generation of production plan based on automatic creation of master production and operation schedules, also focusing on efficiency evaluation methods. Based on the goals, development is the task of Industry 4.0, which determines its relevance.

Keywords: automation, Industry 4.0, optimization, simulation model, process chart, master production schedule, operative schedule

© The Authors, published by CULTURAL-EDUCATIONAL CENTER, LLC, 2020

This work is licensed under Attribution-NonCommercial 4.0 International

I. Introduction

The emergence of algorithms and tools for generation of production plans contributed to change in technological production modes. With handicraft and manufacture types of production, there was no direct need for such production tools. Manufacturing orders and process charts had not regulated the technological process.

After the industrial revolution, there was a transition to mass production. At the same time, there was a necessity for planning manufacturing processes to prevent downtime and machine-down of assembly lines. Changes in output products occurred quite rarely, so schedule of process for a long time remained relevant and unchanged Theuer et al. (2011). Since it was rarely necessary to compose and modify it, this task was usually carried out through manual labor.

In modern conditions within the confines of “Industry 4.0” preference is given to flexible industries. Such preference means that final products are produced in small batches with specified technical characteristics.(Iureva et al. (2019)) To achieve this, operational production planning is required, which allows quick reconfiguration of processes. At the same time, within framework of planning optimization tasks should be solved in order to reduce production costs and production time.

It is challenging to organize changes in production process, a redistribution of resources with manual planning. In this case, the efficiency prediction lays in responsibility of contractor and performed without formal fixation of results (Iureva et al. (2018)). This obstacle does not allow verification of results and processes, which poses enormous risks. The above factors impede production flexibility and bring in human factor errors. It should be noted that in case of “manual” scheduling requires an individual specialist and results of his work are extremely difficult to integrate into modern economic models. Another way to solve this problem is to use over-priced simulation soft-ware. However, working with this kind of software required highly qualified specialists (Theuer et al. (2011); Pinedo (2011)). The cost of software and specialists often makes it unacceptable for small businesses; however, exceptions depending on the type of product. It is also important to note that simulation modeling often has redundant functionality and requires significant computational capabilities, which make long-term planning time consuming and complicated computational process.

The purpose of this work is to develop a variety of production planning algorithm. In this case, the algorithm should have an acceptable computational complexity, scalability, simple integration into the information systems of production and its environment (Liu et al. (2018); Esteban et al.(2018)). Also, algorithm should allow solving optimization problems in different ways in order to determine effect of number of specified production resources on the production time, allow determining the required number for the implementation of plan within specified time frame to automatically generating Operative and Master Production Schedules.

A separate problem is the consideration of the limitation sand effects imposed by real production. The main are (Gjeldum et al. (2007); Hahn et al. (2018)):

• Variable quantitative and qualification composition of staff.

• Accounting work of each worker.

• Equipment failure.

• Preventive maintenance.

• Delays in logistics operations.

• Mutually exclusive nature of certain types of work.

• The second paper section dedicated to the problem statement and formal requirements.

• The third describes approaches to the generation production plan, reasons for choosing these approaches.

• The fourth section is about Master Production Schedule, fund, their classification and methods of calculation.

• Fifth dedicated to generating of Operative Schedule, imitation model and optimization methods.

• Last section describes experimental algorithm test.

II. Problem Statement

To formalize the task of building production plans, let’s introduce model of input 1 and output 2 data for the algorithm.

Table 1. Formal Input Data

Type of dataDescription
Production planList of consistently planned production:type and amount of productBeginning and finishing time of productionplan execution
Resources demandsAssignment of operations on an assemblyline workstationsStaff requirements
Production processOperations, operational time, a sequenceof operations, dependency on blanks
ProductionvariablesWorkshop (amount of assembly lines andworkstations)Staff (qualification, work gang, amount)

Initial data includes production plan, process charts, production variable and requirements for production re-sources. Production plan includes nomenclature and number of products planned for manufacturing, as well as deadlines for plan implementation.

Table 2. Formal Output Data

Type of dataDescription
Production planGantt diagram: manufacturing, every production operation, operations forming blanksDiagram of loading blanks into production
An intensity of resources usageStaff workload (average and personal

Initial data includes production plan, process charts, production variable and requirements for production re-sources. Production plan includes nomenclature and number of products planned for manufacturing, as well as deadlines for plan implementation. Production routings describe producing processes for manufacture of each product and include required operations to, and their sequence, components, and blanks necessary to perform each operation. Production parameters include description of capacity, a swell as employment size, including their qualifications, and material production resources. Requirements for resources describes where can operation be performed, as well as requirements for staff and material resources.

It is necessary to build the algorithm that provides:

• Calculation of time of production of individual units of production to fulfill production plan.

• Calculation of the time of beginning and finishing of every operation under conditions of existing resources limitations.

• Determination of average resource utilization rates.

• The developed algorithm should provide solution to some optimization problems:

• Determining the influence of the number of specified production resources on the plan deadline.

• Determining quantity influence of all production resources on the plan implementation period.

• Determining a necessary amount of all production resources for the plan implementation in a given period.

III. Approach Description

Planning task has tremendous computational complexity since it is NP-compete problem with vast number of variables. Therefore, planning task is divided into two parts, where the result of the first (Master Production Schedule)is the input data for the second (Operative Schedule). Master Production Schedule — focused on drawing up long-termproduction plans, without specifying resource usage. Operative Schedule is primarily focused on system of equation sand inequalities that describes production process in detail. This partitioning allows to divide scheduling task Fig.1 into two closely related subtasks and significantly reduce overall computational complexity by iteratively searching for the final production plan, when approximate Master Production Schedule is first made, then its correctness is carried out within Operative Schedule, and in case of discrepancy — adjustment is in progress.

Figure 1. Interaction of two planning approaches.

IV. Master Production Plan

A. Funds

Analysis of production plan is carried out in terms of available production resources, referred to as funds. There are four types of funds allocated throughout system:

• Flow fund — description of resource described by a consistency of consumption.

• Financial fund — description of financial resource and its changes.

• Stock fund — description of resource which could be stored and accumulated through time.

• Time fund — description of time resources as main and nonrenewable.

B. Calculations Methods of the Funds

To generate master production schedule was chosen evaluation model of funds, the point is to calculate the time funds determining time ratio use of resources and amount of them with different types of input data, and further comparative analysis.

As can be seen from the descriptions of funds, they intersect with each other in the process of calculation, based on this, a simple dependency was singled out, which allows determining the efficiency of the generated production plan: Fa ≥ Fc ≥ Fi.

Table 3. Types of Calculations of the Funds

Ideal fundCalculation of distribution of resources on a time axis based on process chart within order nomenclature or one unit of productionFa
ConsumedfundCalculation of distribution of resources on a time axis based on process chart, lost and overhead used resources within order nomenclature or one unit of productionFc
Available fundCalculation of distribution of resources on a time axis based the on number of available resources within order nomenclature or one unit of productionFi

Visualization of time funds is carried out using graphing, where the area under the graph shows the volume of the funds under consideration. Several ways were proposed to cover all possible resources and calculate corresponding funds Tab. 3. Time funds visualization is carried out using graphing, where the area under the graph shows the volume of the funds under consideration.

C. Fund Relations Model

To define relationships, patterns and consequences in the model was developed a model of temporary production assets using the tools of set theory and category theory Fig. 2.

Figure 2. The formal fun relations model.

V. Operative Schedule

The developed algorithm based on a new method of generating a production plan allows automatically obtain production process schedule and information on launch of blanks into production based on input data with or with-out restrictions on resources, generation Master Production Schedule, matching absolute (calculated as deviation from null) and astronomic times.

A. Math Model

Production process modeling. The planning algorithm based on the technological process representation in the form of a system of equations and inequalities, the solution of which is the production plan. The process model is characterized by the following:

• System of equations defined on discrete set of numbers, which linearly models the working time in hundredths of an hour (conversion to real-time is performed out at stage of data output from algorithm).

• Technological operations are described by expressions opt2 = opt1 + dt, where opt1 is start time of operation, opt2 is finish time of operation, dt is duration of operation, but operation is not.

• Sequence of operations described by inequalities of form op1t≤ op2t1, where op1t2 is finish time of operation 1, op2t1 is start time of operation 2, these inequalities make it possible to commit cause-­effect relationships unambiguously.

• To optimize the algorithm, formation and calculation of system of equations is performed in stages, as groups of operations corresponding to independent units of products added to system of equations of operations.

An example of a production model of four operations Fig. 3 formed out at stage of data output from the algorithm).

Figure 3. The system of equations and inequalities.

Production resources modeling. Generation of the plan described before proceeds in one step, but to account for resources in the system restrictions imposed are set by them and which should be considered in each pass of the algorithm, representation of it in the form of the system of equations and inequalities Fig. 4.

Figure 4. System of equation and inequalities with resources restrictions.

B. The Developed Algorithm

The general principle of the algorithm. The search for a solution to the system of equations is carried out according to the algorithm shown in Fig. 5 and Tab. 4.

Table 4. Integrated Algorithm Steps

1Compare the number of planned operationsand the total number of operations.
2If all operations are planned.
2.1If there are no free variables and there are noplanned products.
2.1.1Add the following unit to the system of equations.
2.2Get a list of parameters of the system of equations sorted in ascending order (free variables for which values, not variables give all constraints).
2.3Substitute the parameter with the minimumvalue. If there are several such values, then thechoice is made randomly or by the specifiedrule.
2.4Simplify the system of equations. It consistsof calculating all possible expressions, substituting calculated bound variables, removingredundant inequalities. Simplification checks the correctness of the invariants
3If all operations are planned — work of algorithm ends.

Any solution obtained by the presented system of equations is the correct plan for organization of production, within which time of beginning and finishing of operations are determined.

Figure 5. The schedule generation algorithm.

The algorithm with restrictions on resources.

This algorithm is a modification of the schedule generation algorithm without taking the limitations of production resources into account. It allows considering:

• The presence of sets of similar work resources (equipment, employees of a given qualification) that may be required to perform operations.

• Organization of assembly lines where operations performed, and appropriate restrictions imposed on sequence and simultaneity of operations.

The introduction of resources into the basic algorithm is carried out locally within the several steps 5.

Table 5. Integrated Algorithm Steps

1Added binding operations of the added unit of production to the required resources.
2When defining parameters and their values, added accounting for constraints imposed by resources.
3Added loading of calculated values of variables into resource models, which changes their contribution to the dynamic system of equations.

The main difference of the modified algorithm is that the system of equations dynamically changes after each planned operation. For example:

• At the first station of the assembly line a unit of production was loaded, for which it is necessary to perform operations 1, 2 and 3 consistently. In this case, the fact of “loading” means that operation 1was planned.

• This means that at the workstation only operation 1can be performed. At the same time, it is impossible to load other units of production on the assembly line until stage one is released (operations 2 and 3are planned).

• Blocking of assembly line within the framework of the model is described by adding to the system of inequalities additional restrictions on operations that are not loaded into the assembly line.

The result of implementation of operative scheduling is a set of integers — time for which the operation is performed, that is, a deviation from null. Since organization of any production involves some features, such as:

• Availability of working time and time of rest intervals.

• Complex organization of work timetable.

• Availability of days off, holidays.

Then calendar software component (CSC) converting ab-solute time to astronomical shown in Fig. 6. CSC takes a user-defined start date, deviation and data on work timetable as input data for calculation of working time intervals:

• A date is checked for presence of working intervals.

• For each interval duration is summed with current deviation and astronomical time.

• If, specified deviation is exceeded, result is returned.

In case of absence of working periods, return to point 1.

Figure 6. Conversion time module state machine.

C. Ways of Optimization

An example of optimization could be a random selection of next operation in scheduling process; this choice is possible only in cases of simultaneous execution of several independent operations. Thus, variability achieved in which from different implementations, the best option is chosen. The figure shows a process chart of the product and two plans that built as a result of a random selection of operations. As can be seen from the Fig. 7, the first plan is more optimal in time and resources than the second one.

Figure 7. Example of proof for exhaustion illustrating two ways of realization production plan in terms of one process chart.

Despite that proof by exhaustion model is universal, at the same time in some cases combinatorial complexity becomes close to an impossibility of calculation. To solve this problem was introduced the concept of special optimization mathematical models. Limiting the functionality reduce combinatorial complexity making it possible to calculate larger tasks. For example, on productions with assembly lines, there is a balancing problem between minimizing takt time and needed operation durations. To solve this problem is used assembly line balancing method, that allows solving this specific problem: determining balance between takt time, staff workload and operation durations.

VI. Experiment

To solve the problem of determining the optimal number of production and staff resources, an algorithm firstly runs without production restrictions — the results of its work determined by the minimum possible time to complete the production plan.

Further, on the basis of the process chart, the minimum required the composition of resources for the implementation of the plan determined as the maximum resource requirements for single operation. After that, an iterative algorithm is launched.

The algorithm stops working when the execution time of the plan reaches the minimum value. The output o the algorithm is a graph with the dependence of the execution time of the plan on the number of production and staff resources. If it is necessary to execute the plan at the specified time, the algorithm stops working when the execution time reaches the specified limit.

After receiving production plan, determined by minimal execution time, appears to need to bind theoretical calculations repelling from the execution time of operations to a astronomical time, considering days off, holidays and work timetables of involved staff. From the point of view of cost and time of storage, it is made to maximize an efficiency of distribution of production capacity involve din the execution of the order. It leads to an opportunity to increment the number of orders executed in parallel for the avoidance of idle production resources when the main order must be completed by a specific deadline or decreasing of time of accomplishment each order.

After finishing optimization, the production plan, correlated with staff work timetable, could be used more effectively. The result of the work presented in the form of Gantt diagram Fig.8.

Thus, the developed algorithm allows to determine:

• Operative schedule.

• Master production schedule.

• Map of planned absolute time on astronomic.

VII. Conclusions

The paper presents the algorithm approaches for automatic generation of production plan based on Master Production Schedule and Operative Schedule (including start-up schedule for manufacturing of products and blanks) taking into account staff and production resources. The operation schedule based on problem parameterization of constructing a plan in the form of a system of linear inequalities and equations, followed by iterative resolution of the resulting system of inequalities. Master production schedule use as basis evaluation model of funds. Optimization algorithms have been partially developed to determine the need for production resources for the implementation of the plan within a specified time frame. A software implementation of the developed algorithm was carried out and tested. The test results show the performance of the proposed approach. Also, within of above planning methods was solved the separate problem — consideration of the limitations and effects imposed by real production.


This work was financially supported by Government of Russian Federation (Grant 08–08) and by the Ministry of Science and Higher Education of Russian Federation, passport of goszadanie no. 2019–0898.


 [1]   Theuer, H. and Leo, A. K. Productivity Management, 2011, no. 16(4), pp. 37–45

 [2]   Pinedo, M. L. Planning and Scheduling in Manufacturing and Services: Second Edition, Springer, New-York, pp. 1 536

 [3]   Gjeldum, N., Tufekcic, D., and Veza, I. Modeling of control loop in production scheduling and inventory level control, in Annals of DAAAM and Proceedings of the International DAAAM Symposium, 2007, pp. 297–298

 [4]   Hahn Gerd, J. and Brandenburg, M. A sustainable aggregate production planning model for the chemical process industry, in Computers and operations research, 2018, vol. 94, pp. 154–168

 [5]   Liu, Q., Dong, M., and Chen, F. F. Single-­machine-based joint optimization of predictive maintenance planning and production scheduling, in Robotics and computer-­integrated manufacturing, 2018, vol. 51, pp. 238–24

 [6]   Esteban, D. J., Handl, J., and Xu, D. Integrating meta-heuristics, simulation and exact techniques for production planning of a failure-­prone manufacturing system, in European journal of operational research, 2018, vol. 266(3), pp. 976–98

 [7]   Tanada, H., Ikemoto, T., Masutani, R., Tanaka, H., and Takubo, T. Integrated process planning and scheduling: an enhanced ant colony optimization heuristic with parameter tuning, in Journal of intelligent manufacturing, 2018, vol. 29(3), pp. 585–601

 [8]   Iureva, R. A.Kremlev, A. S.Margun, A. A.Vlasov, S. M.and Timko, A. S. Measures to design secure cyber-­physical things (Book Chapter), in Smart Innovation Systems and Technologies, 2019, vol. 142, pp. 315–322

 [9]   Iureva, R. A.Andreev, Y. S.Iuvshin, A. M.and Timko, A. S. Information security of Smart Factories, in Journal of Physics Conference Series, 2018, DOI: 10.1088/1742-6596/1015/4/042015