2-Approximation and Hybrid Genetic Algorithm for Long Chain Design Problem in Process Flexibility - Intelligent Computing for Sustainable Energy and Environment - page 230

2-Approximation and Hybrid Genetic Algorithm
for Long Chain Design Problem in Process
Flexibility
Yuli Zhang, Shiji Song, and Cheng Wu
Dept. of Automation, TNList, Tsinghua University, Beijing 100084, P.R. China
[e-mail],{shijis,wuc}@mail.tsinghua.edu.cn
Abstract. Long chain flexibility strategy is an effective way to match
the supply with the uncertain demand in manufacturing system. However
there are few studies on the long chain design problem with nonhomo-
geneous link costs. This paper first presents a mixed 0-1 LP model and
proves that it belongs to NP-complete. Then an approximation algorithm
is proposed which includes three steps: 1) solve a relaxed LP; 2) generate
a minimum spanning tree; 3) find the optimal local match. Under the
quadrangle inequality assumption, we show that it is a 2-approximation
algorithm. At last, based on another equivalent reformulation, we embed
the 2-approximation algorithm and a 2-opt exchange local search into a
hybrid genetic algorithm. By comparison with CPLEX solver, numerical
experiments validate the effectiveness of the proposed algorithms.
Keywords: Long chain design, process flexibility, 2-approximation.
1 Introduction
In the increasingly competitive marketplace, there is an trend of shorter prod-
uct upgrade cycle, more customized demand and higher demand variability. Be-
sides the traditional operations strategies, such as inventory control and surplus
capacity buffers, flexibility strategies have been proven as effective ways to de-
crease the mismatch between the supply and demand. It has been applied in
many industry fields, such as automobile industry [1], textile industry [2] and
semiconductor industry [3].
Tang and Tomlin [4] analyzed the potential supply chain risks and provided
convincing arguments for deploying flexibility to mitigate supply chain risks.
Process flexibility via flexible manufacturing process has been widely adopted to
match the supply with the uncertain demand by shifting production quantities
across internal plants or machines. Process flexibility is defined as the ability to
build different types of products in the same plant or production facility at the
same time [5]. Facing increasing deamnd uncertainty, process flexibility allows
the company to reallocate its production capacity, workload and other flexible
resources.
Although the total flexibility design [6], i.e., each plant build all products,
provides the optimal performance of match, it suffers unacceptable expensive