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

setup cost. However, it has been shown that well designed limited flexibility,
i.e., each plant builds only a few products, may yield most of the benefit of the
total flexibility design. Furthermore, Jordan and Graves [5], through empirical
analysis, have shown that the long chain configuration which chains products and
plants together to the greatest extent possible, generates the greatest benefit.
In the case of symmetrical manufacturing system with n products and n
plants, the long chain strategy requires that each plant produces exactly two
products, demand for each product can be satisfied from exactly two plants and
all plants and products are connected, directly or indirectly, by product assign-
ment links. Motivated by the seminal work of [5], there are numerous empirical
studies and analytical results on process flexibility. Graves and Tomlin [7] iden-
tified effective guidelines for process flexibility strategies in multi-stage supply
chain, Gurumurthi and Benjaafar [8] extended this work to queuing systems,
and Hopp et al. [9] to flexible workforce scheduling. Based on the set-theoretic
methodology, Bassamboo et al. [10] analyzed newsvendor networks with multiple
products and parallel resources, and characterized the optimal flexibility config-
uration for both symmetric and asymmetric systems. Aksin and Karaesmen [11]
characterized the decreasing marginal value of flexibility and capacity in general
process flexibility structures. Chou et al. [12] analyzed the worst-case perfor-
mance of the flexible structure design problem using the graph expander struc-
ture, designed guidelines for general non-symmetrical systems and developed a
simple and easy-to-implement heuristic to design flexible process structures.
To evaluate the eciency of the long chain strategy in the symmetrical system,
Chou et al [13] utilized the random walk and developed a system of equations to
compute its performance. They showed that long chain structure performs well
for a variety of realistic demand distributions, even when the system size is large.
For manufacturing system with general demand and supply, they presented con-
straint sampling method to identify a sparse process flexibility structure within
optimality of the total flexibility structure. David and Wei [14] provided the
first non-asymptotic theory that explains the effectiveness of the long chain.
Based on the supermodularity property of long chains, they showed that for any
size system, not only large size, the long chain always maximizes expected sales
among all 2-flexibility strategies.
Although long chain strategy has been proven as an effective guideline in
process flexibility design, there are few studies on how to implement this strategy.
In the literatures, especially under the symmetrical system assumption, each
product is arbitrarily assigned to two different plants. However in reality the
link costs between plants and products, which may contain the setup cost for one
plant producing certain product and transportation cost to deliver the product
to certain market, are usually quite different.
In this paper, we attempt to provide models and solutions on the implemen-
tation of the long chain strategy. First, under the bipartite graph representation
of process flexibility, we present a mixed 0-1 linear programming model for the
long chain design problem, and show that it belong to NP-complete. Second,
although it can be transformed to a symmetrical Traveling Salesman Problem