# Safety Times for Multistage Assembly System

Authors: Goran Lazovic; Vesna Sesum-Cavic; Slobodanka Mitrovic; Slobodan Radojevic; Nebojsa Dedovic; Naveed Ishtiaq Chaudhary
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Nowadays, a wide class of problems can be solved by using the classical newsboy model. However, in problems where uncertainty of events and randomness are omnipresent, there is a necessity to adapt the existing solutions and/or find new extensions that will properly answer all requirements. This paper considers a multistage assembly system where interrelated assembly operations with independent stochastic operation times should be planned in an optimal way. Delivery of items in a requested time implies that either delay costs or holding costs appear. The goal is to find optimal safety times. We propose an approximate technique based on successive application of the solution of simpler one-stage problem. The generalized mathematical model suggested is built up on the relaxed hypothesis and can be used in multistage assembly networks. The existence and uniqueness of the solution are proven. The preliminary tests are performed and our approximate technique is compared to exact results.


---

## Body

## 1. Introduction

The newsboy problem is well-known. Different variants and extensions of the newsboy problem are used in many applicative scenarios (e.g., [1–9]). New requirements, imposed by each specific applicative scenario, introduce more complexity. Therefore, there is a necessity of extended and refined methods in treating of the newsboy problem. Basically, the solution of the newsboy problem is known when it is considered on a simple model. However, it is still an open issue in case of complex models (e.g., if penalties are random values).In maintenance systems, one of the main problems is uncertainty of events that drastically affect the maintenance efficiency and performance of the system. Typically, these events are random and correlated with demanding time or lead time for some reserve part, or time needed to prepare some reserve part. It is often supposed that a lead time or time needed to prepare some reserve part equals 0 (a reserve part is directly available) or constant, which is a very rough assumption. As many factors influence the above mentioned time, it has a random deviation, which significantly affects the system performance. The classical newsboy problem should be adapted to the given scenario and therefore, the appropriate mathematical models should be developed.The following assumptions are used:(1) a multistage assembly network is represented by a tree in the graph theory [10], (2) planning of interrelated assembly operations with independent stochastic operation times, and (3) delivery of items in a requested time (taking into account that it cannot be done until all end items are ready). As a consequence, either delay costs appear (if the given delivery requirement cannot be satisfied), or holding costs appear (if end items are ready earlier than the requested delivery time). Therefore, the goal is to find optimal safety times in order to minimize the total expected costs. The considered problem includes several stages, and therefore finding the exact solution is too difficult. In such situations, the usual way of coping with the problem is the application of a certain heuristic that is based on successive applications of the solution of simpler one or two-stage assembly network [11–13]. A hierarchical structure is approximated by a series of two-level structures. Under certain assumptions, the two-stage problem can be solved as the classical newsboy problem [14–16]. In [17], the authors consider the problem of contract assembly with combined supply lead time and demand quantity uncertainty and use stochastic operation times as well as stochastic demand. A more general class of stochastic assembly problems is considered in [18]. In [12], the authors calculate lower and upper limits for the decision variables and lower and upper bounds for the objective function. In [13], the focus is on dynamic, continuous-time generalization of the single-period newsboy problem. They reduce a multilevel system into a series of discrete newsboy problems and give an appropriate algorithm.Reference [19] solves the newsboy problem by considering multiple discounts and formulates and solves the newsboy problem by considering multiple upgrades as well as a mixed newsboy problem characterized with multiple discounts and upgrades. Reference [20] investigates a multiperiod production planning problem for multiple products, where the uncertain demand and the accumulated effort of market investment on demand are considered. Reference [21] studies a newsvendor model with discrete demand and shows that the optimal ordering decision with discrete demand is very different from that with continuous demand. Reference [22] considers the inverse newsvendor problem as a variant of the traditional newsvendor problem and provides an analysis of the problem under the assumptions of normally and exponentially distributed service times.The research work presented in [11] inspired us and it serves as our starting point. Namely, on the basis of the mathematical model in [11], we made a generalization. So, [11] is a special case of the presented model (see Section 3, (3)). Our model is built up on the extended assumption that the summed holding costs of individual stage components are greater than or equal to holding costs of the assembled component. The motivation for such a generalization came from the practical use-case (already mentioned maintenance systems). However, there are many similar real-life scenarios (e.g., holding costs of a completely assembled computer that waits to the installation are less than the sum of holding costs of each individual component). Therefore, the introduced relaxation in the starting assumption is important in order to encompass and properly address the abovementioned class of real-life use-cases.In this paper, we suggest a generalized approach with a random time assumed for the components in leafs (e.g., a delivery from some external source or a preparation for installation). The approach is based on a methodology of decomposition of the general problem into series of simple ones.Thenovelty and the maincontribution of this paper can be summarized as(i)
A new model for determining of critical times in one stage assembly network is given.(ii)
A theoretical result given in Theorem1 (Section 3) is new: the existence and uniqueness of the solution in a given model is proved.(iii)
A heuristic procedure described for the determination of the so-called starting times for all assembly/production steps is new.(iv)
This generalized model can be used in multistage assembly networks.


## 2. Problem Statement

In order to better clarify the problem itself, we separately provide the assumptions and notations used in the following text.


### 2.1. Notations

The following notations are used to establish mathematical models:td requested delivery time for end componente positive holding cost for end componentb positive delay cost for end componentC cost function at final nodeZ expected cost function at final nodei node corresponding to componenti assembly operationti starting time for componenti assembling operationτi starting time for componenti assembling operation, relative to starting time for end componentt0Li stochastic assembling duration time for componentiFi cumulative distribution function forLifi density function forLiTi time of componenti availabilityei positive holding cost for componentie^i positive stage holding cost at nodeib^i positive stage delay cost at nodeiCi stage cost function at nodeiZi stage expected cost function at nodei


### 2.2. Assumptions

Besides already mentioned initial assumption (a multistage assembly network represented by a tree in the graph theory, planning of interrelated assembly operations with independent stochastic operation times and delivery of items in a requested time taking into account that it cannot be done until all end items are ready), in accordance with [11], the following ones are made:Consider the end component0.(i)
The delay costs can be expressed asb((t0+ L0)− td)+, wherex+=max (x,0),b is a positive delay cost per time unit, andtd is a requested delivery time for end component0;(ii)
In case of several end components, the delay cost is calculated as the maximum delay;(iii)
Delay costs associated with other nodes are not taken in consideration, although they may affect the delay at node0.Consider nodek, and suppose thattk≥max (tl+Ll, tm+Lm, tn+Ln), i.e., componentk assembling, cannot start before preceding stage components are not assembled. Holding costs at nodek are obtained until the next stage assembly operation starts or the final delivery. The holding costs during the operations are disregarded.A graphical presentation of the considered assembly network can be seen on Figure1. It consists of the arcs, which represent the assembling operations, and nodes. Nodei is the node where an assembling operation for componenti starts, whereas the assembling timesLi are independent random variables with continuous cumulative distributionsFi and densityfi, andei is positive holding cost per time unit.Figure 1
The assembly network.The goal is to find optimal safety times, i.e., to plan assembling operations so that the total expected holding and delay costs are minimized [11].


## 2.1. Notations

The following notations are used to establish mathematical models:td requested delivery time for end componente positive holding cost for end componentb positive delay cost for end componentC cost function at final nodeZ expected cost function at final nodei node corresponding to componenti assembly operationti starting time for componenti assembling operationτi starting time for componenti assembling operation, relative to starting time for end componentt0Li stochastic assembling duration time for componentiFi cumulative distribution function forLifi density function forLiTi time of componenti availabilityei positive holding cost for componentie^i positive stage holding cost at nodeib^i positive stage delay cost at nodeiCi stage cost function at nodeiZi stage expected cost function at nodei


## 2.2. Assumptions

Besides already mentioned initial assumption (a multistage assembly network represented by a tree in the graph theory, planning of interrelated assembly operations with independent stochastic operation times and delivery of items in a requested time taking into account that it cannot be done until all end items are ready), in accordance with [11], the following ones are made:Consider the end component0.(i)
The delay costs can be expressed asb((t0+ L0)− td)+, wherex+=max (x,0),b is a positive delay cost per time unit, andtd is a requested delivery time for end component0;(ii)
In case of several end components, the delay cost is calculated as the maximum delay;(iii)
Delay costs associated with other nodes are not taken in consideration, although they may affect the delay at node0.Consider nodek, and suppose thattk≥max (tl+Ll, tm+Lm, tn+Ln), i.e., componentk assembling, cannot start before preceding stage components are not assembled. Holding costs at nodek are obtained until the next stage assembly operation starts or the final delivery. The holding costs during the operations are disregarded.A graphical presentation of the considered assembly network can be seen on Figure1. It consists of the arcs, which represent the assembling operations, and nodes. Nodei is the node where an assembling operation for componenti starts, whereas the assembling timesLi are independent random variables with continuous cumulative distributionsFi and densityfi, andei is positive holding cost per time unit.Figure 1
The assembly network.The goal is to find optimal safety times, i.e., to plan assembling operations so that the total expected holding and delay costs are minimized [11].


## 3. Two-Stage System

As previously mentioned, the approach is based on a methodology of decomposition of the general problem into series of simple ones. An approximate solution is obtained by successively applying the exact solution for a two-stage system. Therefore, we first consider and analyze the system presented in Figure2.Figure 2
The two-stage system.Lett0 be the optimal starting time for assembly operation at final node 0. Consider stage that precedes the assembly operation at final node 0. The stage delay costs can be expressed as b^(T¯-t0)+, where b^ is a positive stage delay cost per time unit, T¯=max1≤i≤n⁡Ti andTi= ti+Li. Two types of holding costs are incurred. Individual holding costs for componenti are incurred until all stage assembly operations are finished and can be expressed as hi=ei(T¯-Ti). Stage holding costs are incurred after all stage assembly operations are finished, and can be expressed as h^=e^(t0-T¯)+, where e^ is a positive stage holding cost per time unit. The costsC=C(t1,t2,…,tn) can be expressed as: C=e^(t0-T¯)++∑i=1neiT¯-Ti+b^(T¯-t0)+. It is natural (if a delay in the previous stage (with regard to found optimal timet0) exists, from linearity and additivity of the expectation, the expected costs/delay will be transferred to the final stage.) to assume that delay (T¯-t0)+ will produce the same delay in the next (final) stage, i.e., corresponding costs should be equal b^(T¯-t0)+=b(T¯-t0)+ thus b^=b and in the same way e^=e. The cost function can be simplified as follows:(1)C=et0-T¯++∑i=1neiT¯-Ti+bT¯-t0+Notice that the single-stage system (several end items) can be easily obtained as a special case of the two-stage system with final node assembly operation time L≡0 and e=∑i=1nei (see Figure 3).Figure 3
The single-stage system (several end items).Especially ifn=1, T¯=T1, we get the standard Newsboy problem C=e1(td-T1)++b(T1-td)+with the optimal solution given by: t1=td-F1-1b/b+e1.Consider the general case again. Asx+=x+(-x)+, the cost function can be expressed as(2)C=et0-T¯+∑i=1neiT¯-t0-Ti-t0+b+eT¯-t0+=∑i=1nei-eT¯-t0+∑i=1neit0-Ti+b+eT¯-t0+We assume the following: the summed holding costs per time unit of first stage components are greater than or equal to the holding cost per time unit of second stage component at final node0 (Figure 2), i.e., ∑i=1nei≥e. For ∑i=1nei=e the cost function is(3)C=∑i=1neit0-Ti+b+∑i=1neiT¯-t0+which is the model analysed in [11]. As Ti=ti+Li, i.e.,TT^=maxi⁡Ti, we get(4)C=∑i=1nei-emaxi⁡ti+Li-t0+∑i=1neit0-ti-Li+b+emaxi⁡ti+Li-t0+If we denote τi=t0-ti, the cost function is(5)C=∑i=1nei-emaxi⁡Li-τi+∑i=1neiτi-Li+b+emaxi⁡Li-τi+The expected cost function Z=E(C)=Z(τ1,τ2,…,τn) is(6)Z=∑i=1nei-eEmaxi⁡Li-τi+∑i=1neiτi-ELi+b+eEmaxi⁡Li-τi+It can be concluded that the expected cost functionZ has a unique minimum in a finite point.Theorem 1.
The expected cost function Z given by (6) has a unique minimum in finite point (τ1∗,τ2∗,…,τn∗).Proof.
First, we show that the expected cost function Z given by (6) is a convex function with arguments τ1,τ2,…,τn. The second part(7)∑i=1neiτi-ELiis a linear function and thus a convex function, whereas the convexity of the first part and the third part, respectively, (8)∑i=1nei-eEmaxi⁡Li-τib+eEmaxi⁡Li-τi+follows from monotonicity and linearity of expectation and convexity of a maximum of convex functions. That means that the expected cost function Z is a convex function as the sum of convex functions. On the other side, as limt→+∞⁡C=+∞ (see (1)) from monotonicity of expectation it follows that limτ→+∞⁡Z=limt→+∞⁡E(C)=+∞.
Properties of the expected cost function Z listed above provide the existence of a unique minimum in finite point(τ1∗,τ2∗,…,τn∗).It can be concluded that the exact solution is found in the two-stage system taking into account the introduced assumption.


### 3.1. Optimal Starting Times Determination

LetD=maxi⁡Li-τi, as D=D+-D-, wherex-=max (-x, 0)=(-x)+, the expected cost function is: Z=e-∑i=1neiE(D-)+∑i=1neiτi-E(Li)+b+∑i=1neiE(D+). For estimation of optimal starting times, it is necessary to determine the expectation of non-negative random variablesD+ andD-. As cumulative distribution functions are FD+(t)=P(D+<t)=∏iFi(τi+t) and FD-(t)=P(D-<t)=1-∏iFi(τi-t), corresponding expectations are:(9)ED+=∫0+∞1-∏iFiτi+tdt,ED-=∫0+∞∏iFiτi-tdtthus the expected cost function is:(10)Z=e-∑i=1nei∫0+∞∏iFiτi-tdt+∑i=1neiτi-ELi+b+∑i=1nei∫0+∞1-∏iFiτi+tdtThe stationary point of function Z is the solution of the following system of equations: (11)∂Z∂τi=e-∑i=1nei∂∂τi∫0+∞∏iFiτi-tdt+ei+b+∑i=1nei∂∂τi∫0+∞1-∏iFiτi+tdt=0,i=1,2,..,nFinally, the stationary point is the solution of the following system of nonlinear equations: (12)ei=-e+∑inei∫0+∞fiτi-t∏j≠iFjτj-tdt+b+∑i=1nei∫0+∞fit+τi∏j≠iFjt+τjdt,i=1,2,..,nThe obtained system of equations can be solved by numerical integration. Let us suppose that (τ1∗,τ2∗,…,τn∗) is the solution of the above system. The optimal starting times ti∗=t0-τi∗ for the two-stage system can be determined accordingly.


### 3.2. An Extension to Multistage System

Let us consider the two-stage system with root in nodei that is a part of the multistage system (Figure 4). The cost function for the stage that precedes the assembly operation at nodei is (see (2))(13)Ci=∑jeij-e^iTi¯-ti+∑jeijti-Tij+b^i+e^iTi¯-ti+where (Ti)j=(ti)j+(Li)j is the availability of component(i)j, Ti¯=maxj⁡{(Ti)j} and b^i,e^i the corresponding stage delay and stage holding costs. It is necessary to estimate stage delay costs b^i, i.e., stage holding costs e^i. As mentioned in the problem formulation, delays at other nodes may affect the delay at final node0.Figure 4
A two-stage system as a part of the multistage system.One possible methodology could be to distribute delay costs at final node0 down the assembly tree.Assume that the assembly operation at nodei starts with delay Δti. A change of delay costs ΔiB at final node0 is(14)ΔiB=Δtib^;Ti=T¯0;Ti<T¯So, the expectation of random variable ΔiB/Δti can be taken as stage delay costs b^i at nodei:(15)b^i=EΔiBΔti=b^PTi=T¯=b^PTi=max⁡Tjj=b^∏j≠iFLj-Liti∗-tj∗where FLj-Li is the distribution function of random variable Lj-Li. On the other side, if stage assembly operations are finished before requested time, that will affect holding costs at final node0.Assume that the assembly operation at nodei started in some previous moment ti-Δti. A change of holding costs ΔiE at final node0, is(16)ΔiE=Δtie^-∑j≠iej;Ti=T¯ei;Ti<T¯The expectation of random variable ΔiE/Δti can be taken as stage holding costs e^i at nodei: (17)e^i=EΔiEΔti=e^-∑j≠iejPTi=T¯+eiPTi<T¯=e^-∑jejPTi=T¯+ei=e^-∑jej∏j≠iFLj-Liti∗-tj∗+eiThe cost functionCi at stage that precedes assembly operation at nodei is completely defined:(18)Ci=∑jeij-e^iTi¯-ti+∑jeijti-Tij+b^i+e^iTi¯-ti+and the expected cost function Zi=E(Ci) is as follows:(19)Zi=∑jeij-e^iETi¯-ti+∑jeijti-ETij+b^i+e^iETi¯-ti+In order to provide the convergence of the above process, it is necessary to show that Zi is a convex function; i.e., it is enough to prove ∑j(ei)j≥e^i. This condition is valid as it follows directly from the general hypothesis: the summed holding costs per time unit of stage components are greater than or equal to the holding cost per time unit of stage component that follows (Figure 4), i.e., ∑j(ei)j≥ei:(20)e^i=e^-∑kekPTi=T¯+ei=e-∑kekPTi=T¯+ei≤ei≤∑jeijIn this way, the problem solution of safety time estimation can be extended to the multistage assembly network.At the end of this section, we provide a brief sum-up of the proposed procedure.After finding optimal times in the two-stage tree and a root in final node 0 (12), the summed holding costs and delay costs from final node 0 are being distributed to nodes of the previous stage by using the described procedure ((15), (17)). With each distribution tom nodes of the previous stage (Figure 4), the starting problem is being decomposed intom problems of the lower orders, which are further solved in the same way.


## 3.1. Optimal Starting Times Determination

LetD=maxi⁡Li-τi, as D=D+-D-, wherex-=max (-x, 0)=(-x)+, the expected cost function is: Z=e-∑i=1neiE(D-)+∑i=1neiτi-E(Li)+b+∑i=1neiE(D+). For estimation of optimal starting times, it is necessary to determine the expectation of non-negative random variablesD+ andD-. As cumulative distribution functions are FD+(t)=P(D+<t)=∏iFi(τi+t) and FD-(t)=P(D-<t)=1-∏iFi(τi-t), corresponding expectations are:(9)ED+=∫0+∞1-∏iFiτi+tdt,ED-=∫0+∞∏iFiτi-tdtthus the expected cost function is:(10)Z=e-∑i=1nei∫0+∞∏iFiτi-tdt+∑i=1neiτi-ELi+b+∑i=1nei∫0+∞1-∏iFiτi+tdtThe stationary point of function Z is the solution of the following system of equations: (11)∂Z∂τi=e-∑i=1nei∂∂τi∫0+∞∏iFiτi-tdt+ei+b+∑i=1nei∂∂τi∫0+∞1-∏iFiτi+tdt=0,i=1,2,..,nFinally, the stationary point is the solution of the following system of nonlinear equations: (12)ei=-e+∑inei∫0+∞fiτi-t∏j≠iFjτj-tdt+b+∑i=1nei∫0+∞fit+τi∏j≠iFjt+τjdt,i=1,2,..,nThe obtained system of equations can be solved by numerical integration. Let us suppose that (τ1∗,τ2∗,…,τn∗) is the solution of the above system. The optimal starting times ti∗=t0-τi∗ for the two-stage system can be determined accordingly.


## 3.2. An Extension to Multistage System

Let us consider the two-stage system with root in nodei that is a part of the multistage system (Figure 4). The cost function for the stage that precedes the assembly operation at nodei is (see (2))(13)Ci=∑jeij-e^iTi¯-ti+∑jeijti-Tij+b^i+e^iTi¯-ti+where (Ti)j=(ti)j+(Li)j is the availability of component(i)j, Ti¯=maxj⁡{(Ti)j} and b^i,e^i the corresponding stage delay and stage holding costs. It is necessary to estimate stage delay costs b^i, i.e., stage holding costs e^i. As mentioned in the problem formulation, delays at other nodes may affect the delay at final node0.Figure 4
A two-stage system as a part of the multistage system.One possible methodology could be to distribute delay costs at final node0 down the assembly tree.Assume that the assembly operation at nodei starts with delay Δti. A change of delay costs ΔiB at final node0 is(14)ΔiB=Δtib^;Ti=T¯0;Ti<T¯So, the expectation of random variable ΔiB/Δti can be taken as stage delay costs b^i at nodei:(15)b^i=EΔiBΔti=b^PTi=T¯=b^PTi=max⁡Tjj=b^∏j≠iFLj-Liti∗-tj∗where FLj-Li is the distribution function of random variable Lj-Li. On the other side, if stage assembly operations are finished before requested time, that will affect holding costs at final node0.Assume that the assembly operation at nodei started in some previous moment ti-Δti. A change of holding costs ΔiE at final node0, is(16)ΔiE=Δtie^-∑j≠iej;Ti=T¯ei;Ti<T¯The expectation of random variable ΔiE/Δti can be taken as stage holding costs e^i at nodei: (17)e^i=EΔiEΔti=e^-∑j≠iejPTi=T¯+eiPTi<T¯=e^-∑jejPTi=T¯+ei=e^-∑jej∏j≠iFLj-Liti∗-tj∗+eiThe cost functionCi at stage that precedes assembly operation at nodei is completely defined:(18)Ci=∑jeij-e^iTi¯-ti+∑jeijti-Tij+b^i+e^iTi¯-ti+and the expected cost function Zi=E(Ci) is as follows:(19)Zi=∑jeij-e^iETi¯-ti+∑jeijti-ETij+b^i+e^iETi¯-ti+In order to provide the convergence of the above process, it is necessary to show that Zi is a convex function; i.e., it is enough to prove ∑j(ei)j≥e^i. This condition is valid as it follows directly from the general hypothesis: the summed holding costs per time unit of stage components are greater than or equal to the holding cost per time unit of stage component that follows (Figure 4), i.e., ∑j(ei)j≥ei:(20)e^i=e^-∑kekPTi=T¯+ei=e-∑kekPTi=T¯+ei≤ei≤∑jeijIn this way, the problem solution of safety time estimation can be extended to the multistage assembly network.At the end of this section, we provide a brief sum-up of the proposed procedure.After finding optimal times in the two-stage tree and a root in final node 0 (12), the summed holding costs and delay costs from final node 0 are being distributed to nodes of the previous stage by using the described procedure ((15), (17)). With each distribution tom nodes of the previous stage (Figure 4), the starting problem is being decomposed intom problems of the lower orders, which are further solved in the same way.


## 4. Some Numerical Results and Discussion

We used two sets of sample problems in order to evaluate the suggested approximate procedure.


### 4.1. Problem Sets

The following problem set is used to evaluate the suggested approximate procedure. The three-stage networks are considered in Figures5 and 6. As it can be seen from the pictures, the problem set 1 is decomposed into two 2-stage problems, whereas the problem set 2 is more complex and decomposed into three 2-stage problems.Figure 5
An assembly network 1 for the considered problem set.Figure 6
An assembly network 2 for the considered problem set.We use the following parameters for a numerical example. Holding costsei at every node are constant and equal to 1, whereas delay costsb at final node0 belong to 5,25,50. For assembly operations time exponential distribution X:E(1), i.e., normal distribution Y:N(0,1)is used. Further, we assume that distributions of operation times are:L0=L1=L3=X, L2= L5=Y2, L4=2X, L6=2Y2 with expected operation time equal 1. Dispersion of given distributions is parameterized in the following way. Instead of distributionL, a+ (1-a)·L,a∈0,0.5,0.8 is taken, this way, the expected operation time remains 1, but dispersion will be changed. The goal is to determine optimal starting timest2,t3,t4 when a certain assembly operations should be activated in order to minimize the total expected costs. Assume that the requested delivery time istd= 0.


### 4.2. Parameter Sensitivity and Comparison Analysis

Tables1 and 2, respectively, show obtained results for 9 test examples. Table 1 presents the results for the example in Figure 5, whereas Table 2 presents the results for the example in Figure 6. For every test example, there are two subrows. The first subrow contains the values of parametersa andb and the exact solutions for optimal starting timest2,t3,t4, i.e.t3,t4,t5, andt6 in which minimum of the total expected costs is reached. The exact solutions are obtained in MatLab. The second subrow contains solutions obtained by using the proposed approximation and the value of the total expected costs, i.e., deviation of minimal total expected costs expressed in percentage.Table 1
Results for the example in Figure5.
a b t 2 t 3 t 4 Z % ( 1 ) 0.00 5 -5.6817 -8.9957 -9.8808 8.6353 -4.4636 -8.1565 -9.0760 8.8418 2.34 ( 2 ) 0.00 25 -9.5108 -13.8605 -14.8619 13.6123 -8.1273 -15.1227 -16.0435 14.0289 2.97 ( 3 ) 0.00 50 -11.3712 -16.1748 -17.2351 16.0047 -9.8716 -18.2755 -19.1849 16.7053 4.19 ( 4 ) 0.50 5 -3.9700 -6.0422 -6.9813 4.3201 -3.2318 -5.5694 -6.5320 4.4202 2.26 ( 5 ) 0.50 25 -5.7672 -8.5509 -9.5439 6.8207 -5.0636 -9.0402 -10.0066 7.0165 2.79 ( 6 ) 0.50 50 -7.0828 -9.6849 -10.7116 8.0456 -5.9340 -10.5754 -11.5333 8.3495 3.64 ( 7 ) 0.80 5 -2.8292 -4.1775 -5.1954 1.7158 -2.4927 -4.0226 -5.0093 1.7447 1.66 ( 8 ) 0.80 25 -3.5906 -5.2513 -6.2422 2.7094 -3.2255 -5.3903 -6.3844 2.7699 2.18 ( 9 ) 0.80 50 -3.8246 -5.7494 -6.7340 3.2010 -3.5743 -6.0797 -7.0557 3.3351 4.02Table 2
Results for the example in Figure6.
a b t 3 t 4 t 5 t 6 Z % ( 1 ) 0.00 5 -10.8038 -11.5284 -10.7891 -11.3452 11.2195 -11.3934 -11.3820 -10.8962 -11.7067 11.8147 3.51 ( 2 ) 0.00 25 -17.0659 -17.8230 -17.2410 -17.8448 17.7063 -16.3767 -18.5712 -16.7905 -17.9286 18.4801 4.19 ( 3 ) 0.00 50 -20.2048 -20.9545 -20.4889 -21.1705 20.7971 -18.5125 -19.3732 -16.5802 -18.6037 22.3192 6.82 ( 4 ) 0.50 5 -6.8610 -7.7265 -6.8320 -7.6252 8.0147 -6.1766 -7.1368 -5.9168 -7.0536 8.2506 2.86 ( 5 ) 0.50 25 -9.9837 -10.8667 -10.0536 -10.8490 20.8745 -9.0003 -9.9779 -8.2540 -9.3247 21.6670 3.66 ( 6 ) 0.50 50 -11.4793 -12.3481 -11.5799 -12.4326 34.4485 -11.7443 -11.8789 -9.6807 -11.8666 36.3321 5.18 ( 7 ) 0.80 5 -4.5742 -5.5234 -4.5465 -5.4594 3.6143 -4.4311 -5.4151 -4.2227 -5.1586 3.7029 2.39 ( 8 ) 0.80 25 -5.7823 -6.7320 -5.7992 -6.7488 10.3934 -5.4264 -6.4102 -5.1177 -6.1380 10.7023 2.89 ( 9 ) 0.80 50 -6.3553 -7.3029 -6.3896 -7.3216 17.8629 -5.8198 -7.0863 -5.4804 -6.4555 18.6259 4.10The column “%” in Tables1 and 2 presents a relative error between expected costs of the exact solution and expected costs of the solution obtained by using the proposed heuristic. For fixed value of parameterb and with an increased value of parametera, a relative error decreases. From Table 1, it can be seen that the suggested model treats changes in the assembly system in an adequate way: the smaller dispersion (i.e., the bigger value of parametera), the less deviation from the exact solution. From the other side, the deviation increases with a disproportion of costs,h andb (h is always equal to 1,b takes values 5, 25, 50). In Table 2, the slightly increased value of error in some cases of the problem set 2 compared to the problem set 1 can be influenced by ∗) the increased complexity of the considered problem and ∗) the existence of more critical paths L6L2L0, L4L1L0 (as the time distributions L6 and L4 are doubled).Comparing our results with results of the problem set 2 from Axsater [11] (which is more realistic than the problem set 1), the following could be noticed:(i)
regarding deviation of the assembly operation duration both techniques show similar behavior, i.e., a greater deviation of assembly operations durations (smaller value of the parametera) produce a greater relative error;(ii)
in our case, the moments of initiating certain operations on the nodes(i)j preceding the operation corresponding to node i  are mainly estimated in same way—either all starting times are overestimated or all of them are underestimated (see Tables 1 and 2), i.e., (21)t3opt<t3approx,t4opt<t4approx,Table1.rows1,4,7t3opt>t3approx,t4opt>t4approx,Table1.rows2,3,5,6,8,9t5opt<t5approx,t6opt<t6approx,Table2.rows3,4,5,6,7,8,9t5opt>t5approx,t6opt>t6approx,Table2.row1This is expected since our proposed heuristic consists of series of consecutive goals and each goal represents an “overall” optimization of starting times corresponding to nodesij so that an assembly operation at node i that follows could be started at presumed time ti.This is not the case for Axsater [11] procedure, i.e., ts1opt<ts1approx and ts2opt>ts2approx (Table 3).Table 3
Problem set 2 results from Axäter [11].
Optimum by simulation Approximate policy t s 1 t s 2 t m Costs t s 1 t s 2 t m Costs -4.3 -3.1 -2.3 3.68 -4.20 -3.20 -2.26 3.94 -5.0 -3.5 -2.5 6.46 -4.57 -3.53 -2.53 6.86 -5.3 -3.6 -2.7 7.82 -4.76 -3.70 -2.68 8.69 -4.6 -3.2 -2.6 9.18 -4.49 -3.49 -2.66 9.86 -5.8 -3.9 -3.4 16.16 -5.42 -4.32 -3.33 17.57 -7.1 -4.4 -3.8 19.12 -5.90 -4.75 -3.70 22.29 -5.2 -3.3 -3.3 17.89 -4.98 -3.99 -3.31 20.04 -8.3 -4.7 -4.6 31.85 -6.84 -5.64 -4.67 34.41 -9.9 -5.5 -5.4 38.79 -7.80 -6.49 -5.41 43.69So, we obtained an improvement of the results presented in [11]. The obtained results are promising: (1) the values of deviation are relatively small, and (2) the time improvement becomes significant with the increase of levels; i.e., the greater number of level is introduced in the problem, and the better improvement in results is visible. One of the motivations for the study was also to consider problems with more complex assembly graphs. In a more complex model, it could be noticed a confirmation in the effectiveness of the used heuristic, i.e., a confirmation of the promising results obtained in the simpler model. A comparison of our suggested heuristic with exact solutions oneven more complex graphs is not presented as large and complex instances are difficult to be optimally solved by using exact methods [11].As already mentioned, [11] elaborated that the considered problem with several stages is, in general, too difficult to be solved exactly. So, the important research question that we considered is to construct a heuristic that should be improved by means of two issues: (1) the quality of approximation and (2) a generalization, so that it can “cover” different practical use-cases, which was originally our motivation to start with. In the presented numerical results, we estimated its quality of approximation. The benefit of using the suggested heuristics is the possibility to solve the starting problem for an assembly network witharbitrary many stages.


### 4.3. Statistical Analysis

In order to draw the conclusion with statistical confidence, i.e., to establish whether the performance on the two selected problem sets differs with statistical significance, the ANOVA test is performed. The comparative analysis showed that, for fixed value of parameterb and with an increased value of parametera, a relative error decreases. Now, we take another point of view in which we would like to analyze the following:(i)
Is the average value of the relative error (“%”) significant, for different, variable values of parametersa andb?(ii)
As a consequence of the previous point, what could we expect about the relative error (“%”) without regard to specific values ofa andb, if problem set changes?The analysis is set up as follows:(1)
Statement of heuristic performance hypothesis: For the two problem sets, the relative error “%” distribution is compared using the null-hypothesis as
H0: There is no difference in the mean “%” between the two problem sets.H1: There is a difference in mean “%” between the two problem sets.(2)
Significance level: The test is performed at a significance level ofα = 0.05.(3)
Interpretation of results: If thep-value from the ANOVA-test is less than 0.05, the results are referred to as significantly different and the null-hypothesis,H0, is rejected at the defined significance level. If thep-value is greater than 0.05, then the null-hypothesis is not rejected.According to the obtained data from Tables1 and 2, thep-value is 0,3291, which supports the null-hypothesis.


## 4.1. Problem Sets

The following problem set is used to evaluate the suggested approximate procedure. The three-stage networks are considered in Figures5 and 6. As it can be seen from the pictures, the problem set 1 is decomposed into two 2-stage problems, whereas the problem set 2 is more complex and decomposed into three 2-stage problems.Figure 5
An assembly network 1 for the considered problem set.Figure 6
An assembly network 2 for the considered problem set.We use the following parameters for a numerical example. Holding costsei at every node are constant and equal to 1, whereas delay costsb at final node0 belong to 5,25,50. For assembly operations time exponential distribution X:E(1), i.e., normal distribution Y:N(0,1)is used. Further, we assume that distributions of operation times are:L0=L1=L3=X, L2= L5=Y2, L4=2X, L6=2Y2 with expected operation time equal 1. Dispersion of given distributions is parameterized in the following way. Instead of distributionL, a+ (1-a)·L,a∈0,0.5,0.8 is taken, this way, the expected operation time remains 1, but dispersion will be changed. The goal is to determine optimal starting timest2,t3,t4 when a certain assembly operations should be activated in order to minimize the total expected costs. Assume that the requested delivery time istd= 0.


## 4.2. Parameter Sensitivity and Comparison Analysis

Tables1 and 2, respectively, show obtained results for 9 test examples. Table 1 presents the results for the example in Figure 5, whereas Table 2 presents the results for the example in Figure 6. For every test example, there are two subrows. The first subrow contains the values of parametersa andb and the exact solutions for optimal starting timest2,t3,t4, i.e.t3,t4,t5, andt6 in which minimum of the total expected costs is reached. The exact solutions are obtained in MatLab. The second subrow contains solutions obtained by using the proposed approximation and the value of the total expected costs, i.e., deviation of minimal total expected costs expressed in percentage.Table 1
Results for the example in Figure5.
a b t 2 t 3 t 4 Z % ( 1 ) 0.00 5 -5.6817 -8.9957 -9.8808 8.6353 -4.4636 -8.1565 -9.0760 8.8418 2.34 ( 2 ) 0.00 25 -9.5108 -13.8605 -14.8619 13.6123 -8.1273 -15.1227 -16.0435 14.0289 2.97 ( 3 ) 0.00 50 -11.3712 -16.1748 -17.2351 16.0047 -9.8716 -18.2755 -19.1849 16.7053 4.19 ( 4 ) 0.50 5 -3.9700 -6.0422 -6.9813 4.3201 -3.2318 -5.5694 -6.5320 4.4202 2.26 ( 5 ) 0.50 25 -5.7672 -8.5509 -9.5439 6.8207 -5.0636 -9.0402 -10.0066 7.0165 2.79 ( 6 ) 0.50 50 -7.0828 -9.6849 -10.7116 8.0456 -5.9340 -10.5754 -11.5333 8.3495 3.64 ( 7 ) 0.80 5 -2.8292 -4.1775 -5.1954 1.7158 -2.4927 -4.0226 -5.0093 1.7447 1.66 ( 8 ) 0.80 25 -3.5906 -5.2513 -6.2422 2.7094 -3.2255 -5.3903 -6.3844 2.7699 2.18 ( 9 ) 0.80 50 -3.8246 -5.7494 -6.7340 3.2010 -3.5743 -6.0797 -7.0557 3.3351 4.02Table 2
Results for the example in Figure6.
a b t 3 t 4 t 5 t 6 Z % ( 1 ) 0.00 5 -10.8038 -11.5284 -10.7891 -11.3452 11.2195 -11.3934 -11.3820 -10.8962 -11.7067 11.8147 3.51 ( 2 ) 0.00 25 -17.0659 -17.8230 -17.2410 -17.8448 17.7063 -16.3767 -18.5712 -16.7905 -17.9286 18.4801 4.19 ( 3 ) 0.00 50 -20.2048 -20.9545 -20.4889 -21.1705 20.7971 -18.5125 -19.3732 -16.5802 -18.6037 22.3192 6.82 ( 4 ) 0.50 5 -6.8610 -7.7265 -6.8320 -7.6252 8.0147 -6.1766 -7.1368 -5.9168 -7.0536 8.2506 2.86 ( 5 ) 0.50 25 -9.9837 -10.8667 -10.0536 -10.8490 20.8745 -9.0003 -9.9779 -8.2540 -9.3247 21.6670 3.66 ( 6 ) 0.50 50 -11.4793 -12.3481 -11.5799 -12.4326 34.4485 -11.7443 -11.8789 -9.6807 -11.8666 36.3321 5.18 ( 7 ) 0.80 5 -4.5742 -5.5234 -4.5465 -5.4594 3.6143 -4.4311 -5.4151 -4.2227 -5.1586 3.7029 2.39 ( 8 ) 0.80 25 -5.7823 -6.7320 -5.7992 -6.7488 10.3934 -5.4264 -6.4102 -5.1177 -6.1380 10.7023 2.89 ( 9 ) 0.80 50 -6.3553 -7.3029 -6.3896 -7.3216 17.8629 -5.8198 -7.0863 -5.4804 -6.4555 18.6259 4.10The column “%” in Tables1 and 2 presents a relative error between expected costs of the exact solution and expected costs of the solution obtained by using the proposed heuristic. For fixed value of parameterb and with an increased value of parametera, a relative error decreases. From Table 1, it can be seen that the suggested model treats changes in the assembly system in an adequate way: the smaller dispersion (i.e., the bigger value of parametera), the less deviation from the exact solution. From the other side, the deviation increases with a disproportion of costs,h andb (h is always equal to 1,b takes values 5, 25, 50). In Table 2, the slightly increased value of error in some cases of the problem set 2 compared to the problem set 1 can be influenced by ∗) the increased complexity of the considered problem and ∗) the existence of more critical paths L6L2L0, L4L1L0 (as the time distributions L6 and L4 are doubled).Comparing our results with results of the problem set 2 from Axsater [11] (which is more realistic than the problem set 1), the following could be noticed:(i)
regarding deviation of the assembly operation duration both techniques show similar behavior, i.e., a greater deviation of assembly operations durations (smaller value of the parametera) produce a greater relative error;(ii)
in our case, the moments of initiating certain operations on the nodes(i)j preceding the operation corresponding to node i  are mainly estimated in same way—either all starting times are overestimated or all of them are underestimated (see Tables 1 and 2), i.e., (21)t3opt<t3approx,t4opt<t4approx,Table1.rows1,4,7t3opt>t3approx,t4opt>t4approx,Table1.rows2,3,5,6,8,9t5opt<t5approx,t6opt<t6approx,Table2.rows3,4,5,6,7,8,9t5opt>t5approx,t6opt>t6approx,Table2.row1This is expected since our proposed heuristic consists of series of consecutive goals and each goal represents an “overall” optimization of starting times corresponding to nodesij so that an assembly operation at node i that follows could be started at presumed time ti.This is not the case for Axsater [11] procedure, i.e., ts1opt<ts1approx and ts2opt>ts2approx (Table 3).Table 3
Problem set 2 results from Axäter [11].
Optimum by simulation Approximate policy t s 1 t s 2 t m Costs t s 1 t s 2 t m Costs -4.3 -3.1 -2.3 3.68 -4.20 -3.20 -2.26 3.94 -5.0 -3.5 -2.5 6.46 -4.57 -3.53 -2.53 6.86 -5.3 -3.6 -2.7 7.82 -4.76 -3.70 -2.68 8.69 -4.6 -3.2 -2.6 9.18 -4.49 -3.49 -2.66 9.86 -5.8 -3.9 -3.4 16.16 -5.42 -4.32 -3.33 17.57 -7.1 -4.4 -3.8 19.12 -5.90 -4.75 -3.70 22.29 -5.2 -3.3 -3.3 17.89 -4.98 -3.99 -3.31 20.04 -8.3 -4.7 -4.6 31.85 -6.84 -5.64 -4.67 34.41 -9.9 -5.5 -5.4 38.79 -7.80 -6.49 -5.41 43.69So, we obtained an improvement of the results presented in [11]. The obtained results are promising: (1) the values of deviation are relatively small, and (2) the time improvement becomes significant with the increase of levels; i.e., the greater number of level is introduced in the problem, and the better improvement in results is visible. One of the motivations for the study was also to consider problems with more complex assembly graphs. In a more complex model, it could be noticed a confirmation in the effectiveness of the used heuristic, i.e., a confirmation of the promising results obtained in the simpler model. A comparison of our suggested heuristic with exact solutions oneven more complex graphs is not presented as large and complex instances are difficult to be optimally solved by using exact methods [11].As already mentioned, [11] elaborated that the considered problem with several stages is, in general, too difficult to be solved exactly. So, the important research question that we considered is to construct a heuristic that should be improved by means of two issues: (1) the quality of approximation and (2) a generalization, so that it can “cover” different practical use-cases, which was originally our motivation to start with. In the presented numerical results, we estimated its quality of approximation. The benefit of using the suggested heuristics is the possibility to solve the starting problem for an assembly network witharbitrary many stages.


## 4.3. Statistical Analysis

In order to draw the conclusion with statistical confidence, i.e., to establish whether the performance on the two selected problem sets differs with statistical significance, the ANOVA test is performed. The comparative analysis showed that, for fixed value of parameterb and with an increased value of parametera, a relative error decreases. Now, we take another point of view in which we would like to analyze the following:(i)
Is the average value of the relative error (“%”) significant, for different, variable values of parametersa andb?(ii)
As a consequence of the previous point, what could we expect about the relative error (“%”) without regard to specific values ofa andb, if problem set changes?The analysis is set up as follows:(1)
Statement of heuristic performance hypothesis: For the two problem sets, the relative error “%” distribution is compared using the null-hypothesis as
H0: There is no difference in the mean “%” between the two problem sets.H1: There is a difference in mean “%” between the two problem sets.(2)
Significance level: The test is performed at a significance level ofα = 0.05.(3)
Interpretation of results: If thep-value from the ANOVA-test is less than 0.05, the results are referred to as significantly different and the null-hypothesis,H0, is rejected at the defined significance level. If thep-value is greater than 0.05, then the null-hypothesis is not rejected.According to the obtained data from Tables1 and 2, thep-value is 0,3291, which supports the null-hypothesis.


## 5. Conclusion

New or changed requirements in maintenance systems increase overall complexity and impose the necessity of finding the solution of appropriate complex models. In such a case, the solution can be found only by using some approximate techniques. This paper considers a multistage assembly system in which the goal is to find optimal starting assembly times taking into account randomness of various events. We proposed one approximation of the multilevel hierarchical structure in the assembly procedure by a series of two-stage structures. A new model for determining optimal starting times in two-stage assembly network is given. The existence and uniqueness of the solution in a given model is proven. Further, thisgeneralized model can be used in arbitrary-level assembly systems.Future work will consider finding the problem solution of safety time estimation in the two-stage assembly network with further relaxation of the introduced assumption (e.g., through an appropriate parameterization, e.g., holding costs and delay costs could be also time functions, random variables).



---

*Source: 8208049-2018-11-07.xml*