Keywords

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; Dolgui et al. 2009). 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, 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:

$$ \begin{array}{*{20}l} {\overline{B} \, = \,\{ \overline{B}^{(i)} ,\,i \in \overline{N} ,\,\,\overline{N} \, = \,(1, \ldots ,\overline{n} )\} \,{\text{is}}\,{\text{the}}\,{\text{set}}\,{\text{of}}\,{\text{customer}}\,{\text{orders}}\,\left( {\text{jobs}} \right)} \hfill \\ {D\, = \,\{ D_{\mu }^{i} \,,\mu \in \overline{S} ,\overline{S} = \,(1, \ldots ,s_{i} )\} \,{\text{is}}\,{\text{the}}\,{\text{set}}\,{\text{of}}\,{\text{manufacturing}}\,{\text{operations}}} \hfill \\ {M\, = \,\{ M^{j} ,j \in N,N = (1, \ldots ,n)\} \,{\text{is}}\,{\text{the}}\,{\text{set}}\,{\text{of}}\,{\text{stations}}} \hfill \\ \end{array} $$

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 and 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. Equations (1)–(8) exemplify process control models, constraints, and objective functions.

$$ \frac{{dx_{i\mu }^{(o)} }}{dt} = \dot{x}_{i\mu }^{(o)} = \sum\limits_{j = 1}^{n} {\varepsilon_{ij} (t)u_{i\mu j}^{(o)} (t)} $$
(1)
$$ \frac{{dx_{i\mu j}^{(f)} }}{dt} = \dot{x}_{i\mu j}^{(f)} = u_{i\mu j}^{(f)} $$
(2)
$$ \sum\limits_{i = 1}^{{\bar{n}}} {\sum\limits_{\mu = 1}^{{s_{i} }} {u_{i\mu j}^{(o)} (t)} } \le 1,\,\,\,\sum\limits_{j = 1}^{n} {u_{i\mu j}^{(o)} (t)} \le 1 $$
(3)
$$ \sum\limits_{j = 1}^{n} {u_{i\mu j}^{(o)} [\sum\limits_{{\alpha \in\Gamma _{{i\mu_{1} }}^{ - } }} {(a_{i\alpha }^{(o)} - x_{i\alpha }^{(o)} )} + \prod\limits_{{\beta \in\Gamma _{{i\mu_{2} }}^{ - } }} {(a_{i\beta }^{(o)} - x_{i\beta }^{(o)} )} ]} = 0 $$
(4)
$$ 0 \le u_{i\mu j}^{(f)} (t) \le c_{i\mu j}^{(f)} \cdot u_{i\mu j}^{(o)} $$
(5)
$$ \sum\limits_{i = 1}^{{\bar{n}}} {\sum\limits_{\mu = 1}^{{s_{i} }} {u_{i\mu j}^{(f)} (t)} } \le \tilde{\tilde{R}}_{\,j}^{(f)} \cdot \xi_{{}}^{(f)} (t) $$
(6)
$$ J_{1}^{(o)} = \frac{1}{2}\sum\limits_{i = 1}^{{\bar{n}}} {\sum\limits_{\mu = 1}^{{s_{i} }} {(a_{i\mu }^{(o)} - x_{i\mu }^{(o)} (T_{f} ))^{2} } } $$
(7)
$$ J_{2}^{(o)} = \sum\limits_{i = 1}^{{\bar{n}}} {\sum\limits_{\mu = 1}^{{s_{i} }} {\sum\limits_{j = 1}^{n} {\int\limits_{{T_{0} }}^{{T_{f} }} {\alpha_{i\mu }^{(o)} (\tau )u_{i\mu j}^{(o)} (\tau )d\tau } } } } $$
(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.

Equation (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_{i\mu j}^{(f)} (t) \) is not a binary variable like \( u_{i\mu j}^{(o)} (t) \), but it is equal to the processed flow volume \( x_{i\mu j}^{(f)} \) at each time point t. The model (2)–(5) and (6) uses the assignment results from the model (1)–(3) and (4) in the form of the control variables \( u_{i\mu j}^{(o)} (t) \) and extends them by the actual processing speed of the machines subject to the constraints (5) and (6). Inequalities (5) use the assignment decisions \( u_{i\mu j}^{(o)} (t) \) and consider the actual processing speed \( c_{i\mu j}^{{}} (t) \) of the stations \( M^{(j)} \). Constraints (6) reflect that the processing speed is constrained by \( \tilde{\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 Tf. The objective function (8) minimizes total maximum lateness using penalties. The penalty function \( \alpha_{i\mu }^{(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. 1.

    Initial solution \( \overline{{\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. 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. 3.

    The transversality conditions are evaluated.

  4. 4.

    The conjugate system is integrated subject to \( {\mathbf{u}}(t) = \overline{{\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. 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) and (6) influences the operations execution control model (1), (3) and (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 execute different functions subject to individual sets of operations within the jobs. Therefore, 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 simultaneously 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 formulation of the scheduling model as optimal program control allows including into consideration 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.