Location sensitive multi-task oriented service composition for cyber physical systems

As a core technology to enable service-based cyber physical systems (CPSs), CPS service composition has received a lot of attention from researchers. However, existing studies on it mostly aim to solve single task oriented CPS service composition problem, and the multi-tasking requirements of CPSs are not considered. In fact, there are quite a few situations where multiple tasks need to be completed as soon as possible, such as smart emergency response, and smart manufacturing. In addition, locations have much influence on the execution time of CPS services because before CPS services begin to work for tasks, the required physical entities must move or be transported to the predefined locations. In this paper we investigate the CPS service composition problem in which these two characteristics are both considered. To address it, we not only need to select appropriate CPS services for each task, but also need to arrange the invocation sequence for each selected CPS service. The final goal is to find a service selection and invocation scheme that can optimize the makespan as much as possible. A heuristic approach based on an improved quantum genetic algorithm is designed to handle it. Experimental results show that the proposed method can find the superior schemes. Compared with the schemes given by other methods, our schemes can achieve lower makespan under various situations, such as different number of CPS services and tasks, and different types of spatial distribution.