دانلود مقاله ISI انگلیسی شماره 25731
عنوان فارسی مقاله

یک روش برنامه ریزی پویا با فهرست هایی برای مسئله اشتراک گذاری پشت واره

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
25731 2011 5 صفحه PDF سفارش دهید محاسبه نشده
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
A dynamic programming method with lists for the knapsack sharing problem
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Computers & Industrial Engineering, Volume 61, Issue 2, September 2011, Pages 274–278

کلمات کلیدی
مسئله به اشتراک گذاری پشت واره - بهینه سازی ترکیبیاتی - حداقل و حداکثر برنامه ریزی - برنامه ریزی پویا -
پیش نمایش مقاله
پیش نمایش مقاله  یک روش برنامه ریزی پویا با فهرست هایی برای مسئله اشتراک گذاری پشت واره

چکیده انگلیسی

In this paper, we propose a method to solve exactly the knapsack sharing problem (KSP) by using dynamic programming. The original problem (KSP) is decomposed into a set of knapsack problems. Our method is tested on correlated and uncorrelated instances from the literature. Computational results show that our method is able to find an optimal solution of large instances within reasonable computing time and low memory occupancy.

مقدمه انگلیسی

The knapsack sharing problem (KSP) is a max–min mathematical programming problem with a knapsack constraint (see Brown, 1979, Brown, 1991 and Brown, 1994). The KSP is NP-complete. The KSP occurs when resources have to be shared or distributed fairly to several entities, e.g. distribution of scarce resources like ammunition or gasoline among different military units (see Brown, 1979) or budget shared between districts of a city (see Yamada et al., 1997 and Yamada et al., 1998). The KSP is composed of n items divided into m different classes. Each class NiNi has a cardinality n i with ∑i∈Mni=n∑i∈Mni=n and M={1,2,…,m}M={1,2,…,m}. Each item j∈Nij∈Ni is associated with: • a profit pij, • a weight wij, • a decision variable xij ∈ {0, 1}. We wish to determine a subset of items to be included in the knapsack of capacity C , so that the minimum profit associated with the different class is maximised. The KSP can be formulated as follows: equation(1.1) View the MathML source(KSP)maxmini∈M∑j∈Nipij·xij=z(KSP),s.t.∑i∈M∑j∈Niwij·xij⩽C,xij∈{0,1}fori∈Mandj∈Ni, Turn MathJax on where z (KSP ) denotes the optimal value of the problem (KSP ) and for i∈Mi∈M and j∈Ni,wij,pijj∈Ni,wij,pij and C are positive integers. Furthermore, we assume that ∑i∈M∑j∈Niwij>C∑i∈M∑j∈Niwij>C and maxi∈M,j∈Ni{wij}⩽Cmaxi∈M,j∈Ni{wij}⩽C. A common way to solve the KSP consists of its decomposition into knapsack problems (see for examples Hifi and Sadfi, 2002 and Yamada et al., 1998). Indeed, for a class i∈Mi∈M, we define the following problem: equation(1.2) View the MathML source(KPi(Ci))max∑j∈Nipij·xij=z(KPi(Ci)),s.t.∑j∈Niwij·xij⩽Ci,xij∈{0,1}j∈Ni. Turn MathJax on The objective is then to find View the MathML source(C1∗,C2∗,…,Cm∗) such that View the MathML source∑i∈MCi∗⩽C, Turn MathJax on and View the MathML sourcemini∈M{zKPiCi∗}=z(KSP), Turn MathJax on where for a problem P,z(P)P,z(P) represents its optimal value. An upper bound and a lower bound of z(P)z(P) will be denoted, respectively, by View the MathML sourcez¯(P) and View the MathML sourcez̲(P), respectively. Hifi et al. have proposed to solve the knapsack problems (KPi(Ci))i∈M(KPi(Ci))i∈M via a dense dynamic programming algorithm in Hifi and Sadfi, 2002 and Hifi et al., 2005. Their method starts with Ci=0,i∈MCi=0,i∈M, and increases regularly the capacities until ∑i∈MCi>C∑i∈MCi>C. In this article, we propose an algorithm for solving the KSP. Our algorithm is based on a dynamic programming procedure with dominance technique to solve the knapsack problems (KPi(Ci))i∈M(KPi(Ci))i∈M. Our algorithm starts by solving the problems (KPi(Ci))i∈M(KPi(Ci))i∈M with View the MathML sourceCi⩾Ci∗,i∈M and ∑i∈MCi⩾C∑i∈MCi⩾C. At each step, we try to decrease the values of (Ci)i∈M(Ci)i∈M, towards View the MathML source(Ci∗)i∈M. The use of lists permits one to reduce the memory occupancy; the expected benefit being the solution of large instances. Without loss of generality, we consider in the sequel that the items in a class i∈Mi∈M are sorted according to decreasing ratios View the MathML sourcepijwij,j∈Ni. In Section 2, we present the dynamic programming algorithm used to solve the problems (KPi)i∈M(KPi)i∈M. Section 3 deals with the algorithm we propose for the KSP. Computational results are displayed and analyzed in Section 4. Some conclusions and perspectives are presented in Section 5.

نتیجه گیری انگلیسی

In this paper, we have proposed a method to solve the KSP with a dynamic programming list algorithm. The original problem (KSP) is decomposed into a set of knapsack problems. The initial value of the knapsack capacity is obtained via an overestimation. This value is updated and decreased throughout the solution process. Computational results show that best results were obtained when the number of classes is relatively small. They show also that DPKSP is able to solve large instances within reasonable computing time and small memory occupancy. Moreover, our method use less memory than previous methods in the literature. We think that very good results can be obtained with our method for instances with bigger capacities and a great number of classes (in the problems considered, capacities are generated so that they are equal to the half sum of all item weights, as a consequence, the bigger the weights, the bigger the capacity is). In future work, it would also be interesting to consider a multi method that combines the advantages of our approach with the one of Hifi et al. In order to decrease the processing time, parallel implementation of DPKSP could be considered. Indeed, the computations on knapsack sub-problems are independent and could be done in parallel.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.