Web service location-allocation using discrete NSGA-II with matrix based genetic operations and a repair mechanism

Web Service Location-Allocation Problem (WSLAP) is an important and challenging NP-hard combinatorial optimization problem where multiple objectives affecting the quality of service (QoS) are to be optimized simultaneously. Most of the existing research articles mainly focus on selecting web service locations that minimize two QoS: total cost and total response time. However, another QoS factor throughput also needs attention when selecting sites for allocating web services. Therefore, we have constructed a new WSLAP model that minimizes the total cost and the total negative quality factor. This negative quality factor considers throughput along with latency to strengthen the QoS of the located web services. Further, three NSGA-II variants, NSGA-II.V1, NSGA-II.V2, and NSGA-II.V3, with a novel matrix-based chromosome representation, are developed to deal with the proposed bi-objective WSLAP model. These algorithms involve matrix-based genetic operations for better exploration and a repair mechanism for tackling infeasibility. The proposed model and algorithms are validated on 24 test instances, out of which 14 are existing, and 10 are newly created with increased web services, user centres and service locations. The experimental results claim that the proposed WSLAP model succeeded in improving the throughput with a comparatively lower total cost. Further, the proposed algorithms outperformed the compared algorithms in terms of hypervolume, inverted generational distance and computational time on 89% of instances. © 2023, The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature.