Pages:     | 1 |   ...   | 68 | 69 || 71 | 72 |   ...   | 82 |

l Condition 2: Cycle time c is not violated for each station S, k {1, 2, , m}, i.e., sum of the processing times of k all the operations assigned to station S (called station time), has to be not greater than cycle time c:

k ti c.

(1) iVk For SALBP-1, line balance b is optimal when it uses the minimal number of m stations and when Condition 1 and Condition 2 are satisfied for line balance b.

Constructing an optimal line balance for SALBP-1 is binary NP-hard problem even for the case of two stations used in the optimal line balance (i.e., if S = (S, S )), empty precedence constraints (i.e., if A = ), and fixed 1 ~ processing times of all the operations V processed on the assembly line (i.e., if V = ).

The latter claim may be easily proven by polynomial reduction of NP-complete partition problem [Garey, Johnson, 1979] to SALBP-1 with two stations and with A = (see [Scholl, 1999]). For the sake of simplicity, notation t(Vk ) = ti (2) iVk is used for the original vector t = (t, t, , t ) of the operation times. Set V includes operations of two main types:

1 2 n ~ ~ subset V of operations with variable processing time (manual operations) and subset V \V of operations with ~ fixed processing time (automated operations). We assume that, if j V, then operation time t is a given nonj negative real number: t 0. However, the value of this operation time can vary during life cycle of the j ~ assembly line and can even be equal to zero. Zero operation time t will mean that operation j Vk V will j be processed (by an additional worker) in such a way that processing operation j will do not increase station time ~,t ~ ~+ for S for the new vector t = ( t ) =(t1,t2,,tn,tn,,tn ) of the operation times: ti = ti. The k iVk iVk \{j} ~ latter equality is possible if t = 0. If i V \V, then operation time t is given real number fixed during the life i j ~ cycle of the assembly line. We assume that t > 0 for each operation i V \V. As far as the processing time of i the automated operation is fixed, one can consider only such automated operations, which have strictly positive processing times. Indeed, an operation with fixed zero processing time has no influence on the solution of SALBP-1. In contrast to usual stochastic problems (see surveys [Erel, Sarin, 1998; Sarin, Erel, Dar-El, 1999]), we do not assume any probability distribution known in advance for the random processing times of the manual operations. Moreover, this paper does not deal with concrete algorithms for constructing an optimal line balance in a stochastic environment. It is assumed that the optimal line balance b is already constructed for the given vector t = (t, t,..., t ) of the operation times. Our main aim is to investigate the stability of the optimality of a line 1 2 n balance b with respect to independent variations of the processing times of all the manual operations ~ ~ V = {1, 2,, n} or a portion of the manual operations. More precisely, we investigate the stability radius of an optimal line balance b, which may be interpreted as the maximum of simultaneous independent variations of the manual operation times with definitely keeping optimality of line balance b.

Motivation, Notations, and Definition An assembly line balancing problem with fixed cycle time (denoted as SALBP-1) arises when a new assembly line must be installed, and the internal demands and properties of the assembly line have to be estimated. Cycle time c is defined on the basis of customer demands in the finished products. The value of c may be calculated as the ratio of available operating time of the assembly line and production volume for the same calendar interval.

One of the common mathematical problems at the stage of assembly line design is SALBP-1.

300 Intelligent Systems This problem may also arise when cycle time c of acting assembly line has to be changed because of changing customer demands in the finished product. In the real-world assemble lines, processing times of some operations may be known exactly and fixed for a long time (e.g., if operation has to be done by fully-automated machine or by semi-automated machine). Modern machines and robots are able to work permanently at a constant speed for a long time. However, in many cases it is not realistic to assume constant operation times for some operations, e.g., if an operation has to be done by a human operator with rather simple tools. In the case of a human work, operation time is subject to physical, psychological, and other factors. Due to the learning of operators, the operation times during the first days (weeks, months) of a life cycle of the assembly line may differ considerably from the processing times of the same operations during the later days (weeks, months). Moreover, some workers can leave the plant, and new workers with lower (or higher) skills have to replace them.

In the case of changeable operation times, it is important to know the credibility of the optimal line balance at hand with respect to possible independent variations of all or a portion of the operation times. Line balance b, ~,t which is optimal for the original vector t = ( t ) of the operation times, may lose its optimality (and even t feasibility) for some new vector t = (~,t ) of the operation times. For example, due to increasing of some operation times, line balance b may become infeasible for cycle time c since inequality (1) may be violated. In such a case, it is necessary to look for another line balance and to use it, if possible, for a suitable modification of production process on the assembly line. Also, line balance b may lose its optimality with saving its feasibility. It t may occur if another operation assignment, say, b become feasible for the modified vector t = (~,t ) of the s operation times, and b uses less stations than line balance b uses. Of course, each re-engineering and s modification of the assembly line being in process takes an additional time and other expenditure. So, assembly line modification has to be started, if it is really necessary: when the income from the re-engineering and modification will be larger than the total expenditure caused by the re-engineering. Thus, an evaluation of expenditures and benefits should be conducted before deciding whether re-engineering of assembly line is necessary. However, these expenditures and benefits are difficult to evaluate before the end of the reengineering process. In this paper, we present some sufficient conditions for keeping the optimality of the line balance being in process. For example, re-engineering is not necessary if the currently applied line balance ~ remains optimal in spite of the changes of the operation times t.

To test whether line balance b remains feasible for the new vector t = (~,t ) of the operation times takes t ~ O(n) time (if station times are included in the input data) or O(n) time (otherwise). Indeed, for the new operation times we have to verify inequality (1) for each subset Vk,k = 1,2,...,m, that includes at least one manual operation with changed processing time in the new vector t. On the other hand, in the case of feasibility of the line balance b for the new vector t, in order to test its optimality for t we have to solve the NP-hard problem SALBP-1. Intuitively, it is clear that sufficiently small changes of the operation times t1,t2,...,tn may ~ keep line balance b feasible and optimal for the new vector t = (~,t ) of the operation times. The aim of this t paper is to estimate or (what is better) to calculate the largest independent variations of the operation times ~ ti,i V, that do not violate the feasibility and optimality of the line balance b at hand.

Also, note that at the stage of the design of the assembly line, there may exist a lot of optimal line balances.

Using stability analysis, one can select such an optimal line balance, which feasibility and optimality are more ~ stable with respect to possible variations of the operation times ti,i V.

Let B denote the set of all assignments of operations V to stations S, S, , S (for all possible numbers m of 1 2 m the stations: 1 m n ), which satisfy Condition 1. Subset of set B of all operation assignments (line balances) which also satisfy Condition 2 for the given vector t = (t, t, , t ) of the operation times is denoted by B(t) = {b 1 2 n bk bk bk b, , b } where b, k {0, 1,..., h}, means the following line balance: V = V V...V. Let 1 h k 1 2 mbk subset of set B(t) of all the optimal line balances be denoted by B (t). Inclusion b B (t) implies that line opt opt b b b balance b: V = V V... V, satisfies Condition 1, Condition 2, and the following optimality condition 1 2 mb for the vector t = (t, t,, t ) of the operation times.

1 2 n XII-th International Conference "Knowledge - Dialogue - Solution" Condition 3: m = min{ mbk : b B(t)}.

b k Since line balance b is contained in the set B(t), we obtain b = b B(t) for some index r {0, 1,, h}. However, r as a matter of convenience, index r will be omitted for the optimal line balance b, which stability will be investigated. Note that in both definitions of set B and set B(t), number m of stations is not fixed. Namely, for each line balance b from the set B(t), inequalities mb mb n must hold, and number of stations in an operation k k assignment from set B has to belong to set {1, 2, , n}. The main questions under consideration may be ~ formulated as follows. How much can be modified the components of the vector t simultaneously and n independently from each other that the given line balance b remains feasible and optimal Let Rn (and R+ ) denote the space of n-dimensional real vectors t = (t, t, , tn ) (and the space of n-dimensional non-negative 1 real vectors, respectively) with the maximum metric, i.e., distance d(t,t*) between vector t Rn and vector * t* =(t1, t*,, t* ) Rn is calculated as follows: d( t,t* ) = max{ ti - t* : i V}. Here ti - t* 2 n i i denotes the absolute value of the difference ti - t*. Let line balance b be optimal for the given non-negative i n t real vector t = (~,t ) =(t, t, , t ) R+ of the operation times, i.e., b Bopt ( t ). For SALBP-1, the formal 1 2 n definition of stability radius of an optimal line balance may be introduced as follows.

~ ~ ~ 1 ~ Definition 1: The open ball O ( t ) with radius R+ and center t R+ n in the space Rn is called a ~ * stability ball of the line balance b Bopt ( t ), if for each vector t* = ( t, t ) of the operation times with ~ ~ n * t O (~) R+ line balance b remains feasible and optimal. The maximal value of the radius of stability t ~ ball O ( t ) of the line balance b is called stability radius denoted by (t).

b ~+1 ~+It should be noted that in Definition 1 vector t = (tn, tn,..., tn ) of the processing times of the automated operations and the complete vector t = (~,t ) = (t1,t2,...,tn ) of the operation times are fixed, while vector t ~ ~ ~ * * ~ t = (t1,t*,...,t* ) may vary within the intersection of the open ball O( t ) Rn with the space R+ n of 2 n the non-negative real vectors. The stability radius (t) is equal to the minimal upper bound of independent b ~ variations i of the processing times t of all the manual operations i V, which definitely keep the optimality of i the line balance b, i.e., inclusion b Bopt (t*) holds with ti* = max{0,ti - i} or ti* = ti + i.In the rest of this paper, we survey some recent results proven in [Sotskov, Dolgui, 2001; Sotskov, Dolgui, Portmann, 2006;

Sotskov et al, 2005] on stability analysis of an optimal line balance for SALBP-1 and for SALBP-2.

Stability Radius of an Optimal Line Balance for SALBP-~ Let Vkb denote the subset of manual operations of set Vkb, and let Vkb denote the subset of automated ~ operations of set Vkb. For each index k {1, 2, , m }, equality Vkb = Vkb Vkb holds. The following remark b is useful in stability analysis of an optimal line balance for SALBP-1.

Remark 1: Let us consider the line balance b Bopt (t) being in process and the modified vector t = (~,t ) of t b the given operation times. If there exists subset Vk, k {1, 2,..., mb }, in the line balance b such that ti = 0, (3) iVkb t we continue to affirm that the line balance b uses m stations for the modified vector t = (~,t ).

b 302 Intelligent Systems We can argue Remark-1 as follows. In spite of the equality (3) valid for the vector t = (~,t ), station S is still t k exists in the assembly line with line balance b. At very least to delete station S causes additional cost and k additional time for re-engineering the assembly line. Moreover, after deleting station S we obtain another line k balance, say, b* :

B * * b* V = Vib =V1b V2b...Vm b* i{ 1,2,...,mb },ik ~ where mb* = mb -1. Note that, due to the validity of inequality t > 0 for each automated operation i V\V, i b ~ equality (3) is only possible if Vkb = Vk. In [Sotskov, Dolgui, Portmann, 2006], it was proven the following necessary and sufficient conditions for the case when optimality of the line balance bB (t) is unstable.

opt Theorem 1: For the line balance bB (t) equality (t)=0 holds if and only if there exists a subset Vkb, opt b ~ k {1, 2,,mb}, such that Vkb and t(Vkb ) = c.

To present a formula for exact value of stability radius (t) of optimal line balance bB (t) and lower bound for b opt (t) we need the following notations:

b ~ b b = min { :Vkb, k {1, 2,..., mb}}, (4) k where c - t(Vkb) b = ~ k Vkb and value t(V ) is defined in (2). It is easy to see that testing criterion given in Theorem 1 takes O(n) time. The k b asymptotic bound O(n) is defined due to calculating station times t(Vp ), p = 1, 2,...,mb. Therefore, if station times are included in the input data of the algorithm, then algorithm takes O(m ) time.

b The following lower bound of stability radius has been obtained within the proof of Theorem 1.

b Corollary 1: If optimality of line balance b B (t ) is stable, then b( t ) min{,b } where opt b* t(Vp ) - c b* b* b = min { (Vp ) : b* B} and (Vp ) =.

~b* Vp ~b( d ) ~b( d ) Let Vp = {i1,i2,...,iu }, where u = Vp, and indices v of operations i are assigned in such a way v ~,t n that the following inequalities hold: ti1 ti2... tiu. We set ti = 0. Vector t = ( t ) R+ closest to b(d ) b(d) ~,t t, for which subset Vp is feasible (i.e., inequality (1) holds for subset Vp with vector t = ( t ) of the ~b(d) b( d ) operation times), can be obtained if for each operation iq Vp we set tiq = max{ 0,t - (Vp ) } j b( d ) where j and i denotes the same manual operation (j = i ), and value (Vp ) is calculated as follows:

Pages:     | 1 |   ...   | 68 | 69 || 71 | 72 |   ...   | 82 |

2011 www.dissers.ru -

, .
, , , , 1-2 .