Национальная академия наук Беларуси

Размер3.17 Mb.
1   2   3   4   5   6   7   8   9   ...   16


    1. Ben Ammar, O. D'un système d'assemblage multi-niveau sous incertitudes des délais d'approvisionnement / O. Ben Ammar, H. Marian, A. Dolgui // Actes de la conférence internationale Modélisation, Optimisation et Simulation (MOSIM'12). – Bordeaux, 2012. – 10 p.

    2. Dolgui, A. Supply planning for single-level assembly system with stochastic component delivery times and service level constraint / A. Dolgui, M.A. Ould Louly, F. Hnaien // International Journal of Production Economics. – 2008. – Vol. 115(1). – P. 236–247.

    3. Planning order release dates for multilevel linear supply chain with random lead times / A. Dolgui [et al.] // Systems Science. – 2007. –Vol. 31(1). – P. 19–25.

    4. Dolgui, A. Supply planning under uncertainties in MRP environments: A state of the art / A. Dolgui, C. Prodhon // Annual Reviews in Control. – 2007. – Vol. 31. – P. 269–279.

    5. Dolgui, A. A model for supply planning under lead time uncertainty / A. Dolgui, M.A. Ould Louly // International Journal of Production Econo-mics. – 2002. – Vol. 78. – P. 145–152.

UDC 519.8


S.Deleplangue, A.Quilliot, H.Toussaint

LIMOS, UMR CNRS 6158, Bat. ISIMA, Université Blaise Pascal, France

e-mail: alain.quilliot@isima.fr
1. RCPSP Problems and their Variants

Dealing with Resource Constrained Project Scheduling Problems (RCPSP: [1, 2]) means scheduling a set of tasks V, subject to temporal and cumulative resource constraints. This problem may be related to industrial activity planning [1]). RCPSP problems are difficult one, most often NP-hard. Linking RCPSP and Network Flow has already been done in [3, 2]. So, our goal is here to make appear the way this link may help in designing fast and efficient generic methods, and to apply them to RCPSP extensions involving:

  • Routing Delays/Costs [1], where resources circulate between tasks

  • Financial Resources [1], where tasks may produce or destroy resources.

2. Network flow related to RCPSP instances

Given a network G = (Z, E), with node set Z and arc set E, together with a Rp valued function defined on the node set Z, we say that a Rp-valued E-indexed vector f is a -flow vector iff for any z in Z:

 e in v fe = for any z in  Z,  e in v fe = (v)

(Extended Kirshoff Law)

Any RCPSP instance I gives rise to a Task Network N(I) whose node set is the task set of I augmented with two auxiliary nodes, and the arc set comes in a natural way (figure). Following [1], one derives from any feasible schedule T a flow vector F defined on N(V). The pair (F, T) is called a Timed Flow and we state that solving the RCPSP instance I means computing, on the Task network N(I), a Timed flow (F, T) such that TEnd is the smallest possible.

Turning RCPSP solution into Network Flow

3. Methods: a generic insertion process

Our algorithmic generic approach involves an Insertion/Removal component, and a Cut/Ordering component.

The Insertion/Removal component: At any time during the process, we are given an Inserted Task subset W, and with a current timed flow (F, T). Performing an Insertion means picking up v0 in V- W, and extending (F, T) for W  {v0}. The related mechanism involves a Cut, i.e. a partition of W into 2 subsets U and W - U, such that no flow amount goes from to (W - U)  {End} to U  {Start}. The Insertion Flow problem is about computing optimal related flow values. Performing a Removal means reversing this operation. We show that both the Insertion Flow and Removal Problems are in P-Time.

The Cut component: a crucial point is about the choice of the cut U. We check that the search for a best Cut is NP-Complete. Still, we designed several heuristics for this problem, based on Min-Cut approximations.

The Linear Ordering component: we derive a greedy RCPSP-Insertion Scheme from above by linearly ordering V and inserting the tasks of V according to this order. While, one gets good results through random sorting for Standard RCPSP, dealing with financial resources is harder, since computing a feasible schedule is NP-Complete. We handle this through filtering rules.

Local Search: The above Insertion mechanism gives rise in a generic way to a local search operator: given a timed flow (F, T), we pick up some (small) subset S of V, remove it and insert it again into (F, T). The subset S is the parameter of the local operator Transform-Insertion, main component of the local search LS-RCPSP-Insertion Scheme algorithmic scheme.

Numerical Tests: For every test package, derived from PSPLIB, we computed Gap = the gap between our best value obtained through N-rep replications on PC AMD opteron 2.1GHz, and we got, in case of Standard RCPSP table.

Greedy Scheme and Local Search Mean Results



N-Rep Greedy

CPU-Time (s) Greedy

Gap (%)


Gap (%)

Local Search

10 Rep

Time (s)

Local Search

10 Rep













Comment: those results are good, given the generic features of the algorithms.

1. Hartmann, S. A survey of variants and extensions of the RCPS / S. Hartmann, D. Briskom // EJOR 207. – 2010. – P. 1–14,

2. Herroelen, W. Project Scheduling-Theory/Practice / W. Herroelen // Prod. Oper. Manag. – 2006. – 14, 4. – P. 413–432.

3. Artigues, C. Insertion techniques for static and dynamic RCPSP / C. Artigues, P. Michelon, S. Reusser // EJOR 149. – 2003. – P. 249–267.

4. Kolisch, R. Characterization/generation of a large class of RCPSP Problems / R. Kolisch, A.Sprecher, A.Drexel / Manag. Sci. – 1995. – 41-10. – P. 1693–1703.

UDC 519.8

Optimal (s,S) Inventory Policy under Markov

Modulated Non-Stationary Demand: A Computational

E. Gurkan, Y. Malli, S. A. Tarim

Hacettepe University, Department of Management, Ankara, Turkey

Inventory management is the process of overseeing of orders and matching supply with demand in order to maximize total profit or minimize total cost. One of the earliest studies in inventory management is due to Harris, who proposed the EOQ formulae, which is concerned with minimizing fixed ordering and linear holding costs under deterministic and static demand [1]. This early paper followed by many well-known studies. One of the most important contributions to the field is made by Scarf, who proved the optimality of (S,s) type policies with stochastic period demands, holding and penalty costs and fixed ordering costs [2]. According to the (S,s) policy, at the beginning of a period if the stock level is below a critical point s, then inventory level must be increased up to the order-up-to-level S.

Most of the earlier works on (s,S) policy assume period demands independent of each other. In most practical settings, however, period demand follows a Markovian structure, realised demand in period t determines the distribution of demand in period t+1. Using Markov modulated models, it is possible to define the demand model that is affected by uncertain environmental factors such as political situations, the state of economy, etc.

Sethi and Cheng proved that under Markovian demand the optimal inventory policy is still an (s,S) type control policy, with a distinction that (s,S) parameters are state dependent [3].

In this paper we will provide a stochastic dynamic programming model for computing exact policy parameters. This modeling framework can tackle only small size instances, however still this approach will be useful to gauge new heuristics that will be developed to manage Markov modulated inventory systems in the future.

The paper proposes an algorithm and its implementation, and also presents numerical instances and their optimal solutions to provide insight into the Markov modulated inventory systems.


1. Harris, F. Operations and Cost (Factory Management Series) / F. Harris. – Chicago : A.W. Shaw and Company, 1913.

2. Scarf, H. The Optimality of (S,s) Policies in the Dynamic Inventory Problem, Mathematical Methods in the Social Sciences / H. Scarf ; ed. by K. Arrow, S. Karlin, and P. Suppes. – Stanford, CA : Stanford University Press, 1960. – Р. 196–202.

3. Sethi, S.P. Optimality of (S,s) policies in Inventory Models with Markovian Demand / S.P. Sethi, F. Cheng // Operations Research. – 1997. –45(6). – Р. 931–939.

UDC 519.8
M.L. Bentaha, O. Battaïa, A. Dolgui

École Nationale Supérieure des Mines, EMSE-Fayol,

CNRS UMR6158, LIMOS, F-42023 Saint-Étienne, France

e-mail: {bentaha,battaia,dolgui}@emse.fr
The purpose of the study is to consider The Disassembly Line Balancing Problem (DLBP) under task times uncertainty and to develop a solution method.
1. Problem formulation
The DLBP can be defined as follows [3]. There is a product that must be disassembled. The disassembly process is defined by a set of possible tasks. Process alternatives are represented by a precedence graph where two types of arcs exist: AND and OR. The first type imposes a mandatory precedence relation between two tasks i and j, i.e., if i precedes j then it must be completed when j is started. OR-relations allow modeling of optional precedence dependencies where only one option is chosen for the final solution [4]. The given set of tasks is to be assigned to a sequence of identical workstations taking into account the existing precedence constraints defined by AND/OR graph. Moreover, the cycle time constraint has to be taken into account. This constraint imposes a limit on total processing time of the tasks assigned to the same workstation. The goal is to minimize the number of workstations required to assign all tasks respecting these constraints.

In practice, the task processing times can vary due to the different end-of-life conditions of the items to be disassembled as well as due to the manual execution of the tasks by operators. However, to the best of our knowledge, no work exists in the literature taking into account stochastic nature of disassembly tasks [5]. To fill this gap, we consider this problem under the assumption that the task processing times are random variables with known normal probability distributions. As a consequence, the sum of the processing times may exceed the objective cycle time for certain realizations of random variables [2]. To take this into account, the objective function is composed of the cost of the workstations required plus the penalty costs induced by the excess of the cycle time limit.

2. Solution method
A two-stage stochastic linear mixed integer program with fixed recourse is developed to deal with task times uncertainty. In order to solve the problem, the L-shaped method, which is one of the most effective methods for resolving the two-stage stochastic problems with recourse [1] is proposed. This method is tested on a series of benchmark problems found in the literature.
Since promising results have been obtained for the benchmark problems tested, the following step would be to test the proposed solution method on a dataset of industrial problems in order to evaluate its practical efficiency. Then, the model can be considered for the disassembly task times given by, for example, triangular distribution. Another promising perspective is to consider the hazardous disassembly tasks in order to reduce their environmental impact. Also, the formulation considered can be easily adapted for the stochastic assembly line balancing problem.
1. Birge, J.R. Stochastic Programming Computation and Applications / J.R. Birge // INFORMS Journal on Computing. – 1997. – Vol. 9, № 2. – P. 111–133.

2. Dolgui, A. Supply Chain Engineering: Useful Methods and Techniques / A. Dolgui, J.-M. Proth. – Springer, London, 2010. – 541 p.

3. Güngör, A. Disassembly Line in Product Recovery/ A. Güngör, S.M. Gupta // IJPR. – 2002. – Vol. 40, № 11. – P. 2569–2589.

4. Koc, A. Two Exact Formulations for Disassembly Line Balancing Problems with Task Precedence Diagram Construction Using an AND/OR Graph / A. Koc, I. Sabuncuoglu, E. Erel // IIE Transactions. – 2009. – Vol. 41, № 10. – P. 866–881.

5. McGovern, S.M. The Disassembly Line: Balancing and Modeling / S.M. McGovern, S.M. Gupta. – McGraw Hill, New York, 2011. – 373 p.

UDC 519.8

A polynomial-time heuristic for the dynamic lot

sizing problem with remanufacturing
Onur A. Kilic

Hacettepe University, Ankara, Turkey

e-mail: onuralp@hacettepe.edu.tr

In the recent years remanufacturing practices have accelerated due to increasing environmental awareness. Firms implementing remanufacturing practices recover used products returned from customers; and process them into reusable products. However, matching supply to demand is more difficult in integrated manufacturing and remanufacturing environments due to the need of coordinating manufacturing and remanufacturing operations in the context of inventory management. Hence, the applicability of traditional inventory control approaches in such integrated systems is rather limited. This has motivated research efforts towards extending traditional inventory control problems with remanufacturing options.

An important problem considered in this context is the Economic Lot-Sizing Problem with Returns (ELSR). The problem can be described as follows. A retailer faces deterministic dynamic demands and returns over a finite planning horizon. The demand can be met via two alternative sources: manufacturing orders for new products, and remanufacturing orders for returned products. It is assumed that new and remanufactured products are identical, and hence, both are regarded to be serviceable. The retailer holds both serviceable and return inventories. When a manufacturing or a remanufacturing order is placed, it incurs a fixed setup cost plus a production cost proportional to the order size. Also, a holding cost is incurred for each unit of serviceable and return carried in inventory from one period to the next. The retailer aims to minimize the total costs over the planning horizon. The ELSR problem has recently received increasing attention in the literature and shown to be NP-hard [1].

In the current study, we propose a new heuristic for the ELSR problem. The heuristic builds on the zero-inventory property for manufacturing and the all-or-nothing property for remanufacturing. It is known that the optimal solution of the problem does not always satisfy the aforementioned properties [2]. Thus, the proposed heuristic corresponds to an over-constrained version of the problem, and provides an upper bound for the optimal cost. The current study contributes to the literature by providing a polynomial-time algorithm to compute the aforementioned heuristic, and showing that the associated optimality gap is, in general, very small. We conduct a numerical study where the cost performance of the new heuristic is compared against the optimal solution as well as the earlier heuristics proposed in [2] and [3]. We show that the new heuristic outperforms the earlier heuristics and provides near-optimal results for all test instances considered. In particular, the new heuristic yields an optimality gap smaller than 5 % over 99 % of the test instances. These suggest that the proposed heuristic, which also comes with properties that could ease the coordination of manufacturing and remanufacturing operations, is a viable alternative to the optimal policy.

1. Economic lot-sizing with remanufacturing: complexity and efficient formulations / M.J. Retel Helmrich [et al.] // Technical Report. – Rotterdam Econometric Institute, 2010.

2. Teunter, R.H. Dynamic lot sizing with product returns and remanufacturing / R.H. Teunter, Z.P. Bayindir, W. Van Den Heuvel // International Journal of Production Research. – 2006. – № 44. – Р. 4377–4400.

3. Schulz, T. A new Silver-Meal based heuristic for the single-item dynamic lot sizing problem with returns and remanufacturing / T. Schulz // International Journal of Production Research. – 2011. – № 49. – Р. 2519–2533.

УДК 62-83



А.А. Приходько, А.В. Нестеров, С.В. Нестеров

Кубанский государственный технологический университет, Краснодар, Россия

В докладе приведены результаты вычислительного эксперимента, суть которого состоит в решении задачи Коши для однородного уравнения Матье:– при различных сочетаниях коэффициентов a и q. Анализ полученных таким образом функций должен ответить на вопрос о том, как они связаны с коэффициентами уравнения a и q. Эта проблема актуальна для нестационарных объектов управления, главным условием эффективности которых является требование [1]. Предполагается, что данное требование удовлетворяется соответствующим выбором коэффициентов a и q. Поиск зависимостей спектральных характеристик от сочетания коэффициентов a и q составляет предмет настоящего исследования. Количественно характеризовать названные характеристики удобно глубиной модуляции m, несущей частотой и частотой модуляции . Исследования показали, что глубина частотной модуляции очень мала, в связи с чем это явление далее не рассматривается.

нализ показывает, что глубина амплитудной модуляции лежит в пределах 0 < m < 0,35. Общее представление о влиянии соотношения коэффициентов уравнения Матье на глубину модуляции устойчивых колебаний дает рис. 1.

Рис. 1. Зависимость глубины модуляции от коэффициентов a и q
Согласно исследованиям, несущая частота находится в диапазоне . При очень малых q несущая частота ω равна собственной частоте уравнения Матье (), при увеличении q частота колебаний возрастает. На рис. 2 изображена зависимость несущей частоты от коэффициента q при неизменных a.

Рис. 2. Диаграмма несущей частоты
Таким образом, проведенные исследования позволяют систематизировать решения однородного уравнения Матье в первой зоне устойчивости. Зависимости, приведенные в докладе, могут служить для приближенной оценки решений уравнения Матье без его интегрирования.
Список литературы
1. Анализ решений уравнения Матье при моделировании нестационарного электропривода / А.А. Приходько, А.В. Нестеров, С.В. Нестеров // XXIII Международная инновационно-ориентированная конференция молодых ученых и студентов : труды междунар. конф., Москва, 14–17 декабря 2011 г. – М. : Изд-во ИМАШ РАН, 2011. – С. 211.

УДК 004.946; 629.78; 658.512.011.56: 004.42



С.В. Гусев1, А.В. Лемзиков2

1Объединенный институт проблем информатики НАН Беларуси, Минск

e-mail: gsv@tut.by;

2Белорусский государственный университет информатики
и радиоэлектроники, Минск
Большинство конечно-элементных расчетов, проводимых инженерами, не учитывает технологию изготовления детали, в частности различных видов термической обработки. Для оценки напряженно-деформированного состояния (НДС) детали и изделия в целом довольно часто применяется несколько программных продуктов, каждый из которых эффективно решает свой круг задач [1].

Узкоспециализированные программные продукты по компьютерному моделированию процесса термической обработки закалки токами высокой частоты (ТВЧ), в частности TERMOSIM [2], позволяют определить рациональные режимы термической обработки и НДС детали. Однако формат представления данных в этом пакете не разрешает непосредственно использовать НДС детали после закалки ТВЧ в дальнейших расчетах в пакете конечно-элементного анализа LS-DYNA.

Для обеспечения передачи НДС детали после закалки ТВЧ из пакета TERMOSIM в пакет LS-DYNA разработаны специализированные программные средства, обеспечивающие перенос значений тензора напряжений с тетраэдальных элементов TERMOSIM (сетка А) на HEX-элементы LS-DYNA (сетка Б).

С целью повышения эффективности решения задачи в LS-DYNA конечно-элементная модель построена на базе HEX-элементов, что позволяет уменьшить размер расчетного файла, а следовательно, и время расчета. Формирование трехмерной геометрической модели деталей колесной передачи и генерация соответствующих сеток для LS-DYNA проводятся в программе ANSYS ICEM CFD.

Перенос результатов из одной сетки в другую состоит из следующих этапов:

1. В случаях когда для уменьшения вычислительной сложности или увеличения точности моделирования анализ НДС при закалке осуществлялся на области детали, выделенной из всей геометрии исходя из соображений симметрии, производится достроение сетки А на основании информации о симметрии исследуемой детали.

2. На сетках А и Б выбираются по две опорные точки с совпадающими координатами, по которым проводится совмещение конечно-элементных сеток.

3. Для каждого узла сетки Б производится интерполяция компонентов тензора напряжений по значениям узлов сетки А.

4. Полученные значения тензора напряжений узлов сетки Б используются в качестве начального напряженного состояния при моделировании механической задачи в LS-DYNA.

В качестве объекта исследования выступают элементы колесной передачи грузового автомобиля семейства МАЗ-6422. Механизм состоит из сателлита и коронной шестерни. Геометрические параметры сателлита для двух программных продуктов совпадают. Для сателлита учитывается НДС, возникающее в детали после закалки ТВЧ.

Использование результатов расчета НДС в TERMOSIM позволяет средствами LS-DYNA определить максимальный крутящий момент в конструкции с учетом образовавшихся при закалке ТВЧ напряжений.

Каталог: event
event -> Доклад о ситуации с обеспечением прав человека в европейском союзе
event -> Разнарядка
event -> Занятие первое. Работа с файловым менеджером Total Commander
event -> Инструменты ретуши Adobe Photoshop
event -> Семинар будет проходить 27 и 28 января. Курс «Скульптура бровей»
event -> Пиганов Михаил Николаевич профессор кафедры ктэсиУ, член оргкомитета; Зеленский Владимир Анатольевич профессор кафедры ктэсиУ, отв секретарь оргкомитета. Пленарное заседание

Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8   9   ...   16

База данных защищена авторским правом ©vossta.ru 2019
обратиться к администрации

    Главная страница