Книги по разным темам Pages:     | 1 |   ...   | 69 | 70 | 71 | 72 | 73 |   ...   | 82 |

q q ti ti ( d ) - c - b =iVp ~b( d ) b( d ) (Vp ) = max { : = 0,1,..., Vp -1 } ~b( d ) Vp - ~b( d ) where maximum is taken among right-hand fractions calculated for all = 0,1,..., Vp -1.

XII-th International Conference "Knowledge - Dialogue - Solution" We can define b(d) b( d ) (b( d )) = max { (Vp ) : t(Vp ) > c } (5) b = min { ( b( d ) ) : b(d) B( mb -1) } In [Sotskov, Dolgui, Portmann, 2006], the following formula for calculating the exact value of stability radius (t) b has been derived.

b b Theorem 2: If optimality of line balance b B (t) is stable, then (t)= min{,b } with being defined in opt b (4) and b in (5).

Let denote the smallest integer greater than or equal to a. Theorem 2 implies the following corollaries.

a t(V ) t(V ) - c( mb -1) b Corollary 2: If m =, then b( t ) min { ; }.

b ~ c n t(V ) t(V ) - c( mb -1) b b Corollary 3: If m = and, then b( t ) =.

b ~ c n b ~ Corollary 4: If b B (t), then b( t ) min {, maxiV ti}.

opt ~ ~ Corollary 5: If b B (t), then b( t ) min {c - maxiV t, maxiV t }.

opt j j b Corollary 6: If b B (t) and b( d ) B( mb -1), then b( t ) min{, ( b( d ) )}.

opt Stability of an Optimal Line Balance for SALBP-In this section, we consider the Simple Assembly Line Balancing Problem when number m of stations is fixed while the cycle time has to be minimized. In other words, we consider SALBP-2: to find an optimal balance of the assembly line for a given number m of stations, i.e., to find a feasible assignment of all operations V to exactly m stations in such a way that the cycle-time c is minimal. For SALBP-2, line balance b is optimal if along with r conditions 1 and 2, it has the minimal cycle time. We denote the cycle time for line balance b with the vector t of r m operation times as c(b, t): c(b, t) = max ti. For SALBP-2, optimality of line balance b=b with vector t of r r s k=iVkbr the operation times may be defined as the following condition.

Condition 4: c(b, t) = min{c(b, t) : b B(t)}, where B(t) = {b, b, Е, b } is the set of all line balances.

s r r 0 1 h For SALBP-2, the formal definition of the stability radius of an optimal line balance may be introduced as follows.

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

~+1 ~+In Definition 2, vector t = (tn, tn, Е, tn ) of the automated operation times and vector ~,t ~ * * ~ t = ( t ) = ( t1,t2,Е,tn ) of all the operation times are fixed, while vector t = ( t1, t*,..., t* ) of the manual 2 n ~ ~ n operation times may vary within the intersection of the closed ball O ( t ) with the space. For each optimal R+ ~ line balance b B (t), we can define a set W(b ) of all subsets Vkbr, k {1, 2, Е, m }, such that r opt r ti = c(b,t). It should be noted that set W(b ) may include the empty set as its element.

r iVkbr 304 Intelligent Systems In [Sotskov et al, 2005], the following claims have been proven.

~ Theorem 3: Let inequality t > 0 hold for each manual operation i V. Then for line balance b B(t), equality i s b (t) = 0 holds if and only if there exists a line balance b B (t) such that condition W(b ) W(b ) r opt s r s does not hold.

Corollary 7: If B (t) = {b }, then b (t) > 0.

opt s s If there exists an index k {1, 2, Е, m} such that t < c(b,t), i (6) iVkb~ ~ then we set = {c(b0,t) - max{ :Vkb W (b0)}} n. Due to (6), the strict inequality (b0) > 0 must (b0) ti iVkb~ hold. If = c(b,t) for each index k {1, 2, Е, m}, then we set = min{t : i V }. We denote 0 (b0) i ti iVkbc(bs,t) - c(b0,t) = min{(b ): b B \ B(t)}, where (b ) =. Theorem 3 implies the following claim.

s s s ~ n Corollary 8: If b (t) > 0, then b (t) min{, (b0) }.

s s The problem of calculating exact value of stability radius b(t) is close to calculating stability radius of the optimal schedule for the makespan criterion (see [Sotskov, 1991; Sotskov, Tanaev, Werner, 1998]).

Conclusion and Recommendations In this paper, the known results on stability analysis of an optimal line balance are presented. To this end, we used the notion of stability radius, which is similar to the stability radius of an optimal schedule introduced in [Sotskov, 1991] for scheduling problems. (A survey of known results on stability analysis in machine scheduling is given in [Sotskov, Tanaev, Werner, 1998].) If stability radius of line balance b is strictly positive, then any ~ independent changes of the operation times t, j V, within the ball with this radius, definitely keep the j optimality of line balance b. On the other hand, if stability radius of b is equal to zero (i.e., if the optimality of line balance b is unstable, see Theorems 1 and 3), then some even small changes of the processing times of all or a portion of the manual operations may deprive the optimality of line balance b. It is worth noting that all conditions presented in this paper (except Theorems 2 and 3 and Corollaries 1 and 8) may be tested in polynomial time, which is important for real-world assembly lines with large numbers of operations and stations. Moreover, for b exact value of stability radius, feasibility of the line balance b, which is defined by the value, may be tested in polynomial time even in Theorem 2.

In practice, the tendency at the design stage must be to find optimal line balance for which stability is as much as possible. Of course, the common objective is to assign to each station a set of operations with roughly the same total operation time (see [Bukchin, Tzur, 2000; Erel, Sarin, 1998; Lee, Johnson, 1991; Sarin, Erel, Dar-El, 1999]).

However, due to the above results, we have to defer stations with manual operations and stations without manual operations. Theorem 1 shows that for the station with manual operations it is desirable to have some slack between cycle time and station time. The larger this slack is, the large stability radius of the line balance may be.

On the other hand, for the stations with only automated operations, such a slack may be as small as possible, which gives the possibility to increase slacks for stations loaded by manual operations. Since the stability radius (t) cannot be larger than c/2, one has to pay special attention to the manual operations with possible variations b of processing times more than c/2 (such operations may cause instability of optimality of the line balance at hand). If it is possible at the design stage, such an operation has to be divided into shorter manual operations.

If line balance will be used for a long time for assembling the same finished product, it is desirable at the design stage, to construct several optimal line balances, and select among them the one with the best stability characteristics. So, it is useful to develop algorithms, which construct a set of optimal line balances (instead of only one optimal line balance), in order to carry out a stability analysis for them. Or, better yet, it is useful to XII-th International Conference "Knowledge - Dialogue - Solution" include in the branch-and-bound or other algorithms used for SALBP-1 and SALBP-2 specific rules in order to ~ construct optimal line balance with larger stability radius. In a concrete study, the set V of manual operations ~ can be reduced (e.g., only critical manual operations may be considered) or, on the contrary, set V may be completed by some unstable automated operations. By changing the set of operations with variable times, the designer of the assembly line can study the influence of different operations on stability of optimality and feasibility of line balances.

In [Sotskov, Dolgui, 2001], slightly different definitions of stability radius and stability ball of an optimal line ~ balance have been used for SALBP-1. Namely, it was assumed that O ( t ) R+ n. Therefore in that paper, b ~} generally smaller stability radii were obtained (in particular, it cannot be greater than min{ ti : i V ).

The above Definition 1 seems to be more appropriate for practical assembly lines.

Acknowledgements This research was supported by ISTC (Project B-986). The author would like to thank Prof. Alexandre Dolgui, Prof. Marie-Claude Portmann, and Prof. Frank Werner for joint research in stability analysis.

Bibliography [Baybars, 1986] I. Baybars, A survey of exact algorithms for the simple assembly line balancing problem, Management Science 32 (8) (1986) 909-932.

[Bukchin, Tzur, 2000] J. Bukchin, M. Tzur, Design of flexible assembly line to minimize equipment cost, IIE Transactions (2000) 585-598.

[Erel, Sarin, 1998] E. Erel, S.C. Sarin, A survey of the assembly line balancing procedures, Production Planning & Control (5) (1998) 414-434.

[Garey, Johnson, 1979] M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, USA, 1979.

[Lee, Johnson, 1991] H.F. Lee, R.V. Johnson, A line-balancing strategy for designing flexible assembly systems, The International Journal of Flexible Manufacturing Systems 3 (1991) 91-120.

[Sarin, Erel, Dar-El, 1999] S.C. Sarin, E. Erel, E.M. Dar-El, A methodology for solving single-model, stochastic assembly line balancing problem, OMEGA - International Journal of Management Science 27 (1999) 525-535.

[Scholl, 1999] A. Scholl, Balancing and Sequencing of Assembly Lines, Heidelberg: Physica-Verlag, Germany,1999.

[Sotskov, 1991] Yu.N. Sotskov, Stability of an optimal schedule, European Journal of Operational Research 55 (1991) 91-102.

[Sotskov, Dolgui, 2001] Yu.N. Sotskov, A. Dolgui, Stability radius of the optimal assembly line balance with fixed cycle time.

In: Proceedings of the IEEE Conference ETFAТ2001 (2002) 623-628.

[Sotskov, Dolgui, Portmann, 2006] Yu.N. Sotskov, A. Dolgui, M-C. Portmann, Stability of an optimal balance for an assembly line with fixed cycle time, European Journal of Operational Research 168 (2006) 783-797.

[Sotskov, et al. 2005] Yu.N. Sotskov, A. Dolgui, N. Sotskova, F. Werner, Stability of optimal line balance with given station set. In: Supply Chain Optimisation (2005) 135-149.

[Sotskov, Tanaev, Werner, 1998] Yu.N. Sotskov, V.S. Tanaev, F. Werner, Stability radius of an optimal schedule: A survey and recent developments, Chapter in: G. Yu (Ed.) УIndustrial Applications of Combinatorial OptimizationФ 16, Kluwer Academic Publishers, Boston, MA, USA, 1998, 72-108.

AuthorТs Information Yuri N. Sotskov - Professor, DSc, United Institute of Informatics Problems of National Academy of Sciences of Belarus, Surganova str., 6, Minsk, Belarus; e-mail: sotskov@newman.bas-net.by 306 Intelligent Systems ОЦЕНКА РЕАЛИЗУЕМОСТИ АЛГОРИТМОВ ДЕЯТЕЛЬНОСТИ ЭКИПАЖА АНТРОПОЦЕНТРИЧЕСКОГО ОБЪЕКТА ПРИ РАЗРАБОТКЕ СПЕЦИФИКАЦИЙ ЕГО БОРТОВЫХ АЛГОРИТМОВ Борис Е. Федунов Аннотация. При проектировании спецификаций бортовых алгоритмов системообразующего ядра антропоцентрического объекта (алгоритмов, реализуемые на бортовых цифровых вычислительных машинах, алгоритмы деятельности экипажа (АДЭ)) возникает задача оценки возможности выполнения экипажем определившихся АДЭ. Для решения этой задачи вся деятельность экипажа структурирована по видам его работ (принятие решений, участие в системах слежения, реализация решений) и проведена количественная оценка временных затрат экипажа на их выполнение.

Предложен критерий оценки реализуемости АДЭ экипажем.

Ключевые слова: алгоритмы деятельности экипажа (АДЭ): решения, операции слежения, диспетчеризация; оценки времени выполнения АДЭ, критерии реализуемости Введение При проектировании спецификаций бортовых алгоритмов системообразующего ядра антропоцентрического объекта (Антр/объекта) инженерами - разработчиками определяются состав и облик алгоритмов, реализуемых на бортовых цифровых вычислительных машинах (БЦВМ-алгоритмы), и алгоритмов реализуемых оператором, членом экипажа Антр/объекта (алгоритмы деятельности экипажа (АДЭ)). При этом возникают задачи:

- разработать АДЭ с глубиной, позволяющей оценить их реализуемость (выполнимость) оператором;

- разработать критерии оценки реализуемости АДЭ;

- создать компьютерную систему, позволяющую инженеру-практику проводить оценку реализуемости конкретного состава АДЭ.

Проектирование спецификаций бортовых алгоритмов в настоящее время опирается на использование математической модели (ММ) Антр/объекта [1], представляющей его внутренний семантический облик через три глобальных уровня управления (ГУУ), а весь объем работы Антр/объекта - через сеансы функционирования. На Антр/объекте различают уровень оперативного целеполагания (первый глобальный уровень управления I ГУУ), уровень определения рационального способа достижения оперативно поставленной цели (второй глобальный уровень управления II ГУУ), уровень реализации принятого способа достижения оперативно поставленной цели (третий глобальный уровень управления III ГУУ).

I ГУУ и II ГУУ составляют семантическую суть системообразующего ядра Антр/объекта.

Каждый сеанс функционирования в этой ММ представляется семантической сетью типовых ситуаций (ТС), выбираемых из единого множества ТС. В свою очередь ТС представима через семантическую сеть проблемных субситуаций (ПрС/С).

Структура деятельности оператора в техническом антропоцентрическом объекте При системном проектировании спецификаций алгоритмов бортового интеллекта деятельность оператора Антр/объекта представляется через следующие составляющие. Оператор на борту Антр/объекта в рамках активизированной концептуальной модели поведения выполняет следующие типы работ:

а) принимает решения по оперативно возникающей проблеме, б) реализует эти решения, в) участвует в различных операциях слежения как элемент следящей системы [3 - 7]. В процессе своей работы он может неоднократно менять свою концептуальную модель поведения.

XII-th International Conference "Knowledge - Dialogue - Solution" Вся необходимая для деятельности оператора информация представляется ему на индикаторах информационно управляющего поля (ИУП) кабины экипажа и/или сообщается ему через кабинные речевые информаторы. Реализация решений и участие в операциях слежения осуществляется экипажем через органы управления ИУП.

Исходной информацией для проектирования АДЭ служат:

Pages:     | 1 |   ...   | 69 | 70 | 71 | 72 | 73 |   ...   | 82 |    Книги по разным темам