| 失效链接处理 |
|
A Binary Particle Swarm Optimization Algorithm For Uncapacitated PDF 下载
本站整理下载：
提取码：fkdh
相关截图：
主要内容：
1. Introduction
The lot-sizing problem attracted attention because of its impact on the
inventory levels and, hence the inventory holding cost and the setup/ordering
cost. It is basically concerned with finding order quantities minimizing the
total cost of lot sizing decisions. Lot quantity might be either an amount of
purchase or production depending on the problem domain on hand in order to
∗
Management Department, Fatih University, 34500 Buyukcekmece, Istanbul, Turkey.
Email: ftasgetiren@fatih.edu.tr
∗∗ Department of Industrial Engineering and Management, Yuan Ze University
No 135 Yuan-Tung Road, Chung-Li, Taoyuan County, Taiwan 320, R.O.C.
2 M. Fatih Taşgetiren & Yun-Chia Liang
meet the net requirements of the customer demand. In lot sizing problems,
time horizon is defined as given time buckets in which quantity decisions are
generally given at the beginning of each time bucket. Lot sizing decisions are
made in such a way that all customer requirements are met at the end of the
time horizon.
In general, lot quantities are determined as the total requirement for a
number of periods in which the total cost is minimized. It balances the
tradeoff between the ordering and the holding costs. In other words, it
depends on the requirement in the current period plus the requirements for the
future periods. So the order quantity is determined by grouping the net
requirements for a number of periods ahead. There exist different techniques
to determine the lot quantities. Most popular one is the lot-for-lot where
whatever needed is ordered. One other strategy is to order a fixed order
quantity, which is common in industry, at each period regardless of any
variation in the demand requirements. Another technique is to cover the net
requirements for a number of future periods, called fixed periods. In addition,
it is also possible to combine the different strategies together.
Several factors should be considered when lot-sizing decisions are
given. These factors are ordering cost, holding cost, shortage cost, capacity
constraints, minimum order quantity, maximum order quantity, quantity
discounts and so on. Combination of these factors results in different models
to analyze and different solution procedures are used depending on the model
employed. The model and its solution procedure can be made complicated by
considering these factors in the models, which can be classified as capacitated
or uncapacitated, single-level or multi-level, single-item or multi-item models.
In this paper, we consider the uncapacitated, single-item, no
shortages-allowed and single-level lot sizing model and solve it by a binary
particle swarm optimization (PSO) algorithm. The rest of the paper is
organized as follows: The next section formulates the problem, followed by a
literature review. Then the binary PSO algorithm applied to lot sizing problem
is given along with a traditional genetic algorithm, followed by some
experimental results. Finally, conclusion and future work is presented.
A Binary Particle Swarm Optimization Algorithm
for Lot Sizing Problem
3
2. Problem Formulation
The mathematical formulation of the lot sizing model considered in this paper
is given as follows:
( )
: (1) 1
min
subject to
ni i cI i Ax ⎟⎠⎞ ⎜⎝⎛ ∑= + 0 (2) 0 i I = ∀ (3) 1 i i R iI i Qi x iI + − = ∀ − 0 (4) i i I ≥ ∀ 0 (5) i i Q ≥ ∀
{ } 0,1 (6) i i x ∈ ∀
Where
n =number of periods
A =ordering/setup cost per period
c =holding cost per unit per period
i R =net requirement for period i
i Q =Order quantity for period i
iI =projected inventory balance for period i
i x =1 if an order is placed in period i, =0 otherwise. i x
In the objective function (1), a penalty A is charged for each order
placed along with a penalty c for each unit carried in inventory over the next
period. Equation (2) guaranties that no initial inventory is available. Equation
(3) is the inventory balance equation in which the order quantity covers all
the requirements until the next order. Equation (4) satisfies the condition that
no shortages are allowed. And finally, equation (5) shows the decision
variable to be either 1 (place an order) or 0 (do not place an order). It
should be noted that initial inventory is zero, , such that by
equation (3) if . Because of the minimization nature of the problem, Qi i x 0 0I = 1 1x = 0 1R >
4 M. Fatih Taşgetiren & Yun-Chia Liang
the ending inventory at each period is minimized to avoid the penalty charge
c, particularly = 0 . nI
3. Literature Review
Different solution procedures are available to determine the lot quantities. The
most popular one is the economic order quantity, EOQ (Mennell, 1961).
Theoretically, EOQ minimizes the ordering and holding cost, but assumes that
the requirements are constant or stationary from period to period. For the case
of dynamic requirements in which the requirements are significantly variable
over the periods, Silver and Meal (1973) presented a heuristic, so called
Silver-Meal heuristic. The heuristic tries to minimize the ordering and holding
costs per unit of time. Other heuristics are common in most production text
books such as Least Unit Cost, LUC and Part Period Balancing, PPB. See
Sipper and Bulfin (1997) for details. Wagner and Whitin, WW (1958)
provided a dynamic programming to solve the problem optimally.
4. Binary PSO Algorithm For Lot Sizing Problem
Particle Swarm Optimization (PSO) is one of the evolutionary optimization
methods inspired by nature which include evolutionary strategy (ES),
evolutionary programming (EP), genetic algorithm (GA), and genetic
programming (GP). PSO is distinctly different from other evolutionary-type
methods in that it does not use the filtering operation (such as crossover
and/or mutation) and the members of the entire population are maintained
through the search procedure. In PSO algorithm, each member is called
“particle”, and each particle flies around in the multi-dimensional search
space with a velocity, which is constantly updated by the particle’s own
experience and the experience of the particle’s neighbors. Since PSO was
first introduced by Kennedy and Eberhart (1995, 2001), it has been
successfully applied to optimize various continuous nonlinear functions.
Although the applications of PSO on combinatorial optimization problems are
still limited, PSO has its merit in the simple concept and economic
computational cost.
The main idea behind the development of PSO is the social sharing of
information among individuals of a population. In PSO algorithms, search is
A Binary Particle Swarm Optimization Algorithm
for Lot Sizing Problem
5
conducted by using a population of particles, corresponding to individuals as
in the case of evolutionary algorithms. Unlike GA, there is no operator of
natural evolution which is used to generate new solutions for future
generation. Instead, PSO is based on the exchange of information between
individuals, so called particles, of the population, so called swarm. Each
particle adjusts its own position towards its previous experience and towards
the best previous position obtained in the swarm. Memorizing its best own
position establishes the particle’s experience implying a local search along
with global search emerging from the neighboring experience or the
experience of the whole swarm. Two variants of the PSO algorithm were
developed, one with a global neighborhood, and other one with a local
neighborhood. According to the global neighborhood, each particle moves
towards its best previous position and towards the best particle in the whole
swarm, called gbest model. On the other hand, according to the local variant,
called lbest model, each particle moves towards its best previous position and
towards the best particle in its restricted neighborhood (Kennedy, 2001).
Kennedy and Eberhart (1997) also developed the discrete binary version of
the PSO. PSO has been successfully applied to a wide range of applications
such as power and voltage control (Abido, 2002), mass-spring system
(Brandstatter & Baumgartner, 2002), and task assignment (Salman et al.,
2003). The comprehensive survey of the PSO algorithms and applications can
be found in Kennedy et al. (2001).
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
