Objective: to implement the neighborhood descent heuristic approach into solving the lot-sizing problem.Methods: a variable neighborhood descent heuristic approach and a framework of lot-sizing problem.Results: dynamic lot-sizing problem is supposed to be an NP-hard problem a problem for which there is no known polynomial algorithm, so the time to find a solution grows with a problem size. In the article, we explain the basic lot-sizing, lot-sizing in closed-loop, describe methods used by other researchers, and provide reasoning for using a variable neighborhood descent heuristic method. Implementation of the method is presented in a numerical example. Application of the method significantly reduces estimation time when searching for lot-sizing problem solution. Application of the method significantly reduces estimation time when searching for lot-sizing problem solution.Scientific novelty: the method may significantly reduce time expenses during the solution of the lot-sizing problem. Practical significance: the method may be implemented for solving the lot-sizing problem in various industries, such as pulp and paper, consumer goods industry and heavy industry.

Анотація наукової статті з математики, автор наукової роботи - Poliakova Irina Yu.


Евристика зниження чергуються околиць для задачі визначення величини різнорідною партії в разі повторного виробництва

Мета: демонстрація застосування евристичного методу дослідження околиць до проблеми визначення розміру партії.Методи: евристичний метод дослідження окрестностей.Результати: проблема визначення розміру партії є завданням, для якої не існує відомого полиномиального алгоритму, таким чином, час знаходження рішення зростає з розміром завдання. У статті розкрито основні методи визначення розміру партії, розміру партії з урахуванням повернення продукції, описані методи, використовувані іншими дослідниками, і наведені аргументи для використання евристичного методу дослідження околиць. Принцип роботи методу представлений на практичному прімере.Научная новизна: метод дозволяє значно скоротити тимчасові витрати при вирішенні задачі визначення розміру партіі.Практіческая значимість: метод може бути застосований для вирішення завдання визначення розміру партій в різних галузях, в тому числі целюлозно-паперової промисловості, виробництві споживчих товарів, важкої промисловості.


Область наук:
  • Математика
  • Рік видавництва: 2020
    Журнал: Актуальні проблеми економіки та права
    Наукова стаття на тему 'A VARIABLE NEIGHBORHOOD DESCENT HEURISTIC FOR A MULTI-ITEM LOT-SIZING PROBLEM WITH REMANUFACTURING'

    Текст наукової роботи на тему «A VARIABLE NEIGHBORHOOD DESCENT HEURISTIC FOR A MULTI-ITEM LOT-SIZING PROBLEM WITH REMANUFACTURING»

    ?ISSN 1993-047Х (Print) / ISSN 2410-0390 (Online)

    УДК 519: 658: 004

    DOI: http://dx.doi.org/10.21202/1993-047X.14.2020.1.1.174-185

    І. Ю. ПОЛЯКОВА1

    1 Санкт-Петербурзький державний університет, м Санкт-Петербург, Росія

    евристика зниження чергуються околиць для задачі визначення величини різнорідною партії в разі повторного виробництва

    Полякова Ірина Юріївна, аспірант, Санкт-Петербурзький державний університет

    Адреса: 191123, м.Санкт-Петербург, вул. Чайковського, 62, тел .: +7 (812) 363-64-94

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    ORCID: http://orcid.org/0000-0002-7278-9114

    Web of Science Researcher ID: https://publons.com/researcher/2989389/irina-poliakova/

    Мета: демонстрація застосування евристичного методу дослідження околиць до проблеми визначення розміру партії.

    Методи: евристичний метод дослідження околиць.

    Результати: проблема визначення розміру партії є завданням, для якої не існує відомого полиномиального алгоритму, таким чином, час знаходження рішення зростає з розміром завдання. У статті розкрито основні методи визначення розміру партії, розміру партії з урахуванням повернення продукції, описані методи, використовувані іншими дослідниками, і наведені аргументи для використання евристичного методу дослідження околиць. Принцип роботи методу представлений на практичному прикладі.

    Наукова новизна: метод дозволяє значно скоротити тимчасові витрати при вирішенні задачі визначення розміру партії.

    Практична значимість: метод може бути застосований для вирішення завдання визначення розміру партій в різних галузях, в тому числі целюлозно-паперової промисловості, виробництві споживчих товарів, важкої промисловості.

    Ключові слова: окрестностний спуск; проблема визначення розміру партії; переробка; багатопродуктової виробництво; евристичний підхід; замкнутий логістичний цикл; зворотна логістика

    Конфлікт інтересів: автором не заявлений.

    Mill Mill ММ Mill ММ Mill ММ Mill Mill ММ Mill ММ Mill ММ Mill ММ Mill ММ M

    Як цитувати статтю: Полякова І. Ю. Евристика зниження чергуються околиць для задачі визначення величини різнорідною партії в разі повторного виробництва // Актуальні проблеми економіки та права. 2020. Т. 14, № 1. С. 174-185. DOI: http://dx.doi.Org/10.21202/1993-047X.14.2020.1.1.174-185

    IMMMMIMMMMIMMMMIMMMMIMMIMMMMIMMMMIMMMMIMMMMIMMMMIMMMMIMMMMIMMIMMMMIMMMMIMMMMIMMMMIMMMMIMMMMIMMMMIMMIMMMMIMMMMIM

    I. YU. POLIAKOVA1

    'Saint-Petersburg State University, Saint-Petersburg, Russia

    A VARiABLE NEiGHBoRHooD DEscENT HEURisTic

    for a multmtem lot-sizing problem with remanufacturing

    Irina Yu. Poliakova, post-graduate student, Saint-Petersburg State University (Saint-Petersburg), Russia

    Address: 191123, Saint-Petersburg, Tchaikovskogo st., 62, tel.: +7 (812) 363-64-94

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    ORCID: http://orcid.org/0000-0002-7278-9114

    Web of Science Researcher ID: https://publons.com/researcher/2989389/irina-poliakova/

    ........................................................................... ISSN 1993-047Х (Print) / ISSN 2410-0390 (Online) ...........................................................................

    Objective: to implement the neighborhood descent heuristic approach into solving the lot-sizing problem. Methods: a variable neighborhood descent heuristic approach and a framework of lot-sizing problem. Results: dynamic lot-sizing problem is supposed to be an NP-hard problem - a problem for which there is no known polynomial algorithm, so the time to find a solution grows with a problem size. In the article, we explain the basic lot-sizing, lot-sizing in closed-loop, describe methods used by other researchers, and provide reasoning for using a variable neighborhood descent heuristic method. Implementation of the method is presented in a numerical example. Application of the method significantly reduces estimation time when searching for lot-sizing problem solution. Application of the method significantly reduces estimation time when searching for lot-sizing problem solution.

    Scientific novelty: the method may significantly reduce time expenses during the solution of the lot-sizing problem. Practical significance: the method may be implemented for solving the lot-sizing problem in various industries, such as pulp and paper, consumer goods industry and heavy industry.

    Keywords: Neighborhood descent; Lot-sizing problem; Remanufacturing; Multi-item lot-sizing; Heuristic approach; Closed-loop; Reverse logistics

    Conflict of Interest: No conflict of interest is declared by the author.

    Ill Mil Mill Mill Mill Mil Mill Mill Mil Mill Mill Mil Mill Mill Mil Mill Mill Mill Mil Mill Mill Mil Mill Mill Mil Mill 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 ^

    For citation: Poliakova I. Yu. A variable neighborhood descent heuristic for a multi-item lot-sizing problem with remanufacturing, Actual Problems of Economics and Law, 2020 року, Vol. 14, No. 1, pp. 174-185 (in Engl.). DOI: http: //dx.doi. org / 10.21202 / 1993-047X.14.2020.1.1.174-185.

    III! III! Mill Mill Mill III! Mill Mill III! Mill Mill III! Mill Mill III! Mill Mill Mill III! Mill Mill III! Mill Mill III! Mill Mill Mill III! Mill Mill III! Mill Mill III! Mill Mill III! Mill lllll Mill III! Mill Mill IN

    Introduction

    The problem solving in lot-sizing is applicable at the intersection of economics and manufacturing, especially in closed-loop logistics.

    It refers to the development of exact and heuristic methods for production planning and scheduling problems. Part Period Balancing (PPB), Wagner-Whitin algorithm and Economic order quantity (EOQ) techniques are among the exact methods.

    "Lot-for-lot techniques" orders that are required for production may not always be feasible. If setup costs are high, the costs may be high as well. Economic order quantity (EOQ) expects a known constant demand and Material requirements planning (MRP) systems often deal with unknown and variable demand. Part Period Balancing (PPB) looks at future orders to determine the most economic lot size. The Wagner-Whitin algorithm is a complex dynamic programming technique that assumes a finite time horizon [1, pp. 310-323].

    Use of PPB, Wagner-Whitin or EOQ techniques gives reasonable results only when setup costs are significant and demand is reasonably smooth. That is why exact methods can not be widely implemented in practice. The main goal in the fitting process is to obtain a model which makes good predictions for new inputs. The main purpose of this research is to show the heuristic method of solving lot-sizing problem with some extensions.

    However, a trend for not optimal, but heuristic approaches gains popularity. In this paper we will draw attention to heuristic approaches. To answer why heuristic approaches are becoming more popular among the researchers, firstly, we need to define the term "heuristic". A heuristic technique, often called just "heuristics", is a kind of approach to problem solving that is suitable for achieving the goal in a limited time, but not guaranteed to be optimal. In other words, the time costs spent on finding the optimal solution are bigger than the effect of finding and applying this optimal solution. That is why it is worth looking for "local", not "global", optimal solutions and using heuristic approach (see above).

    There are not many papers revealing the problem of multi-product dynamic lot-sizing with remanufacturing activities (MDLSRP). Li et al., For example, developed a multi-product lot-sizing problem, proposed some math-ematic algorithms and then proposed heuristic genetic algorithm to solve the problem [2, pp. 101-115]. Another group of scientists led by Sahling proposed a new model formulation for the MDLSRP and fundamentally different approach - a column-generation solution with the combination of a truncated branch-and-bound method [3, pp. 55-75]. Figueira et al. applied a hybrid approach to the specific case in the industry of pulp and paper. This industry is one of the most significant and relevant where it is worth to apply different solutions with reverse logistics [4, pp. 1804-1818].

    ........................................................................... ISSN 1993-047Х (Print) / ISSN 2410-0390 (Online) ...........................................................................

    This research refers to Variable Neighborhood Descent (VND) solution. The approach is based on a systematic change of the neighborhood structures in order to find the best solution. Sifaleras and Konstantaras provide their VND heuristic approach and present benchmark set with the largest instances in the literature [5, pp. 385-392].

    In this paper, it is proposed the literature review on Lot-Sizing Problem with Remanufacturing, model formulation, basic idea of ​​neighborhood descent and numerical example for the two products in three periods with applied neighborhood descent heuristic techniques.

    Literature review on Lot-Sizing in Closed-Loop with remanufacturing

    The first dynamic lot-size model was announced in inventory theory as a generalization of the economic order quantity model. This model takes into account that demand for the product varies over time. Wagner and Whitin introduced the model in тисяча дев'ятсот п'ятьдесят-вісім [6, pp. 89-96].

    The idea of ​​lot-sizing discussed in this paper is almost the same, but more applied to logistics. For example, the retailer orders items from the manufacturer to satisfy the customer's demand. The demand of the customers is fixed in each period and varies from one period to another.

    For dependent demand, total cost is discrete, and the nimum total cost over the planning period usually occurs at the point closest to the balance of the holding and setup costs. The goal of Lot-sizing problem is to satisfy the demand of items in each period while minimizing the combined costs.

    r

    The setup costs - are the costs incurred to get equipment ready to produce the next product lots. The setup costs incur whenever the production quantity is greater than zero.

    The holding costs incur per unit and are costs associated with storing items that remains unsold. These costs are one part of total inventory costs among ordering and shortage costs.

    Therefore, the manufacturer should decide how many items to produce in each period taking into account process costs and holding costs in order to minimize the sum of holding and setup costs. The holding and setup costs in lot-sizing problem act as constraints.

    Closed-Loop supply chain management is the design, control and operation of a system with the aim of maximizing value creation over the entire of a products life cycle.

    Closed-Loop logistics appears when it becomes cheaper for enterprise to remanufacture returned goods or parts of goods and to recover the value from different types and volumes of returns over time. The difference between direct logistics and closed-loop logistics is in the Fig. 1.

    As we have already mentioned, the objective of Lot-Sizing in Closed-Loop is to determine the number of manufactured and remanufactured items in different periods, in order to minimize the sum of set up costs of the manufacturing and remanufacturing processes and holding costs for returns and units that were produced in previous period but not sold. The returned items could be remanufactured and sold as new ones.

    Л

    I--------------------------------------

    Direct logistics / Пряма логістика

    Customer / Клієнт

    Producer /

    Виробник

    Closed-Loop logistics / Зворотній логістика

    Fig. 1. The difference between direct and closed-loop logistics

    Source: compiled by the author.

    Мал. 1. Відмінності між прямою і зворотною логістикою

    Джерело: складено автором.

    ISSN 1993-047Х (Print) / ISSN 2410-0390 (Online)

    Lot size is the number of units that the producer needs either manufacture or remanufacture. The size of the lots in each period is set on the basics of market demand and the number of returns that are both given, but non-stationary.

    The problem discussed in the paper consists of the multi-product dynamic lot-sizing model with manufacturing and remanufacturing setup costs. "The lot-sizing problem under separate set up costs, for manufacturing and remanufacturing, is suitable for situations where there are separate production lines" [5, pp. 385-392].

    Except the approach of A. Sifalerasand and I. Kon-stantaras there is a big number of other approaches related to Lot-Sizing problem in Closed-Loop, which are worth taking under consideration. We will briefly say further about some of them.

    Li, Chen, and Cai [2, 7] presented an uncapitalized lot-sizing problem for several products and applied a heuristic technic to determine a production plan.

    The authors described a model formulation for the lot-sizing problem with the "substitution": the remanu-factured product serves as new one. The model limits production capacity, ignores the interaction of products and setup times. [7, pp. 301-317].

    Sahling suggests combination of two approaches: a column-generation and a truncated branch-and-bound to solve the multi-product capacitated lot-sizing problem. The author presents a new model formulation with remanufacturing and returns. [3, pp. 55-75].

    Koken, Seok and Yoon address their research to the capacitated dynamic lot-sizing problem with returns and hybrid product. The problem is to identify how many of each product type to produce during each period for a hybrid system with manufacturing capacity constraints. The objective of their approach is "to maximize total profit of the production system that consists of new, remanufac-tured and hybrid products" [8, pp. 739-747].

    Model formulation for a Multi-Product Lot-Sizing Problem with Remanufacturing

    Before presenting the model formulation for a Multi-Product Lot-Sizing Problem with Remanufacturing, it is essential to introduce all the notations [6, pp. 301-317].

    In the following, a set of k products k = {1, 2, ... K} are considered. The production process is regarded in several time periods t = {1, 2, ..., T}.

    The demand for product k in time period t D (k, t) and the number of returned items of product k in period tR (k, t) are exogenous parameters and assumed to be time-varying. The demand of each product needs to be fulfilled for each product separately. The returned items can be completely remanufactured and sold as new. Also there are holding costs for the serviceable items of product k per unit time hM (k) and for the recoverable items of product k per unit time hR (k). The holding costs incur per unit, whereas the setup costs incur whenever the production quantity is greater than zero.

    In each time period it is necessary to decide to produce or not to produce the items. Thus zM (k, t) and zR (k, t) shows the binary decision variable denoting the initiation of the manufacturing and remanufacturing lot of product k in period t.

    The number of manufactured items xM (k, t) and number of remanufactured items xR (k, t) of product k in period t shows lot sizes.

    Setup costs of product k for manufacturing kM (k) and remanufacturing kR (k) shows the costs for setting of the the production lines. Also among the notations we need to set the production cost of product k per unit pM (k) and remanufacturing cost of product k per unit pR (k).

    YM (k, t) and yR (k, t) shows respectively the inventory level of serviceable and remanufacturable items of product k in period t. A sufficiently large number M is noted for its technical use. These notations give us opportunity to introduce mathematical formulation.

    Mathematical formulation is borrowed from Sifalerasand and Konstantaras [5]. As it has been already said, the objective of solving lot-sizing problem is to build operations of manufacturing and remanufacturing and to figure out how many units the manufacturer need to produce in order to minimize the total costs for all items and during all the periods.

    The mathematical model (1) represents minimizing Z-value as sum of the total costs for holding items, both manufactured and remanufactured (row 1), costs to produce and re-produce the items (row 2) and the set up costs (row 3).

    K T

    min Z = ^ ^ (hR (k) yR (k, t) + hM (k) xM (k, t)) +

    k = 1 t = 1

    KT

    + ^ ^ (PR (k) xR (k, t) + pM (k) xM (k, t)) +

    k = 1 t = 1

    ISSN 1993-047Х (Print) / ISSN 2410-0390 (Online) ...........................................................................

    K

    +

    ^ ^ (KR (k) zR (k, t) + kM (k) zM (k, t)).

    (1)

    k = 1 t = 1

    The set up costs depends on the decision to manufacture or not and to remanufacture or not, so zR (k, t) and zM (k, t) are binary decision variables denoting the initiation of a remanufacturing or manufacturing lot (2).

    f 1, if xR (k, t) > 0 zR (k, t) (^ otherwise

    Г1, if xM (k t) > 0 xM (k 't) [.otherwise

    (2)

    The constraints defined in Equations (3) are the inventory balance equations, which compute the inventory of returns and serviceables, respectively.

    yR (k, t) = yR (k, t - 1) + R (k t) - xR (k, t),

    yM (k, t) = yM (k, t - 1) + xR (k, t) + xM (k, t) - D (k, t),

    Vt = 1, 2, ..., T, Vk = 1, 2, ..., K. (3)

    Relations (4) are the adapted valid inequalities for the model. Relations (5) ensure that a fixed setup cost incurred when remanufacturing or manufacturing takes place, respectively.

    yM (k, t) > Y1 + p (D (k, s) - M (k, s) (zM (k, s) + zR (k, s))),

    is = t + 1

    Vk, Vt = 1, ..., T-1, Vp = 1, ... T-t, (4)

    yR (k, t) > Y j (R (k, s) - M (k, s) zR (k, s)),

    Vk, Vt = 1, ..., T-1, Vp = 1, ... T-t,

    xR (k, t) < MzR (k, t), xM (k, t) < MzM (k t),

    Vt = 1, 2, ..., T, Vk = 1, 2, ..., K. (5)

    Equations (6) ensure that the inventories are initially empty, set the indicator variables and prevent negative manufacturing, remanufacturing or inventory.

    yR (k, t), yM (k, t), xR (k, t), xM (k, t) > 0,

    zR (k, t), zM (k, t) V {0, 1}, (6)

    yR (k, 0) = yM (k, 0) = 0, Vt = 1, 2, ..., T, Vk = 1, 2, ..., K.

    Basic idea of ​​neighborhood descent

    Variable neighborhood search (VNS) is "a metaheuristic method for solving a set of combinatorial optimization

    and global optimization problems "[9]. According to this method, distant neighborhoods of the current solution are explored. The next step includes moves to a new one neighborhood until an improvement was made. If an improvement was not made, the current solution is regarded as an optimal solution. The VNS method applied repeatedly to get to local optimum [9]. The goal is to find the local minimums in a time-limited environment.

    The local search method is applied repeatedly to get from solutions in the neighborhood to local optimum. VNS was designed for approximating solutions of discrete and continuous optimization problems [9].

    On the line S, which could be found in the Fig. 2, mark 1 shows the starting point - our starting solution. After having the starting solution, according to VND, the neighborhood descents (marks 2 and 3) should be analyzed and the optimal solutions there should be found. Here we can see that the value in mark 3 is better than in mark 2, so we can move to another neighborhood descent, for example, we can move to mark 4. The value in mark 4 seems to be worse than in mark 3, so we need to return to mark 3 and to explore some neigbourhood descents between marks 1 and 3 and so on.

    The Variable neighborhood search is built up on the three following perceptions [10].

    Firstly, a local minimum (mark 3) with respect to all possible neighboring structures is recognized as a global, so that the global extremum (mark 5) from the Fig. 2 does not participate in the solution.

    Secondly, a local minimum with respect to one neighboring structure is not necessarily a local minimum for another neighborhood structure. It means that many different combinations of neighborhoods can be considered, and accordingly the final problem solutions will differ depending on which way we will move, what neighborhood combinations we will choose.

    Thirdly, for many problems, local minimum with respect to one or several neighborhoods are relatively close to each other. This means that it would not be a mistake to choose ones neighborhood structures and not others.

    Introduction of numerical example

    In this paper we consider the numerical example of solving Multy-product Lot-Sizing Problem with Remanufac-turing under separate manufacturing and remanufacturing set up costs. There are separate production lines, one for

    ISSN 1993-047Х (Print) / ISSN 2410-0390 (Online) ...........................................................................

    Fig. 2. Graphic example of neighborhood descent

    Source: compiled by the author.

    Мал. 2. Графічний приклад зниження околиць

    Джерело: складено автором.

    manufacturing and one for remanufacturing. In the following, the set of two products in three periods is considered.

    Holding costs per unit are 10. Set up costs are 300 for the both lines: for manufacturing and remanufactur-ing. The demand value in each period and the number of returns could be found in the Table 1.

    The objective is to determine the number of remanufac-tured and manufactured items in each period, in order to minimize the sum of set up costs of the manufacturing and remanufacturing processes and holding costs for returns and serviceables under various operational constraints.

    According to the input data for the numerical example, we start from o neighborhood descent for the first product:

    (1 0 0 ^ o = [0 1 1

    The first row in vector o shows decisions for the manufacturing production line and the second row shows decisions for the remanufacturing line. The columns are time-periods (from 1 to 3). Numbers 1 and 0 mean just if there is or not production in each period. Vector o does not show the number of units that enterprise should produce.

    Table i

    Input data for the numerical example Таблиця 1. Вхідні дані для чисельного прикладу

    Input data / Вхідні дані Product 1 / Продукт 1 Product 2 / Продукт 2

    Time period / Період часу 1 2 3 1 2 3

    Demand (t, d) / Попит (t, d) 10 20 30 30 20 40

    Returns (t, d) / Повернення ^, d) 5 20 10 20 10 30

    Source: compiled by the author.

    Джерело: складено автором.

    For starting solution of the numerical example, vector про means the decision to manufacture only in the first period and to remanufacture only in the second and third periods that is shown in the vector о. Starting solution for the Product i can be found in the Table 2. Total costs for the 3 periods amount to i 300.

    ISSN 1993-047Х (Print) / ISSN 2410-0390 (Online) ...........................................................................

    Table 2

    Starting solution for the Product 1 Таблиця 2. Початкове рішення для Продукту 1

    Table 3

    Starting solution for the Product 2 Таблиця 3. Початкове рішення для Продукту 2

    Period / Період 1 2 3 E

    Demand (9) / Попит (9) 10 20 30 60

    Return (9) / Повернення (9) 5 20 10 35

    Lots: Q manufacture (9) / Партія: виробництво Q (9) 25 0 0 25

    Lots: Q remanufacture (9) / Партія: повторне виробництво Q (9) 0 25 10 35

    In the stock (units) / На складі (штук) 20 20 0 40

    In the stock (rem units) / На складі (штук) 5 0 0 5

    Satisfy demand / Попит задоволений Yes / Так Yes / Так Yes / Так Yes / Так

    Total holding costs / Загальні витрати на зберігання 200 200 0 400

    Set up costs, man / Витрати на запуск виробництва 300 0 0 300

    Set up costs, rem / Витрати на запуск 2-ї лінії 0 300 300 600

    Total costs / Загальні витрати 500 500 300 1 300

    з =

    1 1 0 1 0 1

    Period / Період 1 2 3 E

    Demand (9) / Попит (9) 30 20 40 90

    Return (9) / Повернення (9) 20 10 30 60

    Lots: Q manufacture (9) / Партія: виробництво Q (9) 10 20 0 30

    Lots: Q remanufacture (t) / Партія: повторне виробництво Q (9) 20 0 40 60

    In the stock (units) / На складі (штук) 0 10 0 10

    In the stock (rem units) / На складі (штук) 0 10 0 10

    Satisfy demand / Попит задоволений Yes / Так Yes / Так Yes / Так Yes / Так

    Total holding costs / Загальні витрати на зберігання 0 100 0 100

    Set up costs, man / Витрати на запуск виробництва 300 300 0 600

    Set up costs, rem / Витрати на запуск 2-ї лінії 300 0 300 600

    Total costs / Загальні витрати 600 400 300 1 300

    Source: compiled by the author.

    Джерело: складено автором.

    The same we have for the Product 2. Vector з shows that the starting solution regarding the second product for enterprise is to manufacture and remanufacture in the first period, only to manufacture in the second and only to remanufacture in the third period:

    Starting solution for the Product 2 is shown in the Table 3. According to the outputs and chosen vector o, the enterprise should manufacture 10 and remanufacture 20 units in the first period. In the second period the number of manufactured items is 20. In the third period the enterprise should remanufacture 40 units of product 2. Total costs for the three periods are 1 300. The fact that the total costs for the both products coincided is accidental.

    The second step after getting results of starting solution is to explore the neighborhoods.

    Source: compiled by the author.

    Джерело: складено автором.

    Firstly, we start the VND procedure and repeat it. Then asking if we find a better solution, we get 1 or 0 (1 - yes, 0 - no). After finding a solution that is better than the previous one, we set this best solution as start for the second iteration.

    Thus, we continue doing iterations and finding the best neighbors with best solutions until the improvement indicates zero, i. e. a better solution is not found and this means the end of VND procedure. VND heuristics takes its advantage of evaluating several solutions at each iteration, comparing them and selecting the best among them before it goes through all other steps at an iteration.

    In terms of considered example, we limit each iteration up to three neighborhoods. Thus, three neighborhoods of starting solution are explored. These neighborhoods are obtained by shifting the set-up for manufacturing and remanufacturing from 1 to 0 and from 0 to 1, respectively. Neighborhoods, in the conditions of our example, are structures that differ from starting solution by only one parameter in one of the two production lines. The tree of neighborhood structures for the Product 1 can be found in the Fig. 3.

    ........................................................................... ISSN 1993-047Х (Print) / ISSN 2410-0390 (Online) ...........................................................................

    i100) V0 1 + 1 /

    Iteration № 1 / Ітерація № 1

    / 1 0 1w1 0 0 \ / 1 0 0 \ V0 1 1 / V0 1 0 / V0 0 1 /

    Iteration № 2 / Ітерація № 2

    / 1 0 1 \ / 1 0 1 \ / 1 0 1 \ V0 1 0 / V1 1 1 / V0 0 1 /

    found. In the Table 4 the lot sizes and inventories in the stock in each of three periods are given.

    Total costs in neighborhoods are 1 100, 1 250 and 1 150, respectively. It is obvious that the best from these thee solutions is 1 100.

    Thus, the best solution from the first iteration, which

    corresponds to vector

    Л 0 Л

    0 1 + 1 V У

    is selected as starting

    Fig. 3. Neighborhood descents for the Product 1

    Source: compiled by the author.

    Мал. 3. Зниження околиць для Продукту 1

    Джерело: складено автором.

    Regarding the first iteration, the optimal solution that minimizes total costs in each neighborhood has been

    solution for the second iteration, and is indicated by the arrows in the Fig. 4. The second poole of solutions is introduced in the Table 5.

    According to the new total costs, there is no one better solution than the starting one. Therefore, the VND solution for the Product 1 shows that the global minimum of total costs achieves while manufacturing 15 units in the first period, remanufacturing 15 units in the second and both manufacturing (10) and remanufacturing (20) in the third period . The tree of neighborhood structures within two iterations for the Product 2 can be found in the Fig. 4.

    Table 4

    Three solutions in neighborhood descents during first iteration for the Product 1 Таблиця 4. Три рішення при зниженні околиць в першій ітерації для Продукту 1

    t Neighborhood № 1 / Околиця № 1 Neighborhood № 2 / Околиця № 2 Neighborhood № 3 / Околиця № 3

    1 2 3 Е 1 2 3 Е 1 2 3 Е

    Demand (t) / Попит (t) 10 20 30 60 10 20 30 60 10 20 30 60

    Return (t) / Повернення (t) 5 20 10 35 5 20 10 35 5 20 10 35

    Lots: Q manufacture (t) / Партія: виробництво Q (t) 15 0 10 25 30 0 0 30 30 0 0 30

    Lots: Q remanufacture (t) / Партія: повторне виробництво Q (t) 0 15 20 35 0 25 0 25 0 0 30 30

    In the stock (units) / На складі (штук) 10 10 0 20 25 30 10 65 25 25 5 55

    In the stock (rem units) / На складі (штук) 5 10 0 15 5 25 10 40 5 25 5 35

    Satisfy demand / Попит задоволений Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так

    Total holding costs / Загальні витрати на зберігання 100 100 0 200 250 300 100 650 250 250 50 550

    Set up costs, man / Витрати на запуск виробництва 300 0 0 300 300 0 0 300 300 0 0 300

    Set up costs, rem / Витрати на запуск повторного виробництва 0 300 300 600 0 300 0 300 0 0 300 300

    Total costs / Загальні витрати 400 400 300 1 100 550 600 100 1 250 550 250 350 1 150

    Source: compiled by the author. Джерело: складено автором.

    Дискусії IIТТ1ГТ Актуальні проблеми економіки та права. 2020. Т. 14, № 1

    Discussions Actual Problems of Economics and Law, 2020 року, vol. 14, No. 1

    ........................................................................... ISSN 1993-047Х (Print) / ISSN 2410-0390 (Online) ...........................................................................

    Table 5

    Three solutions in neighborhoods during second iteration for the Product 1 Таблиця 5. Три рішення при зниженні околиць в другій ітерації для Продукту 1

    t Neighborhood № 1 / Околиця № 1 Neighborhood № 2 / Околиця № 2 Neighborhood № 3 / Околиця № 3

    1 2 3 E 1 2 3 E 1 2 3 E

    Demand (9) / Попит (9) 1G 2G 3G 6G 1G 2G 3G 60 1G 2G 3G 6G

    Return (9) / Повернення (9) 5 2G 1G 35 5 2G 1G 35 5 2G 1G 35

    Lots: Q manufacture (9) / Партія: виробництво Q (9) S G 3G 35 S G 2G 25 3G G S 35

    Lots: Q remanufacture (9) / Партія: повторне виробництво Q (9) S 2G G 25 S 20 1G 35 G G S 5

    In the stock (units) / На складі (штук) G G 1G 1G G G G G 25 25 1G 6G

    In the stock (rem units) / На складі (штук) G G 1G 1G G G G G 5 25 5 Пробіг: 35

    Satisfy demand / Попит задоволений Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так

    Total holding costs / Загальні витрати на зберігання G G 1GG 1GG G G G G 25G 25G 1GG 6GG

    Set up costs, man / Витрати на запуск виробництва 3GG G 3GG 600 3GG G 3GG 6GG 3GG G 3GG 6GG

    Set up costs, rem / Витрати на запуск 2-ї лінії 3GG 3GG G 600 3GG 3GG 3GG 9GG G G 3GG 3GG

    TOTAL COSTS / Загальні витрати 600 3GG 4GG 1 3GG 600 3GG 600 1 5GG 55G 25G 7GG 1 5GG

    Source: compiled by the author. Джерело: складено автором.

    Iteration № i / Ітерація № i

    Iteration № 2 / Ітерація № 2

    vno /

    Vi Про i /

    vi Ю // 1 0 0w0 i О / \ Про Про 0 / \ 1 0 1 / Vi Про О /

    / 1 0 0 // 1 0 0 // 1 0 1 / U 0 1 / V1 1 1 / V1 0 1 /

    Fig. 4. Neighborhood descents for the Product 2

    Source: compiled by the author.

    Мал. 4. Зниження околиць для Продукту 2

    Джерело: складено автором.

    During the second iteration the better solution in the second neighborhood was found. The total costs in this solution amount to 1 200 (Table 6). Taking the solution of

    neighborhood

    Г1 0 0л V1 0 1У

    as a new starting point we move

    to the second iteration of VND heuristics.

    The Table 7 indicates that we should finish our VND method and get back to starting solution of the second iteration because of absence of better solution comparing

    with starting one. The global minimum accounts for the following neighborhood

    Л 0 0 ^

    1 0 1 V У

    , where total costs are 1 200.

    The strategy implies manufacturing and remanufacturing in the first period, 30 and 20, respectively, no production in the second period and then remanufacturing 40 units in the third period.

    ISSN 1993-047Х (Print) / ISSN 2410-0390 (Online)

    The results of the research

    In this research, the multy-product lot-sizing problem with returns has been studied. And to solve this problem, the VND heuristic method has been applied. In the first part of the work the basic ideas of neighborhood descent and closed-loop were revealed.

    VND heuristic method explores small neighborhoods until a local optimum is encountered. VND is not a trajectory following method (as Simulated Annealing or Tabu Search) and does not specify forbidden moves. While the basic VND heuristic method is clearly useful for approximate solution of many combinatorial and global optimization problems, it remains difficult or long to solve very large instances. Often, the size of problems considered is limited in practice by the tools available to solve them more than by the needs of potential users of these tools. Therefore, improvements appear to be highly desirable. Moreover, when heuristics

    are applied to large instances, the strengths and weaknesses become clearly apparent. Three improvements of the basic VNS for solving large instances are now considered.

    Then we introduced the literature review on Lot-Sizing Problem with Remanufacturing and explored different views on this problem in the scientific society. We presented the model formulation and model assumption for the further introducing of numerical example. The example was given for the two products in three periods with applied neighborhood descent heuristic techniques. The example provides some mathematic calculations, computed in Microsoft Excel.

    Using the variable neighborhood descents for solving multi-product dynamic lot-sizing problem with remanu-facturing activities showed the solutions for producing two products. Minimum total costs for both products amount to 2 300. Both obtained best solutions were in the pool of neighborhoods of the first iteration.

    Table 6

    Three solutions in neighborhood descents during first iteration for the Product 2 Таблиця 6. Три рішення при зниженні околиць в першій ітерації для Продукту 2

    t Neighborhood № 1 / Околиця № 1 Neighborhood № 2 / Околиця № 2 Neighborhood № 3 / Околиця № 3

    1 2 3 Е 1 2 3 Е 1 2 3 Е

    Demand (t) / Попит (t) 30 20 40 90 30 20 40 90 30 20 40 90

    Return (t) / Повернення (t) 20 10 30 60 20 10 30 60 20 10 30 60

    Lots: Q manufacture (t) / Партія: проізводствоQ (t) 30 20 0 50 30 0 0 30 30 60 0 90

    Lots: Q remanufacture (t) / Партія: повторне виробництво Q (t) 0 0 60 60 20 0 40 60 20 0 0 20

    In the stock (units) / На складі (штук) 20 30 20 70 20 10 0 30 20 50 40 110

    In the stock (rem units) / На складі (штук) 20 30 20 70 20 10 0 30 20 50 30 100

    Satisfy demand / Попит задоволений Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так

    Total holding costs / Загальні витрати на зберігання 200 300 200 700 200 100 0 300 200 500 400 1100

    Set up costs, man / Витрати на запуск виробництва 300 300 0 600 300 0 0 300 300 300 0 600

    Set up costs, rem / Витрати на запуск 2-ї лінії 0 0 300 300 300 0 300 600 300 0 0 300

    Total costs / Загальні витрати 500 600 500 1 600 800 100 300 1 200 800 800 400 2 000

    Source: compiled by the author. Джерело: складено автором.

    Дискусії IIТТ1ГТ Актуальні проблеми економіки та права. 2020. Т. 14, № 1

    Discussions Actual Problems of Economics and Law, 2020 року, vol. 14, No. 1

    ........................................................................... ISSN 1993-047Х (Print) / ISSN 2410-0390 (Online) ...........................................................................

    Table 7

    Three solutions in neighborhoods during second iteration for the Product 2 Таблиця 7. Три рішення при зниженні околиць в другій ітерації для Продукту 2

    t Neighborhood № 1 / Околиця № 1 Neighborhood № 2 / Околиця № 2 Neighborhood № 3 / Околиця № 3

    1 2 3 E 1 2 3 E 1 2 3 E

    Demand (t) / Попит (t) 30 20 40 90 30 20 40 90 30 20 40 90

    Return (t) / Повернення (t) 20 10 30 60 20 10 30 60 20 10 30 60

    Lots: Q manufacture (t) / Партія: виробництво Q (t) 50 0 0 50 30 0 0 30 30 0 10 40

    Lots: Q remanufacture (t) / Партія: повторне виробництво Q (t) 0 0 40 40 20 10 30 60 20 0 30 50

    In the stock (units) / На складі (штук) 40 30 20 90 20 10 0 30 20 10 10 40

    In the stock (rem units) / На складі (штук) 20 30 20 70 20 10 0 30 20 10 0 30

    Satisfy demand / Попит задоволений Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так Yes / Так

    Total holding costs / Загальні витрати на зберігання 400 300 200 900 200 100 0 300 200 100 100 400

    Set up costs, man / Витрати на запуск виробництва 300 0 0 300 300 0 0 300 300 0 300 600

    Set up costs, rem / Витрати на запуск 2-ї лінії 0 0 300 300 300 300 300 900 300 0 300 600

    Total costs / Загальні витрати 700 300 500 1 500 800 400 300 1 500 800 100 700 1 600

    Source: compiled by the author. Джерело: складено автором.

    Conclusion

    The method has a wide usage in industrial field, especially in heavy industry and in pulp and paper industry. Proper formulation of the problem and correct method application would help to optimize manufacturing process in a short time, saving rather large funds for setting ups and inventory storing. Many companies are very interested in this kind of process optimisations and need to be connected with the scientific society to solve lot-sizing problems and grow up their business.

    Regarding further research directions, it would be interesting to expand the planning horizon from three periods that seems to be unrealistic in practice to 52360 periods. The second thing that could be improved in the model is increasing of the considered products number. Also it would be interesting to consider in the algorithm the possibility of changing input parameters. For example, expenses for starting a production line or the cost of a unit storing can differ from one period to another.

    INN INN INN INN NN INN INN NN INN INN INN NN INN INN NN INN INN NN INN INN INN NN INN INN NN INN NN

    References / Список літератури

    1. Perez K., Yossiri M., Raf A., Reinaldo J., Eli M., Tosoc A. An exact optimization approach for an integrated process configuration, lot-sizing, and scheduling problem, Computers & Operations Research, 2019, March, No. 103, pp. 310-323.

    2. Li Y., Chen J., Cai X. Uncapacitated production planning with multiple product types, returned product remanufacturing, and demand substitution, OR Spectrum, 2006, No. 28, pp. 101-125.

    3. Sahling. A column-generation approach for a short-term production planning problem in closed-loop supply chains, Business Research, 2013, No. 6, pp. 55-75.

    ........................................................................... ISSN 1993-047Х (Print) / ISSN 2410-0390 (Online) ...........................................................................

    4. Figueira G., Santos M. O., Almada-Lobo B. A hybrid VNS approach for the short-term production planning and scheduling: A case study in the pulp and paper industry, Computers & Operations Research, 2013, No. 40, pp. 1804-1818.

    5. Sifaleras A., Konstantaras I. Variable neighborhood descent heuristic for solving reverse logistics multi-item dynamic lot-sizing problems, Computers & Operations Research 2017, No. 78, pp. 385-392.

    6. Wagner H., Whitin T. Dynamic Version ofthe Economic Lot Size Model, Management Science, 1958, Vol. 5, No. 1, pp. 89-96.

    7. Li Y., Chen J., Cai X. Heuristic genetic algorithm for capacitated production planning problems with batch processing and remanufacturing, International Journal of Production Economics, 2007, No. 105, pp. 301-317.

    8. Koken, Seok, Yoon. A simulated annealing algorithm with neighbourhood list for capacitated dynamic lot-sizing problem with returns and hybrid products, International Journal of Computer Integrated Manufacturing, 2018, Vol. 31, No. 8, pp. 739-747.

    9. Mladenovic N. A variable neighborhood algorithm - a new metaheuristic for combinatorial optimization. Abstracts of Papers Presented at Optimization Days, Montreal, 1995.

    10. Brandimarte P. Multi-item capacitated lot-sizing with demand uncertainty, International Journal of Production Research, 2006, Vol. 44, No. 15, pp. 2997-3022.

    11. Macedo P., Douglas A., Santos А. Hybrid manufacturing and remanufacturing lot-sizing problem with stochastic demand, return, and setup costs, International Journal of Advanced Manufacturing Technology, 2015-го, Vol. 82, No. 5.

    12. Alfares H., Turnadi R. Lot sizing and supplier selection with multiple items, multiple periods, quantity discounts, and backordering, Computers & Industrial Engineering, 2018, February, pp. 59-71.

    13. Shekarabi S., Gharaei A., Karimi M. Modelling and optimal lot-sizing of integrated multi-level multi-wholesaler supply chains under the shortage and limited warehouse space: generalised outer approximation, International Journal of Systems Science: Operations & Logistics, 2019, Vol. 6, Is. 3, pp. 237-257. DOI: https://doi.org/10.1080/23302674.2018.1435835

    14. Zhou S., Zhou Y., Zuo X., Xiao Y., Cheng Y. Modeling and solving the constrained multi-items lot-sizing problem with time-varying setup cost, Chaos, Solitons & Fractals, 2018, November, pp. 202-207. DOI: https://doi.org/10.1016/j.chaos.2018.09.012

    15. Guner Goren, H., Tunali, S. Fix-and-optimize heuristics for capacitated lot sizing with setup carryover and backordering, Journal of Enterprise Information Management, Vol. 31, No. 6, 2018, pp. 879-890.

    Дата надходження / Received 10.06.2019 Дата прийняття до друку / Accepted 10.01.2020 Дата онлайн-розміщення / Available online 25.03.2020

    © Полякова І. Ю, 2020 © Poliakova, I. Yu., 2020

    Бікеєв, І. І., Кабанов, П. А.

    Антикорупційне просвіта: питання теорії і практики / І. І. Бікеєв, П. А. Кабанов. У 3 т. Т. 3. - Казань: Изд-во «Знання» Казанського інноваційного університету, 2019. - 240 с. - (Серія: Протидія корупції).

    У книзі розглянуто широке коло питань, пов'язаних з антикорупційним просвітою як інструментом протидії корупції. Викладено особливості правового регулювання цього інструменту на федеральному, регіональному і муніципальному рівнях, а також особливості оцінки якості його організації і здійснення в органах публічної влади та організаціях.

    Робота призначена для осіб, що реалізують державну політику протидії корупції, науковців, викладачів, учнів та всіх, хто цікавиться проблемами корупції.


    Ключові слова: ОКРЕСТНОСТНИЙ УЗВІЗ / ПРОБЛЕМА ВИЗНАЧЕННЯ РОЗМІРУ ПАРТІЇ / ПЕРЕРОБКА / багатопродуктової ВИРОБНИЦТВО / ЕВРИСТИЧНИЙ ПІДХІД / ЗАМКНУТЕ ЛОГІСТИЧНИЙ ЦИКЛ / ЗВОРОТНІЙ ЛОГІСТИКА / NEIGHBORHOOD DESCENT / LOT-SIZING PROBLEM / REMANUFACTURING / MULTI-ITEM LOT-SIZING / HEURISTIC APPROACH / CLOSED-LOOP / REVERSE LOGISTICS

    Завантажити оригінал статті:

    Завантажити