# A Dynamic Approach to Multi-stage Job Shop Scheduling in an Industry 4.0-Based Flexible Assembly System

Dmitry Ivanov, Alexandre Dolgui, Boris Sokolov

► To cite this version:

Dmitry Ivanov, Alexandre Dolgui, Boris Sokolov. A Dynamic Approach to Multi-stage Job Shop Scheduling in an Industry 4.0-Based Flexible Assembly System. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2017, Hamburg, Germany. pp.475-482, 10.1007/978-3-319-66923-6_56 . hal-01666225

HAL Id: hal-01666225

https://inria.hal.science/hal-01666225v1

Submitted on 18 Dec 2017

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# A dynamic approach to multi-stage job shop scheduling in an Industry 4.0-based flexible assembly system

Dmitry Ivanov¹*, Alexandre Dolgui², Boris Sokolov³,⁴

¹ Berlin School of Economics and Law, Department of Business Administration
10825 Berlin, Germany

E-Mail: divanov@hwr-berlin.de

² Automation, Production and Computer Sciences Dept.
IMT Atlantique (former Ecole des Mines de Nantes)

LS2N - CNRS UMR 6004 La Chantrerie
4, rue Alfred Kastler - B.P. 20722
F-44307 NANTES Cedex 3, France

Alexandre.dolgui@imt-atlantique.fr

³ St. Petersburg Institute for Informatics and Automation of the RAS (SPIIRAS)
V.O. 14 line, 39 199178 St. Petersburg, Russia;

E-Mail: sokol@iias.spb.su

⁴ ITMO University, St. Petersburg, Russia

E-Mail: sokol@iias.spb.su

**Abstract.** Industry 4.0 technology is based on the concepts of flexibility and dynamic assembly system design. This enables new production strategies and creates new challenges for job shop scheduling. In particular, manufacturing processes for different customer orders may have individual machine structures whereas the flexible stations are able to execute different functions subject to individual sets of operations within the jobs. This study develops a control approach to job shop scheduling in a customized manufacturing process and job sequencing of operations within the jobs. The developed approach presents a contribution to flexible distributed scheduling in the emerging field of Industry 4.0-based innovative production systems.

**Keywords:** assembly system; scheduling; dynamics; Industry 4.0; control

## 1 Introduction

Individualization of products frequently requires different technological chains of operations in the manufacturing processes. Industry 4.0 technology enables new production strategies with the use of cyber-physical system principles based on highly customized assembly systems with flexible manufacturing process design (Erol et al. 2016, Battaïa et al. 2015, Oesterreich and Teuteberg 2016, Kumar et al. 2016, Nayak et al. 2016). Such innovative production strategies represent new challenges and opportunities for scheduling. In particular, manufacturing processes for different customer orders may have individual station structures whereas the flexible stations are
able to execute different functions subject to individual sets of operations within the jobs (Weyer et al. 2015, Ivanov et al. 2016, Nayak et al. 2016, Zhong et al. 2017).

Practical environments for applications of scheduling and sequencing models and algorithms to customized assembly systems are multi-facet. With the help of smart sensors and plug-and-produce cyber-physical systems, the stations in the assembly system are capable to change the operation processing and setup sequences according to actual order incoming flows and capacity utilization (Otto et al. 2014, Theorin et al. 2017). In the front opening unified pods technology in semiconductor industry, robots are used in real-time operation sequencing. Robots read the information about the products from sensors and tags and decide flexibly where to forward a wafer batch next (Mönch et al. 2012).

Recent literature constituted principles and approaches to design and scheduling of flexible reconfigurable assembly systems with the focus on balancing, scheduling and sequencing (Boysen et al. 2007, Chube et al. 2012, Delorme et al. 2012, Battaïa and Dolgui 2013, Battaïa et al. 2017). In these studies, models and methods for solving problems related to the optimization of assembly system performance intensity for sets of flexibly intersecting operations have been presented. The studies by Ivanov et al. (2012) and (2016) showed a wide range of advantages regarding the application of control-theoretic models in combination with other techniques to scheduling.

It can be observed that in previous studies the selection of the process structure and respective station functionality for operations execution have been considered in isolation. In many real life problems such an integration can have a significant impact on process efficiency (Bukchin and Rubinovitz, 2003). The problem of simultaneous structural-functional synthesis of the customized assembly system is still at the beginning of its investigation (Levin et al. 2016). Previously isolated gained insights into job shop scheduling, scheduling and sequencing with alternative parallel machines can now be integrated in a unified framework. Three most important prerequisites for such an integration, i.e., data interchange between the product and stations, flexible stations dedicated to various technological operations, and real-time capacity utilization control are enabled by Industry 4.0 technology.

## 2 Problem statement

Consider an assembly system that is able to react flexibly at customer orders and produce individualized products. Customers generates orders (jobs) each of which has an individual sequence of technological operations. Each station is dedicated to a set of technological operations. Since multiple stations may perform the same operations, a number of alternatives of job scheduling and sequencing exist subject to actual capacity utilization, machine availability, time-related and cost-related parameters.

The independent jobs consist of a chain of operations whereas the station sequence can differ from different jobs. All jobs are assumed to be available for processing at time zero. Each station is capable of handling only one operation at a time. Processing speed of each station is described as a time function and is modelled by material flow functions (integrals of processing speed functions) and resulting operation processing
time is, in general, dependent on the characteristics of the station. The following performance indicators (objective functions) are considered: Throughput, Lead-time, Makespan, Total lateness, Equal utilization of stations in the assembly line.

The first task is to assign the operations to stations at each stage of the technological process. The second task is to sequence the operations at the stations. Note that both tasks will be solved simultaneously.

Consider the following sets:

$\bar{B} = \{\bar{B}^{(i)}, i \in \bar{N}, \bar{N} = (1, \dots, \bar{n})\}$ is the set of customer orders (jobs)

$D = \{D_{\mu}^{j}, \mu \in \bar{S}, \bar{S} = (1, \dots, s_{i})\}$ is the set of manufacturing operations

$M = \{M^{j}, j \in N, N = (1, \dots, n)\}$ is the set of stations

In terms of scheduling theory, we study a multi-objective, multi-stage job shop scheduling problem with alternative machines at each stage of the technological process with different time-dependent processing speed, time-dependent machine availability, and ordered jobs where job splitting is not allowed. Examples of such problems can be found in the studies by Kyparisis & Koulamas (2006) and Tahar et al. (2006). The peculiarity of the problem under consideration is the simultaneous consideration of both process design structure selection and operation assignment. On one hand, an assignment problem is discrete by nature and requires the introduction of binary variables, i.e., discrete optimization techniques can be correctly used here. At the same time, a non-stationary operation execution can be accurately described in terms of continuous optimization. An additional peculiarity of such simultaneous consideration is that both the machine structures and the flow parameters may be uncertain and change in dynamics and are, therefore, non-stationary.

# 3 Dynamic approach to job shop scheduling

This section considers the principles of the modelling approach. The first principle is to use fundamental results gained in the optimal program control theory for modelling the scheduling decisions. The second principle is the computational procedure based on the maximum principle and Hamiltonian maximization.

## 3.1 Modelling approach

Lee and Markus (1967) and Moiseev (1974) proved optimality and existence control conditions for linear non-stationary finite-dimensional controlled differential systems with the convex area of admissible control. We formulate the scheduling model in the form of such a system.

A particular feature of the proposed approach is that the process control model is presented as a non-stationary dynamic linear system while the non-linearity will be transferred to the model constraints. This allows us to ensure convexity and to use interval constraints. Eqs (1)-(8) exemplify process control models, constraints, and objective functions.
$$ \frac{dx_{i\mu}^{(o)}}{dt} = x_{i\mu}^{(o)} = \sum_{j=1}^{n} \varepsilon_{ij}(t) u_{i\mu j}^{(o)}(t) \quad (1) $$

$$ \frac{dx_{i\mu j}^{(f)}}{dt} = x_{i\mu j}^{(f)} = u_{i\mu j}^{(f)} \quad (2) $$

$$ \sum_{i=1}^{\bar{n}} \sum_{\mu=1}^{s_i} u_{i\mu j}^{(o)}(t) \le 1, \quad \sum_{j=1}^{n} u_{i\mu j}^{(o)}(t) \le 1 \quad (3) $$

$$ \sum_{j=1}^{n} u_{i\mu j}^{(o)} \left[ \sum_{\alpha \in \Gamma_{i\mu}} (a_{i\alpha}^{(o)} - x_{i\alpha}^{(o)}) + \prod_{\beta \in \Gamma_{i\mu}} (a_{i\beta}^{(o)} - x_{i\beta}^{(o)}) \right] = 0 \quad (4) $$

$$ 0 \le u_{i\mu j}^{(f)}(t) \le c_{i\mu j}^{(f)} \cdot u_{i\mu j}^{(o)} \quad (5) $$

$$ \sum_{i=1}^{\bar{n}} \sum_{\mu=1}^{s_i} u_{i\mu j}^{(f)}(t) \le \tilde{R}_{j}^{(f)} \cdot \xi^{(f)}(t) \quad (6) $$

$$ J_{1}^{(o)} = \frac{1}{2} \sum_{i=1}^{\bar{n}} \sum_{\mu=1}^{s_i} (a_{i\mu}^{(o)} - x_{i\mu}^{(o)}(T_f))^2 \quad (7) $$

$$ J_{2}^{(o)} = \sum_{i=1}^{\bar{n}} \sum_{\mu=1}^{s_i} \sum_{j=1}^{n} \int_{T_0}^{T_f} \alpha_{i\mu}^{(o)}(\tau) u_{i\mu j}^{(o)}(\tau) d\tau \quad (8) $$

The processing dynamics of an operation is presented in Eq. (1). In the case of station availability (i.e., $\varepsilon_{ij}(t)=1$) and control $u_{i\mu j}^{(o)}(t)=1$ at the time point t, the operation $D_{\mu}^{(i)}$ is assigned to the machine $M^{(j)}$. The continuous time allows to represent the execution of the operations at each time point, and therefore, to obtain additional information about the execution of the operations. The state variable $x(t)$ accumulates the executed (processed) volume of the considered operation. Constraints (3) and (4) determine the precedence relations in the manufacturing process and assignment rules (i.e., how many operations may be processed at a station simultaneously), respectively. Constraints (3) determine the „and“ and „or“ precedence relations by blocking the operation $D_{\mu}^{(i)}$ until the previous operations $D_{\alpha}^{(i)}, D_{\beta}^{(i)}$ have been completed.

Eq. (2) consists in the dynamic representation of the material flows resulting from the execution of the operations on the machine $M^{(j)}$. The meaning of Eq. (2) is very close to a system dynamics model to balance the flows in a system. However, the proposed approach also considers the strictly defined logic of the execution of the operations (Eq. 4). Moreover, the models of operations control (Eq. 1) and flow control (Eq. 2) are interlinked linearly by Eq. (5) and the conjunctive system (see Ivanov et al. 2016).
The control variable $u_{ij}^{(f)}(t)$ is not a binary variable like $u_{ij}^{(o)}(t)$, but it is equal to the processed flow volume $x_{ij}^{(f)}$ at each time point $t$. The model (2)-(5)-(6) uses the assignment results from the model (1)-(3)-(4) in the form of the control variables $u_{ij}^{(o)}(t)$ and extends them by the actual processing speed of the machines subject to the constraints (5)-(6). Inequalities (5) use the assignment decisions $u_{ij}^{(o)}(t)$ and consider the actual processing speed $c_{ij}(t)$ of the stations $M^{(j)}$. Constraints (6) reflect that the processing speed is constrained by $\tilde{R}_j^{(f)}$ taking into account the lower and upper bounds of some perturbation impacts $0 \le \xi^{(f)}(t) \le 1$ which may decrease the capacity availability.

The objective function $J_1^{(o)}$ (Eq. (7) characterizes the on-time delivery subject to accuracy of the accomplishment of the end conditions, i.e., the volume of the completed operations by the time $T_f$. The objective function (8) minimizes total maximum lateness using penalties. The penalty function $\alpha_{ij}^{(o)}(\tau)$ is assumed to be known for each operation. Note that the constraints (3)–(6) are identical to those in mathematical optimization models. However, at each $t$-point of time, the number of variables in the calculation procedure is determined by the operations, for which precedence and machine availability conditions are fulfilled. This allows us to start description of the second principle of the developed approach, i.e., the computational procedure.

## 3.2 Computational principle

The calculation procedure is based on the application of Pontryagin's maximum principle. The modelling procedure essentially reduces the problem dimensionality at each instant of time due to connectivity decreases. The problem dimensionality is determined by the number of independent paths in a network diagram of manufacturing operations and by current constraints. In its turn, the degree of algorithmic connectivity depends on the dimensionality of the main and the conjugate state vectors at each point of time. If the vectors are known, then the schedule calculation may be resumed after the removal of the “inactive” constraints.

First, on the basis of the Pontryagin's maximum principle and corresponding optimization algorithms, the original problem of optimal control is transformed to the boundary problem. The maximum principle permits the decoupling of the dynamic problem over time using what are known as adjoint variables or shadow prices into a series of problems each of which holds at a single instant of time. Second, the optimal program control vector $\mathbf{u}(t)$ and the state trajectory $\mathbf{x} = \mathbf{f}(\mathbf{x}, \mathbf{u}, t)$ should be determined so that the desired values of the objective functions are obtained as an analogy to goal programming.

At each time instant, the assignment decisions consider only the gray colored operations subject to some available (“competing”) machines, i.e., the large-scale multi-dimensional combinatorial matrix is decomposed. The assignment of a machine $M^{(j)}$
to the execution of the operation $D_{\mu}^{(i)}$ can be described by the piecewise continuous function $u_{i\mu j}^{(o)}(t)$ that becomes equal to 1 in the case of an assignment. As such, the constructive possibility of discrete problem solving in a continuous manner occurs. Besides this, the required consistency between optimal program control and linear programming or integer programming models is ensured – although the solver works in the space of piecewise continuous functions, the control actions can be presented in the discrete form.

In the proposed dynamic scheduling model, a multi-step procedure for scheduling is implemented. At each instant of time while calculating solutions in the dynamic model with the help of the maximum principle, the linear programming problems to allocate jobs to resources and integer programming problems for (re)distributing material and time resources are solved with mathematical programming algorithms.

1. Initial solution $\bar{\mathbf{u}}(t), t \in (T_0, T_f]$ (a feasible control, in other words, a feasible schedule) is computed with a heuristic algorithm.

2. As a result of the dynamic model run, $\mathbf{x}(t)$ vector is received. Besides, if $t = T_f$ the objective function values are calculated.

3. The transversality conditions are evaluated.

4. The conjugate system is integrated subject to $\mathbf{u}(t) = \bar{\mathbf{u}}(t)$ and over the interval from $t = T_f$ to $t = T_0$. For the time $t = T_0$, the first approximation of the conjunctive vector is obtained as a result.

5. From the time point $t = T_0$ onwards, the control $\mathbf{u}(t)$ is determined for different iterations. In parallel with the maximization of the Hamiltonian, the main system of equations and the conjugate one are integrated. The maximization involves the solution of several mathematical optimization problems at each time point.

The assignments (i.e., the control variables) are used in the flow control model by means of the constraints (5). At the same time, the flow control model (2), (5)-(6) influences the operations execution control model (1), (3), (4) through the transversality conditions, the conjunctive system, and the Hamiltonian function. A methodical challenge in applying the maximum principle is to find the coefficients of the conjunctive system which change in dynamics. One of the contributions of this research is that these coefficients can be found analytically (Ivanov et al. 2016). The coefficients of the conjunctive system play the role of the dynamical Lagrange multipliers as compared with mathematical programming dual formulations.

# 4 Conclusions

Industry 4.0 technology enables new production strategies that require highly customized assembly systems. The ultimate objective of those systems is to facilitate flexible customized manufacturing at the costs of mass production. Such innovative production strategies represent a number of new challenges and opportunities for short-term job scheduling. In particular, manufacturing processes for different customer orders
may have individual machine structures whereas the flexible stations are able to exe-
cute different functions subject to individual sets of operations within the jobs. There-
fore, a problem of simultaneous structural-functional synthesis of the customized
assembly system arises.

This study develops an optimal control model and an algorithm for job shop
scheduling in an Industry 4.0-based flexible assembly line. In contrast to previous
studies which assumed fixed process design, our approach is capable of simultaneous-
ly designing manufacturing process in regard to available alternative stations, their
current capacity utilization and processing time, and sequencing jobs at the stations.

The developed framework is also a contribution to scheduling theory. The formula-
tion of the scheduling model as optimal program control allows including into consid-
eration a non-stationary process view and accuracy of continuous time. In addition, a
wide range of analysis tools from control theory regarding stability, controllability,
adaptability, etc. may be used if a schedule is described in terms of control.

5 References

1. Battaïa, O., A. Dolgui. (2013). A taxonomy of line balancing problems and their solution approaches, *International Journal of Production Economics*, 142(2), 259-277.

2. Battaïa, O., Dolgui, A., Guschinsky, N. (2015). Integrated process planning and system configuration for mixed-model machining on rotary transfer machine. *International Journal of Computer Integrated Manufacturing*, published online dx.doi.org/10.1080/0951192X.2016.1247989

3. Battaïa, O., Dolgui, A., Guschinsky, N. (2017). Decision support for design of reconfigurable rotary machining systems for family part production. *International Journal of Production Research* 55(5),1368-1385.

4. Boysen, N. A., Fliedner, M. and Scholl, A. 2007. A classification of assembly line balancing problems. *European Journal of Operational Research*, 183, 674–693.

5. Bukchin, J., Rubinovitz, J. (2003). A weighted approach for assembly line design with station paralleling and equipment selection. *IIE Transactions*, 35, 73–85.

6. Chube, A., L. Benyoucef, and M.K. Tiwari (2012) An adapted NSGA-2 algorithm based dynamic process plan generation for reconfigurable manufacturing system. Journal of Intelligent Manufacturing, 23(4), 1141–1155.

7. Delorme X., A. Dolgui, M.Y. Kovalyov (2012) Combinatorial design of a minimum cost transfer line, *Omega - International Journal of Management Science*, 40(1), 31-41.

8. Dolgui, A., Guschinsky, N., Levin, G. (2009). Graph approach for optimal design of transfer machine with rotary table. *International Journal of Production Research*, 47(2), 321–341.

9. Erol, S., A. Jäger, P. Hold, K. Ott, W. Sihn (2016). Tangible Industry 4.0: A Scenario-Based Approach to Learning for the Future of Production. *Procedia CIRP*, 54, 13-18.

10. Ivanov, D., Sokolov B., Dolgui, A. (2012). Applicability of optimal control theory to adaptive supply chain planning and scheduling, *Annual Reviews in Control*, 36, 73–84.

11. Ivanov, D., Sokolov, B., Dolgui, A., Werner, F., Ivanova, M. (2016). A dynamic model and an algorithm for short-term supply chain scheduling in the smart factory Industry 4.0. International Journal of Production Research, 54(2), 386-402.

12. Kumar, M., Graham, G., Hennelly, P., Srai, J. (2016) How will smart city production systems transform supply chain design: a product-level investigation. *International Journal of Production Research*, 54(23), 7181-7192.
13. Kyparisis, G.J., & Koulamas, C.P. (2006). Flexible flow shop scheduling with uniform parallel machines. *European Journal of Operational Research*, **168**, 985-997.

14. Lee, S., Y. Kang & V. V. Prabhu (2016). Smart logistics: distributed control of green crowdsourced parcel services. *International Journal of Production Research*, **54**(23), 6956-6968.

15. Lee, E.B., & Markus, L. (1967). *Foundations of optimal control theory*. New York.

16. Levin G., B. Rozin. A. Dolgui (2016). Optimization of the Structure and Execution Modes of Intersecting Operation Sets. IFAC-PapersOnLine 49-12 (2016) 105-110.

17. Moiseev, N.N. (1974). *Element of the optimal systems theory* [In Russian]. Moscow: Nauka.

18. Mönch L., Fowler J.W., Mason S. (2012). Production Planning and Control for Semiconductor Wafer Fabrication Facilities: Modeling, Analysis, and Systems. Springer Science & Business Media.

19. Nayak, A., Rodrigo Reyes Levalle, Seokcheon Lee & Shimon Y. Nof (2016). Resource sharing in cyber-physical systems: modelling framework and case studies. *International Journal of Production Research*, **54**(23), 6969-6983.

20. Oesterreich T.D., Teuteberg F. (2016). Understanding the implications of digitisation and automation in the context of Industry 4.0: A triangulation approach and elements of a research agenda for the construction industry. *Computers in Industry*, **83**, 121-139.

21. Otto J., Henning S., Niggemann, O. (2014). Why Cyber-physical Production Systems Need a Descriptive Engineering Approach – A Case Study in Plug & Produce. Procedia Technology, **15**, 295-302.

22. Tahar, D.N., Yalaoui, F., Chu, C. & Amodeo, L. (2006). A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times. *International Journal of Production Economics* **99**, 1-2, 63-73

23. Theorin, A., K. Bengtsson, J. Provost, M. Lieder, C. Johnsson, T. Lundholm & B. Lennartson (2017). An event-driven manufacturing information system architecture for Industry 4.0. International Journal of Production Research, 55(5), 1297-1311.

24. Weyer, S., Mathias Schmitt, Moritz Ohmer, Dominic Gorecky (2015). Towards Industry 4.0 - Standardization as the crucial challenge for highly modular, multi-vendor production systems. IFAC-PapersOnLine, Volume 48, Issue 3, 2015, Pages 579-584

25. Zhong, R.Y., Xu, C., Chen, C., Huang, G.Q. (2017). Big Data Analytics for Physical Internet-based intelligent manufacturing shop floors. *International Journal of Production Research*, **55**(9), 2610-2621.