期刊名称：International Journal of Computer and Information Technology
印刷版ISSN：2279-0764
出版年度：2016
卷号：5
期号：4
页码：1-10
出版社：International Journal of Computer and Information Technology
摘要：Dynamic webservice composition (DWSC) is a
promising technology in supporting Virtual organizations to
autogenerate composite services that maximize the utility of
Internet commerce service consumers over a range of the
consumer’s QoS constraints. However, over the last decade
DWSC remains a non polynomial deterministic problem, making
its industrial application limited. Local planning approaches to
the problem guarantee solutions in polynomial time but lack
capabilities to solve for inter workflow task constraints that could
be critical to a service consumer. The inability of local planning
algorithms to capture global constraints means that the
techniques are likely to yield low quality solutions. Among the
existing global planning approaches, mixed integer programming
(MIP) has been found to be the best tradeoff in guaranteeing
global quality of solutions albeit with the possibility of solutions
being generated in exponential time. This makes MIP techniques
limited for small scale problems. In [23] we proposed SLUM, a
technique that combines the relative advantages of local planning
and MIP to achieve solutions that are more efficient but 5% less
quality than MIP, but 5% more quality than the local planning
approach [25]. However, it remains unknown whether or not
SLUM could be more efficient than the standard MIP (S-MIP) in
the absence of service elimination in layer 1 of the optimization
process, leading to the question, can SLUM exhibit superlinear
speedup relative to S-MIP? Using formal mathematical analysis,
this study established that SLUM can be more efficient up to a
maximum of 2k-1
times than S-MIP, where k is the number of
sequential workflow tasks. Further, using experimentation with
differential calculus and empirical relative complexity
coefficients for analysis , the study established that it would take
3 years to achieve a superlinear speedup of 2k-1
times when k=2
and a speedup of 1.5 times in 28 hours. The conclusion is that
even in the absence of webservice elimination, virtual enterprise
brokers can still benefit from the relative efficiency gains of
SLUM up to a practical limit of 50% over S.
关键词：Web Service Composition; Virtual Organizations;
Decomposition; Superlinear; Optimization; Mixed Integer
Programming; Service Layered Utility Maximization; Empirical
Complexity
