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

Next for problem parameter setting with problem size n = 100 , 150 , 200 and
p =1 , 2 , + ∞

, we randomly generate 10 instances and report the average relative
error and average CPU runtime in Table 2. Table 2 shows that for all the test
instances, 2-APP can find solution with relative error less than 5% and HGA
further decreases the relative error to less than 3% on average in reasonable
time.

Tabl e 2. Performance of 2-APP and HGA for different instances

2-APP HGA

Parameters RE (%) T ( s ) RE (%) T ( s )

p =1 ,n = 100 5.41 0.03 2.95 2.19

p =1 ,n = 150 2.43 0.06 1.59 4.81

p =1 ,n = 200 4.51 0.14 2.72 8.69

p =2 ,n = 100 4.54 0.02 2.55 2.19

p =2 ,n = 150 4.14 0.05 2.44 4.87

p =2 ,n = 200 4.09 0.17 2.40 8.68

p = ∞,n = 100 3.63 0.02 2.18 2.19

p = ∞,n = 150 3.84 0.08 2.51 4.82

p = ∞,n = 200 4.12 0.14 2.30 8.70

6 Conclusions and Future Works

This papers studies how to implement the long chain flexibility strategy when
there are nonhomogeneous link costs between different plants and products. We
first present a mixed 0-1 LP model and show that it belongs to NP-complete
by transforming the NP-complete Hamilton circuit problem to the long chain
design problem. However, the equivalent TSP doesn't holds the triangle equality
property, thus we next present a new approximation algorithm 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. Next a HGA is design to further improve
the solution quality. At last, by numerical experiments we show that CPLEX
solver fails to find good solution for given time while for all the test instances
on average the 2-approximation algorithm and the HGA can obtain high quality
solutions in very limited time.
For further research, other flexibility strategies, such as flexible supply con-
tracts and postponement flexible pricing are interesting research topics on how
to mitigate the supply chain risk by enhancing it flexibility.

Acknowledgment. This work was supported by Natural Science Foundation
of China (No.61273233) and Research Fund for the Doctoral Program of Higher
Education (No. 20090002 110035).