Collaborative task scheduling with new task arrival in cloud manufacturing using improved multi-population biogeography-based optimization

Abstract

Task scheduling is important in cloud manufacturing because of customers’ increasingly individualized demands. However, when various changes occur, a previous optimal schedule may become non-optimal or even infeasible owing to the uncertainty of the real manufacturing environment where dynamic task arrival over time is a vital source. In this paper, we propose a novel collaborative task scheduling (CTS) model dealing with new task arrival which considers multi-supply chain collaboration. We present an improved multi-population biogeography-based optimization (IMPBBO) algorithm that uses a matrix-based solution representation and integrates the multi-population strategy, local search for the best solution, and the collaboration mechanism, for determining the optimal schedule. A series of experiments are conducted for verifying the effectiveness of the IMPBBO algorithm for solving the CTS model by comparing it with five other algorithms. The experimental results concerning average best values obtained by the IMPBBO algorithm are better than that obtained by comparison algorithms for 41 out of 45 cases, showing its superior performance. Wilcoxon-test has been employed to strengthen the fact that IMPBBO algorithm performs better than five comparison algorithms.

Keywords

Cloud manufacturing task scheduling multi-supply chain collaboration new task arrival biogeography-based optimization

1 Introduction

Cloud manufacturing (CMfg), based on advanced information technologies such as cloud computing and Internet of Things, is a new service-oriented manufacturing paradigm aiming to provide users with safe, on-demand, reliable, and high-quality manufacturing services [1]. In CMfg, distributed manufacturing resources and manufacturing capabilities are virtualized and encapsulated into cloud services that can be managed centrally [2]. Centralized management of services conveys that CMfg can handle multiple tasks simultaneously [3].

A CMfg service platform tends to receive multiple tasks concurrently, most of which are multi-granular and complex, and can be decomposed into several subtasks that need to be fulfilled by the cooperation among various services with different functionalities. Because of customers’ increasingly various individualized demands, manufacturing tasks tend to be heterogeneous. Thus, task scheduling is a critical issue in CMfg. It aims to cope with a set of tasks simultaneously and allocate appropriate services with different functionalities for achieving the corresponding tasks that optimize the service status and execution plans of manufacturing tasks while satisfying user requirements. Although research in the field of scheduling in CMfg is available [4], most existing methods only consider the horizontal cooperation between manufacturers who offer different service functionalities; thus, each subtask is fulfilled by one service, and a whole task is achieved by a single-supply chain. By contrast, multi-supply chain collaboration includes the horizontal and vertical cooperation between services with different and same functionalities, respectively; thus, higher-level manufacturing cooperation is achieved and a more flexible and efficient execution plan is obtained. Thus, we propose a novel collaborative task scheduling (CTS) model through multi-supply chain collaboration, which considers both horizontal and vertical cooperation among service suppliers from supply chains.

Most existing studies assume that the CMfg scheduling environment is static, in which no changes occur. However, owing to the uncertainty of the real manufacturing environment, a previous optimal schedule may become infeasible, and the production process may be affected when various changes occur, such as quality of service (QoS) change, service disruption, and new task arrival. In particular, dynamic task arrival over time is an important source that leads to dynamics of the CMfg environment [4]. In this study, we consider new task arrival in the task scheduling problem, which is unpredictable and cannot be controlled beforehand by the CMfg platform operator. When enterprises submit new task requirements to the CMfg platform, some services are occupied because of the unfulfilled allocated tasks from the previous schedules. Because the task scheduling problem in CMfg involves multi-suppliers and multi-demanders, penalty clauses exist when breach of contract occurs, and the original execution plan cannot be disrupted completely [5]. Therefore, using suitable rescheduling strategies for allocating services for the new tasks is essential.

Task scheduling problem is a typical NP-hard problem that cannot be efficiently solved by exact algorithms when the problem scale increases. Thus, it is necessary to try more efficient algorithms for solving the task scheduling problem. In the last decade, various meta-heuristic algorithms have been developed in the literature and applied to many real-world applications as an alternative to traditional exact methods [6, 7]. Meta-heuristic algorithms can be defined as an iterative generation process trying to find near-optimal solutions, by exploring and exploiting the search space, and learning strategies using intelligently combining different concepts [8]. Compared with traditional methods, meta-heuristic algorithms can increase the probability of jumping out of local optimum, and move towards good solutions more quickly with less computational effort, therefore can deal with large complicated problems more effectively and efficiently [9]. In recent years, many meta-heuristic algorithms have been proposed for solving the optimization problem [10]. Biogeography-based optimization (BBO) algorithm is a population-based algorithm introduced by Simon [11] for solving the engineering optimization problem. It has garnered attention from many scholars because it is found that BBO algorithm was superior than many global optimization methods in various fields. For example, research [12, 13] have showed that BBO algorithm can encode the solution with simpler representation schemes, and has a better performance than genetic algorithm (GA), and particle swarm optimization (PSO). Although BBO algorithm has a good performance, it is still challenging to solve the proposed CTS problem effectively and efficiently when the problem scale increases. Thus, some points still need enhancement, including relatively weak exploration ability at the early stage of the evolutionary process and the tendency to be trapped into local optima [14]. Therefore, we propose an improved multi-population BBO (IMPBBO) algorithm that uses a matrix-based solution representation containing multi-supply chain collaboration information, and integrates the multi-population strategy, local search for the best solution, and collaboration mechanism among sub-populations into the basic BBO algorithm for solving the problem effectively. The multi-population strategy is employed to maintain the diversity of population and accelerate the convergence speed. The local search is designed to make solutions jump out of local optimum effectively. Moreover, the collaboration mechanism is used to accelerate the convergence speed. Thus, the proposed IMPBBO can be improved further in optimization accuracy and convergence speed.

The remainder of this paper is organized as follows. Section 2 reviews the related work. Section 3 presents the CTS model through multi-supply chain collaboration, which deals well with the new task arrival. Section 4 introduces the basic BBO algorithm and presents the proposed IMPBBO algorithm. Section 5 discusses the results of the experiment. Section 6 describes the conclusions and future work.

2 Related work

Task scheduling as a critical issue in CMfg has attracted much attention from many scholars. This section gives a brief review about task scheduling problem and meta-heuristic algorithms for the optimization problems.

2.1 Task scheduling problems

In a CMfg system, service selection and composition is an important process that matches and composes qualified services with the corresponding tasks, and is typically used for composite task scheduling process, which has drawn much attention in the last decade [15 –18]. However, most of the existing research on service selection and composition is limited to the single-task scenario, which does not consider the real-world manufacturing environment with multiple tasks requested simultaneously. In addition, most of them assume that, once a service is occupied, it is unavailable until the entire production process is completed. Thus, a gap exists between the theory and industrial application. By contrast, scheduling in CMfg determines when and where tasks should be arranged and performed, and mostly considers the multi-task scenario and service status [4]. Moreover, the multi-task scenario can be further distinguished into two kinds: scenarios of homogeneous tasks and scenarios of heterogeneous tasks.

In the conventional manufacturing systems, scheduling, such as workshop scheduling and supply chain scheduling, has been investigated intensively [19 –21]. In recent years, many researches have studied the task scheduling problem in CMfg from different perspectives. Table 1 summarizes the related typical research work about task scheduling in CMfg. At the early stage, the task considered tends to be simple, which need not to be decomposed into several subtasks and requires only one service for its fulfillment. Laili et al. [22] studied the collaborative design task scheduling problem with the task precedence constraint. Lin and Chong [23] addressed the project scheduling problem with the same task type for optimal allocation of computing resources. However, in the real world, most tasks submitted to the CMfg platform are complicated, which need to be decomposed into several subtasks and completed by the cooperation among various services. Moreover, distinguished from the scheduling problems in conventional manufacturing systems, the task scheduling problem in CMfg has the following key features: large-scale and diverse tasks, large-scale and uncertain services, and massive candidate services for one task [24]. Considering these features, researches have begun to study further on the task scheduling in CMfg. Jian and Wang [25] scheduled a batch task with the same characteristic based on the order of the production process for minimizing the total production time and cost. Li et al. [26] proposed a task scheduling model with multiple types based on the subtask level. Jiang et al. [27] proposed a task scheduling and resource allocation model for minimizing the makespan and cost in cloud-based disassembly. Liu et al. [3] presented a multi-task scheduling model to schedule tasks for achieving better performance of a CMfg system, which integrates service quantity, service efficiency, task workload, and enterprise capacity. Ghomi et al. [28] applied the queuing theory for optimizing CMfg service selection and scheduling load balancing. Li et al. [29] proposed a two-level scheduling model to schedule the heterogeneous tasks to optimize the benefits. Laili et al. [30] investigated the multi-phase integrated scheduling of hybrid tasks in CMfg, containing order priority, assignment, supplier and production process selection, and production line scheduling.

Table 1
Typical research work about task scheduling in cloud manufacturing

Authors Characteristics of tasks Objectives Environment Methods

Laili et al. [22] Multiple simple tasks Time Static GA

Lin and Chong [23] Multiple simple tasks Time Static GA

Cao et al. [31] Single complicated task Time Quality, cost, and service Static Ant colony optimization

Cheng et al. [32] Single complicated task Time, and cost Static GA

Jian and Wang [25] Multiple complicated homogeneous tasks Time, and cost Static PSO

Li et al. [26] Multiple complicated homogeneous tasks Loading balance, cost, and time Static GA

Jiang et al. [27] Multiple complicated heterogeneous tasks Makespan, and cost Static Multi-objective genetic algorithm

Liu et al. [3] Multiple complicated heterogeneous tasks Time, cost, and quality Static Workload-based heuristic

Yuan et al. [33] Multiple complicated heterogeneous tasks Workload, and cost Static PSO

Ghomi et al. [28] Multiple simple heterogeneous tasks Time, cost, and load balancing Static GA

Li et al. [29] Multiple complicated heterogeneous tasks Makespan Static Ant colony optimization

Laili et al. [30] Multiple complicated heterogeneous tasks Idle time, cost, time, transportation, and delay time Static Multi-objective evolutionary algorithms

Zhou et al. [24] Multiple complicated heterogeneous tasks Time Dynamic Event-triggered method

Wang et al. [37] Multiple complicated heterogeneous tasks Time, and cost Dynamic Shuffled frog leading algorithm

Authors	Characteristics of tasks	Objectives	Environment	Methods
Laili et al. [22]	Multiple simple tasks	Time	Static	GA
Lin and Chong [23]	Multiple simple tasks	Time	Static	GA
Cao et al. [31]	Single complicated task	Time Quality, cost, and service	Static	Ant colony optimization
Cheng et al. [32]	Single complicated task	Time, and cost	Static	GA
Jian and Wang [25]	Multiple complicated homogeneous tasks	Time, and cost	Static	PSO
Li et al. [26]	Multiple complicated homogeneous tasks	Loading balance, cost, and time	Static	GA
Jiang et al. [27]	Multiple complicated heterogeneous tasks	Makespan, and cost	Static	Multi-objective genetic algorithm
Liu et al. [3]	Multiple complicated heterogeneous tasks	Time, cost, and quality	Static	Workload-based heuristic
Yuan et al. [33]	Multiple complicated heterogeneous tasks	Workload, and cost	Static	PSO
Ghomi et al. [28]	Multiple simple heterogeneous tasks	Time, cost, and load balancing	Static	GA
Li et al. [29]	Multiple complicated heterogeneous tasks	Makespan	Static	Ant colony optimization
Laili et al. [30]	Multiple complicated heterogeneous tasks	Idle time, cost, time, transportation, and delay time	Static	Multi-objective evolutionary algorithms
Zhou et al. [24]	Multiple complicated heterogeneous tasks	Time	Dynamic	Event-triggered method
Wang et al. [37]	Multiple complicated heterogeneous tasks	Time, and cost	Dynamic	Shuffled frog leading algorithm

Furthermore, conventional scheduling models assume that the mapping relationship between each subtask and its corresponding candidate service is one-to-one. In other words, each subtask can be fulfilled by one service; therefore, the whole task can only be achieved by a single-supply chain, which cannot make best use of the features of massive candidate services for each subtask in CMfg, thus lacking flexibility and efficiency. In this study, we focused on the independent, heterogeneous tasks, and elaborated the multi-supply chain collaboration that includes both horizontal and vertical cooperation between services with different and same functionalities, thereby enhancing cooperation between suppliers and improving the ability of tackling uncertainties in the CMfg system.

A practical manufacturing environment has various uncertainties. Scheduling in conventional manufacturing systems considering dynamic factors has attracted considerable attention [34 –36]. However, research on task scheduling in CMfg, especially considering the dynamic nature of CMfg, is in its infancy. Zhou et al. [24] proposed an event-triggered dynamic task scheduling method for solving task scheduling problem with randomly arriving tasks. Considering the occurrence of plan change in the cloud service execution process, Wang et al. [37] considered the delivery date ahead of the schedule as an example and built a game theory model for encouraging suppliers to participate in rescheduling while minimizing the total participation reward. In this study, we propose a CTS model that deals with new task arrival.

2.2 Meta-heuristic algorithms

Task scheduling and its related problems have attracted much attention, which can be solved by exact algorithms [38]. In CMfg environment, each subtask tends to have massive candidate services. Therefore, with the increasing number of tasks and subtasks, it becomes inefficient to apply exact algorithms because of large search spaces. Many meta-heuristic algorithms have been developed to determine near-to-optimal solutions within limited time. Zhou et al. [39] improved the GA for generating optimal diverse task scheduling solutions. Tao et al. [40] proposed a PSO for obtaining optimal resource service composition plans that considered time, cost, and reliability. Bouzary and Chen [41] combined the developed grey wolf optimizer algorithm with the evolutionary operators of GA to determine service composition and optimal selection solutions with high quality. Wang et al. [18] designed a many-objective memetic algorithm to solve the proposed correlation-aware service composition model. In our recent work, Zhang et al. [42] extended the flower pollination algorithm to solve a collaborative service group-based model considering fuzzy QoS values. Zhang et al. [43] proposed an extended non-dominated sorting genetic algorithm-II for solving the utility-aware multi-task scheduling model, which considers the utilities of both customers and manufacturers.

As a population-based evolutionary algorithm, the BBO algorithm showed a superior performance with a strong search capability and fast convergence speed for solving various combinatorial optimization problems [44, 45]. Kim et al. [46] used BBO algorithm to solve job scheduling problem in cloud computing and the experimental results showed that the performance of BBO algorithm is better than that of PSO, GA, and simulated annealing when the job scheduling problem size is large. Recently, many studies on the BBO algorithms have been conducted effectively in the field of manufacturing. Paslar et al. [47] developed a BBO algorithm by using different types of mutation operators for solving the flexible manufacturing system scheduling problem. Considering the two-stage programming structures, Yang et al. [48] designed an improved BBO algorithm combined with the approximation approach for solving the supply chain network problem. Rifai et al. [49] proposed a non-dominated sorting BBO by designing three emigration–immigration approaches based on sinusoidal, quadratic, and trapezoidal models to substitute the standard linear model, for solving the scheduling problem in a flexible manufacturing system.

Although various extensions of BBO algorithm have been proposed to address optimization problems in the field of manufacturing, few studies have explored the application of the BBO algorithm for solving the task scheduling problem in CMfg considered in this study. In addition, the basic BBO algorithm cannot deal with the proposed CTS model which considers multi-supply chain collaboration directly. Therefore, we propose an IMPBBO algorithm that uses a matrix-based solution representation containing multi-supply chain collaboration information and integrates a multi-population strategy, local search for the best solution, and the collaboration mechanism among sub-populations, which can solve the CTS model more effectively.

3 Mathematical model of the CTS problem with new task arrival

In a CMfg system, diverse tasks are submitted to the cloud platform simultaneously, which tend to be complex, and can be decomposed into several subtasks. Many services in the cloud service resource pool are provided by different suppliers to fulfill a subtask. The CTS problem is aimed to allocate an appropriate service satisfying functional and non-functional requirements for each subtask of all tasks with different types and to determine the sequence of subtasks on corresponding service to realize a multi-objective optimization. In this study, we considered the multi-supply chain collaboration and new task arrival in the CTS problem. Figure 1 shows a schematic diagram of the CTS model in CMfg.

Fig. 1

Schematic diagram of the CTS model in CMfg.

3.1 CTS model

To describe the proposed model explicitly, we introduced and defined the following notations: M

number of enterprises providing services in the CMfg platform

E_m

the enterprise m, m = 1, ... , M

number of tasks submitted to the CMfg platform simultaneously

T_i

the task i, i = 1, ... , I

J_i

number of subtasks composing the task i

ST_ij

the jth subtask of T_i, j = 1, ... , J_i

N_m

number of manufacturing services provided by E_m

MS_mn

the nth manufacturing service offered by E_m, n = 1, ... , N_m

index of supply chains, l = 1, ... , L_i, where L_i is the number of supply chains that achieve T_i

{FT}_{ij}^{mn}

fixed setup time of MS_mn performing ST_ij

{ET}_{ij}^{mn}

executing time of MS_mn performing ST_ij individually

{FC}_{ij}^{mn}

fixed setup cost of MS_mn performing ST_ij

{EC}_{ij}^{mn}

executing cost of MS_mn performing ST_ij individually

{UR}_{ij}^{mn}

reliability of MS_mn performing ST_ij individually per unit time

ɛ_{i}^{l}

fulfillment proportion of the lth supply chain for achieving T_i

TT_mv

transportation time from E_m to E_v

TC_mv

transportation cost from E_m to E_v

S_{ij}^{l}

start time of ST_ij of the lth supply chain

M_{ij}^{l}

completion time of ST_ij of the lth supply chain

completion time of the schedule

total cost of the schedule

total reliability of the schedule

α_{i}^{mvl}

the number of transportation occurrence between E_m and E_v on the lth supply chain of T_i

x_{ij}^{mnl}

binary variable; if ST_ij is executed by MS_mn on the lth supply chain, then $x_{ij}^{mnl}$ =1; otherwise, $x_{ij}^{mnl}$ =0

β_{ij}^{mnl}

binary variable; if $x_{ij}^{mnl}$ =0, then $β_{ij}^{mnl}$ =1; otherwise, $β_{ij}^{mnl}$ is equal to ${UR}_{ij}^{mn}$

QoS attributes can be used to evaluate services based on different non-functional service qualities. We considered three key QoS attributes: time, cost, and reliability. The comprehensive QoS value of a schedule is related to the specific subtask combination structure of tasks, including sequential, parallel, selective, and circular. We elaborated the sequential structure in this model, as the other three structures can be dealt with similarly.

(1) Completion time of the schedule CT $CT = max_{1 ⩽ i ⩽ I, 1 ⩽ l ⩽ L_{i}} {{CT}_{{iJ}_{i}}^{l}}$ (1)

CT is determined by the maximum time required for completing all tasks, including service time (setup and execution time) and transportation time. ${CT}_{{iJ}_{i}}^{l}$ refers to the end time of the last subtask ST_{iJ
_i} of task T_i on the lth supply chain.

(2) Total cost of the schedule C $C_{1} = \sum_{i = 1}^{I} \sum_{j = 1}^{J_{i}} \sum_{m = 1}^{M} \sum_{n = 1}^{N_{m}} \sum_{l = 1}^{L_{i}} ({FC}_{ij}^{mn} x_{ij}^{mnl} + {EC}_{ij}^{mn} x_{ij}^{mnl} ɛ_{i}^{l})$ (2) $C_{2} = \sum_{i = 1}^{I} \sum_{m = 1}^{M} \sum_{v = 1}^{M} \sum_{l = 1}^{L_{i}} {TC}_{mv} α_{i}^{mvl}$ (3) $α_{i}^{mvl} = \sum_{j = 1}^{J_{i} - 1} \sum_{n = 1}^{N_{m}} \sum_{s = 1}^{N_{v}} x_{ij}^{mnl} x_{i (j + 1)}^{vsl}, \forall i, m, v, l$ (4) $C = C_{1} + C_{2}$ (5)

Equation (2) is the total processing cost consisting of total setup and execution cost of used services for fulfilling all tasks on all supply chains, where the Boolean $x_{ij}^{mnl}$ is introduced to characterize whether ST_ij is executed by MS_mn on the lth supply chain. Equation (3) is the transportation cost, referring to the total occurred transportation cost between two adjacent enterprises E_m and E_v. Equation (4) denotes the number of transportation occurrence between two adjacent enterprises E_m and E_v on the lth supply chain of T_i. Moreover, the transportation cost will be zero if two consecutive subtasks under the same task on the same supply chain are performed within the same enterprise. C is the total cost of the schedule, including processing cost C₁ and transportation cost C₂.

(3) Total reliability of the schedule R ${FE}_{ij}^{mnl} = {FT}_{ij}^{mn} x_{ij}^{mnl} + {ET}_{ij}^{mn} x_{ij}^{mnl} ɛ_{i}^{l}$ (6)

$R = \prod_{i = 1}^{I} {\prod_{j = 1}^{J_{i}} \prod_{m = 1}^{M} \prod_{n = 1}^{N_{m}} \prod_{l = 1}^{L_{i}} (β_{ij}^{mnl})}^{{FE}_{ij}^{mnl}}$ (7)

In the previous work [3], R can be calculated by multiplying the reliability of all utilized manufacturing services. Considering that in the real world, reliability of manufacturing services is related to the service time. Thus, instead of multiplying the reliability of all utilized services, the setup and execution time of services are introduced in the reliability calculation. The Boolean $β_{ij}^{mnl}$ is equal to the reliability of MS_mn performing ST_ij individually per unit time when ST_ij is executed by MS_mn on the lth supply chain. Equation (6) denotes setup and execution time of MS_mn performing ST_ij on the lth supply chain. In addition, although reliability of enterprises providing transportation services is also important, to be more concise, only the reliability of manufacturing services is considered in this model. Total reliability of the schedule R can be computed by Equation (7).

The comprehensive value of QoS can be calculated by assigning appropriate weights to different QoS attributes to convert multiple objectives into the single objective. Because the values of CT, C, and R have different orders of magnitude, a normalization process should be carried out first. The normalization method of positive attributes (e.g., reliability) and negative attributes (e.g., completion time and cost) is shown in Equations (8) and (9), respectively [38]. $q_{n} = {\begin{matrix} \frac{q - q_{min}}{q_{max} - q_{min}} & if q_{max} \neq q_{min} \\ 1 & if q_{max} = q_{min} \end{matrix}$ (8)

$q_{n} = {\begin{matrix} \frac{q_{max} - q}{q_{max} - q_{min}} & if q_{max} \neq q_{min} \\ 1 & if q_{max} = q_{min} \end{matrix}$ (9)

where q_n is the normalized QoS attribute value, and q_max and q_min are the maximal and minimal QoS attribute values, respectively.

Thus, based on Equations (8) and (9), we formulated the objective of the CTS mathematical model for determining an optimal schedule using Equation (10). $\begin{matrix} max f & = w_{1} \frac{{CT}_{max} - CT}{{CT}_{max} - {CT}_{min}} + w_{2} \frac{C_{max} - C}{C_{max} - C_{min}} \\ + w_{3} \frac{R - R_{min}}{R_{max} - R_{min}} \end{matrix}$ (10) where f denotes the comprehensive QoS value of a schedule, CT_max, C_max, and R_max denote the maximal CT, C, and R, respectively, and CT_min, C_min, and R_min denote the minimal CT, C, and R of a schedule respectively. w₁, w₂, and w₃ that add up to 1 represent the respective importance of the three QoS attributes.

We subjected the objective to the following constraints: ${CT}_{ij}^{l} ⩾ S_{ij}^{l} + \sum_{m = 1}^{M} \sum_{n = 1}^{N_{m}} {FE}_{ij}^{mnl}, \forall i, j, l$ (11) $\begin{matrix} {CT}_{ij}^{l} - {CT}_{i (j - 1)}^{l} ⩾ \sum_{m = 1}^{M} \sum_{n = 1}^{N_{m}} {FE}_{ij}^{mnl} + \sum_{m = 1}^{M} \sum_{v = 1}^{M} \sum_{n = 1}^{N_{m}} \\ \sum_{s = 1}^{N_{v}} {TT}_{mv} x_{i (j - 1)}^{mnl} x_{ij}^{vsl}, 2 ⩽ j ⩽ J_{i}, \forall i, l \end{matrix}$ (12) $\sum_{m = 1}^{M} \sum_{n = 1}^{N_{m}} x_{ij}^{mnl} = 1, \forall i, j, l$ (13) $\sum_{l = 1}^{L_{i}} ɛ_{i}^{l} = 1, \forall i$ (14)

Constraint (11) ensures that when a subtask is executed by a service on one supply chain, it cannot be interrupted until it is finished. Constraint (12) is the precedence constraint between two successive subtasks under the same task on the same supply chain. Constraint (13) assures that each subtask can be processed by exactly one service on one supply chain. Constraint (14) ensures that the total fulfillment proportion of all supply chains for a task is equal to 1.

3.2 New task arrival

The practical manufacturing environment is typically confronted with unexpected incidents. In the CTS problem with new task arrival, an original schedule is determined by assuming that there is no unexpected disruption in the CMfg system. During task execution based on the original schedule, new tasks are submitted to the CMfg platform unpredictably. Thus, the rescheduling strategy should be triggered, and a new revised schedule should be constructed after disruptions. To explain the CTS problem with new task arrival and rescheduling strategies clearly, Fig. 2 provides an illustrative example. Figure 2(a) shows a Gantt chart of two tasks, nine services, and eight subtasks. 2.1.3 denotes that ST₂₃ is executed by MS₂₂ on the first supply chain. 2.2.3 denotes that ST₂₃ is executed by MS₃₄ on the second supply chain. The bars with the same color indicate that the marked subtasks decomposed from the same task are performed on the same supply chain.

Fig. 2

An example of CTS problem with new task arrival.

(1) Rescheduling strategy 1

With rescheduling strategy 1 (RS1), the original schedule is not influenced by the new tasks. The new tasks are scheduled on available services whose all assigned subtasks are finished. Thus, services may be available at different points of time. Figure 2(b) shows the revised Gantt chart using RS1 based on the example in Fig. 2(a). A new task arrives at time 120, and it can be executed after time 120 on services whose assigned subtasks are finished.

(2) Rescheduling strategy 2

With rescheduling strategy 2 (RS2), the original schedule is also not influenced by the new tasks. In the practical manufacturing environment, available time slots of services during execution process tend to exist. The subtasks of new tasks can be inserted into the available time slots of services while keeping the original schedule unchanged. This strategy can make the best use of the idle time of services. For example, in Fig. 2(a), there exist some available time slots which can be used for new subtask execution. It can be seen from Fig. 2(c) that the idle time of services after time 120 is used, and the first subtask of the new task performed on the first supply chain is inserted into the idle time of MS₂₄ while the first subtask of the new task performed on the second supply chain is inserted into the idle time of MS₁₂.

4 IMPBBO algorithm

In this section, we first provide a brief description of the basic BBO algorithm. Then, we present the proposed IMPBBO algorithm for the CTS problem with new task arrival in CMfg.

4.1 Description of the basic BBO algorithm

The BBO algorithm [11] is a population-based optimization algorithm inspired from the theory of island biogeography. Each solution is called a “habitat” with a habitat suitability index (HSI) used to evaluate the performance of the solution. The habitat comprises a set of features called suitability index variables (SIVs).

In the BBO algorithm, solutions evolve based on two key operators: migration and mutation. According to the equilibrium theory of island biogeography, migration may occur when the number of species is too large for habitats to maintain favorable geographical conditions. Similar to migration in biogeography, in the BBO algorithm, some features of good solutions with high HSI may immigrate to poor solutions with low HSI. Thus, HSI of poor solutions can be improved after accepting new features. The mutation operator is a probabilistic operator that modifies features of solutions randomly to improve the diversity of population.

4.2 IMPBBO algorithm for the CTS problem with new task arrival

Considering the characteristics of the basic BBO algorithm, we presented an IMPBBO algorithm that used a matrix-based habitat representation and introduced the multi-population strategy, a local search for the best solution, and adopted a collaboration mechanism among sub-populations. Figure 3 shows the framework of the IMPBBO algorithm.

Fig. 3

Framework of the IMPBBO algorithm.

4.2.1 Matrix-based habitat representation

Before implementing the proposed algorithm, a representation scheme should be designed to encode the solution of the CTS problem. Considering the characteristic of the CTS problem, a habitat needs contain information including the fulfilled services, number of supply chains for achieving each task, and corresponding proportion of the fulfillment. Thus, to enable the IMPBBO algorithm adaptive to the CTS model, a new matrix-based habitat representation is proposed, which describes the multi-supply chain collaboration mode reasonably. Each matrix consisted of I rows corresponding to the number of the total tasks. By considering the multi-supply chain collaboration, the first part of each row indicated the fulfillment proportions of the corresponding supply chains which are summed to 1. For the remaining L_i parts that equaled the number of supply chains for the corresponding task, the number of elements in one of L_i parts equaled the number of subtasks of the corresponding task, and each element displayed the service assigned to fulfill the corresponding subtask. Figure 4 illustrates an example of a matrix-based habitat representation. The matrix consists of two rows, and each row contains three parts, which denotes that there are two tasks to be scheduled, and each task is fulfilled by two supply chains. For example, T₁ is executed on two supply chains whose fulfillment proportions are 0.4 and 0.6, respectively. For the first row of the matrix, the first element in the second part indicates that MS₂₄ fulfills 40% of ST₁₁ on the first supply chain, while the second element in the third part indicates that MS₃₄ fulfills 60% of ST₁₂ on the second supply chain. This representation method is intuitive for understanding the specific solution.

Fig. 4

An example of matrix-based habitat representation.

4.2.2 Initialization

The IMPBBO algorithm starts with the generation of an initial population as it is population-based. The random approach is adopted to generate the feasible solutions which compose the initial population. In addition, considering the new task arrival, the solutions corresponding to the new task are generated randomly again while keeping the original solutions unchanged.

4.2.3 Multi-population strategy

The multi-population strategy divides the whole population into some sub-populations of the same size. The number of sub-populations is denoted with NSP. Each sub-population evolves independently to explore its corresponding part of the search space. As NSP increases, the diversity of the whole population can be enhanced, and the probability of trapping into the local optima can be decreased.

4.2.4 Migration operator

Migration is the process of species movement between different habitats. The migration operator depends on the immigration and emigration rate of each habitat, which are calculated using linear functions presented in Equations (15) and (16) [11]. $λ_{k} = I_{max} (1 - \frac{S_{k}}{NP})$ (15) $μ_{k} = E_{max} \frac{S_{k}}{NP}$ (16) where λ_k and μ _k are the immigration and emigration rate, respectively, I_max is the maximum immigration rate which occurs when there are no species in the habitat, E_max is the maximum emigration rate which occurs when there exist the largest number of species in the habitat that it can support, S_k is the habitat count, and NP is the maximum number of habitats.

It is obvious that when there exist no species in the habitat, the emigration rate will be zero, and the migration rate will increase when the number of species increases. Whenever the habitat contains the largest number of species, E_max occurs. The equilibrium number of species is the point where I_max and E_max are equal. After selecting the immigration habitat in one sub-population, the emigration habitat is probabilistically chosen according to the emigration rate in the same sub-population. By sharing features between these migration habitats of the same sub-population, low HSI habitats accept some new features from high HSI habitats, thus, improving the exploitation ability of the algorithm.

4.2.5 Mutation operator

By imitating sudden changes in nature, the mutation operator randomly changes the features of solutions. It modifies a habitat’s SIVs randomly based on the mutation probability of each habitat. The habitats with medium HSI are more probable to mutate than those with extremely high and low HSIs. The mutation rate of each habitat m_k can be calculated in Equation (17) [11]. $m_{k} = m_{max} (1 - \frac{P_{k}}{P_{max}})$ (17) where m_max is the maximum mutation probability determined by the user, P_k refers to the probability of a habitat involving k species, which is calculated in Equation (18) [11], and P_max is the maximum value of P_k. $\begin{matrix} P_{k} = \\ {\begin{matrix} - (λ_{k} + μ_{k}) P_{k} + μ_{k + 1} P_{k + 1} & S_{k} = 0 \\ - (λ_{k} + μ_{k}) P_{k} + λ_{k - 1} P_{k - 1} + μ_{k + 1} P_{k + 1} & 1 ⩽ S_{k} ⩽ NP - 1 \\ - (λ_{k} + μ_{k}) P_{k} + λ_{k - 1} P_{k - 1} & S_{k} = NP \end{matrix} \end{matrix}$ (18)

It can be seen that m_max determines the probability of habitat mutation. The probability of habitat mutation happening will increase with the increase of m_max. The diversity of the population and quality of solutions are improved through the mutation strategy. In addition, the solution with the highest HSI remains unchanged.

4.2.6 Local search

The best solution can be enhanced using a local search that searches its neighborhoods to further enhance the algorithm’s exploitation ability. We adopted two typical mutation operators: swap and inversion [50]. For the swap mutation, we randomly selected two positions of a solution. Then, we exchanged the corresponding SIV values assigned to them. Inversion mutation selects successive SIVs at random, and inverses their values.

4.2.7 Collaboration mechanism

The collaboration mechanism enhances communications among sub-populations and further improves solution quality by exchanging information of the search space among different sub-populations. Moreover, it prevents the early stagnation of the proposed algorithm and further improves the diversity of the whole population.

Typical topology structures used in collaboration mechanism include ring, grid, and complete net. In the proposed algorithm, we adopted the topology structure of complete net, assuming that each sub-population exchanged information with its neighbor sub-populations.

To avoid the redundant computing time and cost and to improve the search efficiency, we did not apply the collaboration among sub-populations unless a solution’s HSI was not improved during five successive generations. In addition, too much information exchange may disrupt the search process; thus, we determined the solutions selected for information exchange by using the roulette wheel strategy presented in Equation (19) [51], which are used to replace the worst habitats in other sub-populations. $P_{mk} = \frac{f_{k}}{\sum_{k = 1}^{NP} f_{k}}$ (19)

where P_mk denotes the selection probability of habitat k for information exchange, and f_k is the HSI value of habitat k.

4.2.8 Time complexity of IMPBBO algorithm

Suppose that D is the dimension of the CTS problem and C is the pre-defined number of applying local searches, the time complexity of each process in one iteration of the IMPBBO for solving CTS model is shown as follows: (1) calculation of immigration rate and emigration rate is O (NP×log NP), (2) migration operator is O (NP×D), (3) mutation operator is O (NP×D), (4) local search is O (NP×C). Therefore, by synthesizing the time complexity of each process, the overall complexity of the proposed IMPBBO algorithm is O (NP×(2D+C+log NP)). Moreover, the overall complexity of the basic BBO algorithm is O (NP×(2D+log NP)). It can be seen that the complexity of IMPBBO algorithm is slightly greater than that of the basic BBO algorithm, due to the local search.

4.2.9 Structure and process of the IMPBBO algorithm

The procedures of IMPBBO algorithm for solving CTS problems are presented in Algorithm 1.

Algorithm 1. IMPBBO algorithm for solving the CTS problems
1. NP←Population size
2. NSP←Sub-population number
3. I_max←Maximum immigration rate
4. E_max←Maximum emigration rate
5. m_max←Maximum mutation probability
6. Randomly generate an initial population.
7. While the termination criterion is not satisfied do
8. Evaluate the HSI value of each habitat.
9. for each sub-population do
10. Calculate immigration rate λ_k of each habitat k in sub-population.
11. Calculate emigration rate μ _k of each habitat k in sub-population.
12. for each habitat k in sub-population do
13. if rand (0, 1) < λ_kthen
14. Perform migration operator.
15. end if
16. end for
17. end for
18. for each sub-population do
19. Calculate mutation probability m_k of each habitat k in sub-population.
20. for each habitat k in sub-population do
21. Perform mutation operator based on the mutation probability m_k.
22. end for
23. end for
24. for each sub-population do
25. for each habitat k in sub-population do
26. Perform local search for habitat k.
27. end for
28. end for
29. if the collaboration criterion is satisfied then
30. Exchange information among sub-populations.
31. end if
32. end while
33. Return best habitat

5 Simulation experiment and comparison

We implemented the experiments by using Java on a personal computer with Intel Core (TM) i9-9900 processer at 3.10 GHz and 16 GB RAM operated on Windows 10.

5.1 Experimental setup

We used an illustrative case to examine the performance of the multi-supply chain collaboration on the CTS model. In addition, we conducted experiments for evaluating the performance of the presented IMPBBO algorithm and the performances of the two rescheduling strategies. For all datasets, setup time, setup cost, execution time, execution cost, and reliability of manufacturing services are randomly generated between the intervals [5, 10] hour, [5, 10] $, [30, 80] hour, [30, 80] $, and (0.9, 1) respectively, and transportation time and cost are randomly generated between the intervals [5, 10] hour and [5, 10] $ respectively. All experimental data used in this study have been uploaded to the Figshare database (https://doi.org/10.6084/m9.figshare.13726507.v1).

In addition, we set the control parameters of the proposed IMPBBO algorithm as follows based on the results of the trial of the experiments. The sub-population number NSP = 3, the maximum immigration rate I_max =1, the maximum emigration rate E_max =1, and the maximum mutation probability m_max = 0.1, which were consistent with literature [52]. Moreover, to test the performance of the proposed IMPBBO algorithm for solving the CTS problem, we compared the IMPBBO algorithm with the BBO algorithm, ICPSO [25] (an improved PSO), GA_N2 [23] (an improved GA), EGA_OS [19] (an improved GA), and HGWO [41] (an improved grey wolf optimizer algorithm). Also based on the results of the trial of the experiments, the control parameters of comparison algorithms were set as follows. For the BBO algorithm, the maximum immigration rate I_max =1, the maximum emigration rate E_max =1, and the maximum mutation probability m_max = 0.1 [52]. For ICPSO, the part number p_n = I, the inertia weight W = 0.8, the cognitive ratio c₁ = 2, and the social ratio c₂ = 2 [25]. For GA_N2, the crossover probability p_c = 0.8, and the mutation probability p_m = 0.1 [23]. For EGA_OS, the crossover ratio r_c = 0.8, and the mutation ratio r_m = 0.2 [19]. For HGWO, the crossover probability g_c = 0.15, and the mutation probability g_m = 0.85 [41]. The population size NP and the maximum iteration number were set to 90 and 400, respectively. Because of the randomness of the algorithm, each experiment was run 20 times independently.

5.2 Performance of the multi-supply chain collaboration on the CTS model with new task arrival

To evaluate the performance of the multi-supply chain collaboration on the CTS model with new task arrival, we conducted experimental comparisons between the multi-supply chain collaboration and conventional single-supply chain mode at scheduling and rescheduling stages, respectively, using the IMPBBO algorithm. We set the preference weights w₁, w₂, and w₃ to 0.5, 0.3, and 0.2, respectively, and the maximum number of supply chains to 3.

We used three independent tasks as the illustrative case, denoted as T₁, T₂, and T₃, for simulating the real manufacturing environment. T₁ is the tire production, composed of five subtasks, including mixing (ST₁₁), tire component preparation (ST₁₂), molding (ST₁₃), curing (ST₁₄), and product inspection and testing (ST₁₅). T₂ is the motorcycle assembly, composed of six subtasks, including frame assembly (ST₂₁), engine assembly (ST₂₂), parts assembly (ST₂₃), vehicle assembly (ST₂₄), product testing (ST₂₅), and product package (ST₂₆). T₃ is the bus production, composed of five subtasks, including stamping (ST₃₁), welding (ST₃₂), product painting (ST₃₃), product assembly (ST₃₄), and product testing (ST₃₅). During task execution, a new task arrives at time 50, denoted as T₄, which is the car assembly composed of four subtasks, including frame assembly (ST₄₁), engine assembly (ST₄₂), parts assembly (ST₄₃), and product testing (ST₄₄). In addition, there are six different enterprises that provide eight services respectively. Table 2 presents the partial simulation data on QoS values of manufacturing services. Table 3 lists the partial simulation data on transportation time and cost between different enterprises.

Table 2
Partial simulation data on QoS values of manufacturing services (setup time/setup cost/execution time/execution cost/reliability)

Task Subtask MS ₁₁ MS ₁₂ MS ₂₁

T ₁ ST ₁₁ 7.9211/7.9557/63.7963/46.2064/0.9752 8.2883/5.5113/49.8449/60.1551/0.9759 NA

ST ₁₂ NA 6.0238/7.6169/35.7179/74.2803/0.9655 6.7378/8.3673/53.3820/56.6180/0.9650

ST ₁₃ 5.2617/7.0829/39.2048/70.7952/0.9770 9.9598/6.5630/78.5340/31.4660/0.9799 7.3518/5.6814/78.1787/31.8213/0.9725

T ₂ ST ₂₁ 9.9788/5.0429/37.6738/72.3262/0.9698 NA NA

ST ₂₂ 8.9276/5.7968/39.8799/70.1201/0.9728 7.3033/7.9350/46.9998/63.0002/0.9743 9.4837/8.4948/54.5634/55.4366/0.9633

ST ₂₃ 6.6704/5.5477/58.7436/51.2564/0.9724 5.0323/9.0333/35.6939/74.3051/0.9701 7.4482/7.4222/53.7120/56.2880/0.9713

T ₃ ST ₃₁ 7.2183/8.5734/39.7720/70.2280/0.9796 8.4655/7.4981/57.6486/52.3514/0.9752 5.7584/8.5477/31.6277/78.3723/0.9762

ST ₃₂ 9.2233/7.8299/63.1992/46.8008/0.9797 5.2946/6.0464/39.9989/70.0011/0.9686 6.3612/8.6492/36.4149/73.5851/0.9720

ST ₃₃ 6.8718/7.5463/69.4491/40.5509/0.9718 8.4602/7.1507/37.4138/72.5862/0.9675 7.3252/8.3712/55.3184/54.6818/0.9728

T ₄ ST ₄₁ 6.1094/5.668456.7343/53.2657/0.9772 9.7607/7.0062/49.1827/60.8173/0.9606 9.3356/6.8513/73.3107/36.6893/0.9627

ST ₄₂ NA 8.5765/9.9242/70.8732/39.1268/0.9642 NA

ST ₄₃ 7.3980/5.7560/76.6824/33.3176/0.9782 8.4091/7.7145/54.7351/55.2694/0.9786 9.8082/5.6813/47.1732/62.8277/0.9650

Task	Subtask	MS ₁₁	MS ₁₂	MS ₂₁
T ₁	ST ₁₁	7.9211/7.9557/63.7963/46.2064/0.9752	8.2883/5.5113/49.8449/60.1551/0.9759	NA
	ST ₁₂	NA	6.0238/7.6169/35.7179/74.2803/0.9655	6.7378/8.3673/53.3820/56.6180/0.9650
	ST ₁₃	5.2617/7.0829/39.2048/70.7952/0.9770	9.9598/6.5630/78.5340/31.4660/0.9799	7.3518/5.6814/78.1787/31.8213/0.9725
T ₂	ST ₂₁	9.9788/5.0429/37.6738/72.3262/0.9698	NA	NA
	ST ₂₂	8.9276/5.7968/39.8799/70.1201/0.9728	7.3033/7.9350/46.9998/63.0002/0.9743	9.4837/8.4948/54.5634/55.4366/0.9633
	ST ₂₃	6.6704/5.5477/58.7436/51.2564/0.9724	5.0323/9.0333/35.6939/74.3051/0.9701	7.4482/7.4222/53.7120/56.2880/0.9713
T ₃	ST ₃₁	7.2183/8.5734/39.7720/70.2280/0.9796	8.4655/7.4981/57.6486/52.3514/0.9752	5.7584/8.5477/31.6277/78.3723/0.9762
	ST ₃₂	9.2233/7.8299/63.1992/46.8008/0.9797	5.2946/6.0464/39.9989/70.0011/0.9686	6.3612/8.6492/36.4149/73.5851/0.9720
	ST ₃₃	6.8718/7.5463/69.4491/40.5509/0.9718	8.4602/7.1507/37.4138/72.5862/0.9675	7.3252/8.3712/55.3184/54.6818/0.9728
T ₄	ST ₄₁	6.1094/5.668456.7343/53.2657/0.9772	9.7607/7.0062/49.1827/60.8173/0.9606	9.3356/6.8513/73.3107/36.6893/0.9627
	ST ₄₂	NA	8.5765/9.9242/70.8732/39.1268/0.9642	NA
	ST ₄₃	7.3980/5.7560/76.6824/33.3176/0.9782	8.4091/7.7145/54.7351/55.2694/0.9786	9.8082/5.6813/47.1732/62.8277/0.9650

where NA denotes that the corresponding service cannot perform the subtask.

Table 3

Partial simulation data on transportation time and cost between different enterprises

Transportation time/cost	E ₂	E ₃	E ₄	E ₅	E ₆
E ₁	8.9389/6.0611	9.5737/5.4263	6.7247/8.2753	9.5696/5.4304	8.0188/6.9812
E ₂		8.0881/6.9119	5.8357/9.1643	8.2715/6.7285	8.7387/6.2613
E ₃			5.9085/9.0915	9.1491/5.8509	7.0541/7.9459
E ₄				6.3820/8.6180	6.2190/8.7810
E ₅					6.3167/8.6833

Figure 5 shows the QoS value comparisons between the multi-supply chain collaboration and single-supply chain mode at the scheduling stage and the rescheduling stage using RS1 and RS2, respectively. Based on this case, we observed that QoS values of optimal schedules are better in multi-supply chain collaboration than the single-supply chain mode at both scheduling stage and rescheduling stage that deals with new task arrival using either one of the rescheduling strategies.

Fig. 5

Comprehensive QoS value comparisons at scheduling and rescheduling stages between multi-supply chain collaboration and single-supply chain mode using the IMPBBO algorithm.

Based on this case, multi-supply chain collaboration outperforms the conventional single-supply chain mode at both scheduling and rescheduling stages in the CTS model. Therefore, the proposed multi-supply chain collaboration can be applied in the CTS model in the CMfg environment and combined with the two rescheduling strategies to tackle new tasks if the better schedule can be obtained than the conventional single-supply chain mode.

5.3 Performance of the IMPBBO algorithm

To evaluate the performance of the IMPBBO algorithm, we conducted experiments on three small-scale cases (S01–S03), five medium-scale cases (M01–M05), and seven large-scale cases (L01–L07) for simulating the real manufacturing environment. The generating ranges of case data were: for the small-scale cases, the number of tasks ranged from 2 to 10, number of subtasks ranged from 2 to 5, number of enterprises ranged from 5 to 10, and number of services ranged from 5 to 10; for the medium-scale cases, the number of tasks ranged from 10 to 20, number of subtasks ranged from 5 to 10, number of enterprises ranged from 10 to 20, and number of services ranged from 10 to 20; for the large-scale cases, the number of tasks ranged from 20 to 30, number of subtasks ranged from 10 to 15, number of enterprises ranged from 20 to 30, and number of services ranged from 20 to 30. We set the preference weights w₁, w₂, and w₃ to 0.5, 0.3, and 0.2 respectively, and the maximum number of supply chains on small-, medium-, and large-scale cases to 2, 3, and 4 respectively.

Figure 6 displays the evolution curves from 0 to 400 iterations of the six algorithms for solving the CTS problem on case S03. It can be shown that the IMPBBO algorithm can obtain the highest comprehensive QoS value with a faster convergence speed among six algorithms, indicating its stronger local search ability. Moreover, the solutions obtained by the IMPBBO algorithm within 100 iterations can be even better than the results obtained within 400 iterations by other algorithms. In addition, IMPBBO algorithm can further improve the quality of solutions after 200 iterations, showing that it can avoid falling into local optimum and maintain the diversity of populations. Therefore, the proposed algorithm has a superior search capability and good convergence efficiency for solving the CTS problem.

Fig. 6

Evolution curves of six algorithms on case S03.

It is necessary to calculate the statistical parameters including best, worst, mean, median, and standard deviation (SD) to demonstrate the reliability of the proposed IMPBBO algorithm for solving the CTS model. Tables 4 –9 present the statistical parameters and average computation time by the proposed IMPBBO algorithm, the BBO algorithm, ICPSO, GA_N2, EGA_OS, and HGWO in cases with three scales under different weight combinations of time, cost, and reliability. Tables 4, 6, and 8 display that the best results obtained by the IMPBBO algorithm are better than that obtained by the other algorithms for all 15 cases, 12 out of 15 cases, and 11 out of 15 cases, respectively, and the mean values can outperform for 14 out of 15 cases, 14 out of 15 cases, and 13 out of 15 cases, respectively. It can be found that no matter what the scale of the case is, the best, worst, mean, and median QoS values under three different weight combinations obtained by the proposed IMPBBO algorithm are better than those of the other five algorithms in most cases. Moreover, the standard deviation results of the proposed algorithm are relatively low in most cases comparing with other algorithms, showing that IMPBBO algorithm is reliable and stable to solve the CTS problem. Furthermore, with the increase of the scale of the case, it is indicated that the performance gap between the proposed algorithm and other algorithms is more obvious. Because the algorithms are relatively likely to find the near optimal solution in a small search space. However, the tasks are large-scale with massive candidate services in CMfg environment. Thus, the IMPBBO algorithm is more applicable for task scheduling problems in CMfg. From Tables 5, 7, 9, it can be shown that the IMPBBO algorithm spends more computing time than some comparison algorithms, mainly due to its local search to further improve solutions. In the practical manufacturing environment, the fitness function evaluation is the most important part of the optimization algorithm, and the gap of the time consumption between the IMPBBO algorithm and other comparison algorithms is negligible. Therefore, the IMPBBO algorithm can deal with a good trade-off between solution quality and computation time, and is effective and robust for solving the CTS problem in small-, medium-, and large-scale cases.

Table 4

Statistical results of best, worst, and mean QoS values by six algorithms when w₁ = 0.5, w₂ = 0.3, w₃ = 0.2

Case	IMPBBO			BBO			ICPSO			GA_N2			EGA_OS			HGWO
	Best	Worst	Mean	Best	Worst	Mean	Best	Worst	Mean	Best	Worst	Mean	Best	Worst	Mean	Best	Worst	Mean
S01	0.6564	0.6564	0.6564	0.6559	0.6460	0.6520	0.6425	0.6306	0.6357	0.6540	0.6450	0.6479	0.6564	0.6457	0.6545	0.6555	0.6555	0.6555
S02	0.7701	0.7503	0.7555	0.7674	0.7527	0.7599	0.6812	0.6075	0.6650	0.7075	0.6927	0.6992	0.7600	0.7399	0.7503	0.6625	0.6562	0.6594
S03	0.6683	0.6683	0.6683	0.6652	0.6555	0.6610	0.6478	0.6388	0.6441	0.6614	0.6495	0.6542	0.6683	0.6601	0.6653	0.6553	0.6490	0.6525
M01	0.7305	0.7249	0.7284	0.7162	0.7009	0.7095	0.6520	0.6408	0.6457	0.6613	0.6552	0.6580	0.7136	0.7013	0.7063	0.6783	0.6666	0.6725
M02	0.7352	0.7313	0.7327	0.7206	0.7092	0.7172	0.6519	0.6349	0.6459	0.6666	0.6599	0.6631	0.7170	0.7075	0.7118	0.6773	0.6677	0.6725
M03	0.7353	0.7261	0.7308	0.7172	0.7078	0.7123	0.6480	0.6321	0.6387	0.6627	0.6556	0.6595	0.7092	0.7014	0.7071	0.6766	0.6661	0.6704
M04	0.7279	0.7176	0.7225	0.7110	0.7046	0.7078	0.6505	0.6339	0.6413	0.6631	0.6557	0.6579	0.7054	0.6978	0.7024	0.6702	0.6582	0.6641
M05	0.7475	0.7400	0.7430	0.7292	0.7137	0.7218	0.6684	0.6531	0.6592	0.6728	0.6674	0.6702	0.7205	0.7134	0.7173	0.6860	0.6727	0.6804
L01	0.7777	0.7679	0.7722	0.7751	0.7615	0.7697	0.6977	0.6049	0.6768	0.6991	0.6867	0.6935	0.7634	0.7357	0.7508	0.6644	0.6592	0.6620
L02	0.7732	0.7577	0.7676	0.7750	0.7580	0.7695	0.6932	0.5747	0.6678	0.7025	0.6882	0.6961	0.7694	0.7523	0.7619	0.6709	0.6610	0.6653
L03	0.7780	0.7641	0.7728	0.7654	0.7429	0.7555	0.6654	0.5908	0.6424	0.6863	0.6734	0.6790	0.7529	0.7391	0.7473	0.6595	0.6516	0.6542
L04	0.7552	0.7444	0.7511	0.7375	0.7127	0.7268	0.6734	0.6627	0.6683	0.6766	0.6624	0.6691	0.7349	0.7193	0.7282	0.6993	0.6922	0.6958
L05	0.7762	0.7633	0.7722	0.7594	0.7295	0.7474	0.6833	0.6608	0.6701	0.6774	0.6618	0.6701	0.7427	0.7248	0.7361	0.6584	0.6514	0.6546
L06	0.7656	0.7602	0.7639	0.7666	0.7597	0.7626	0.6868	0.6714	0.6790	0.7065	0.6933	0.7003	0.7607	0.7425	0.7529	0.6651	0.6562	0.6597
L07	0.7466	0.7299	0.7381	0.7335	0.7056	0.7166	0.6758	0.5251	0.6552	0.6781	0.6616	0.6696	0.7315	0.7012	0.7200	0.7002	0.6750	0.6909

Table 5

Statistical results of median, and standard deviation QoS values and average computation time by six algorithms when w₁ = 0.5, w₂ = 0.3, w₃ = 0.2

Case	IMPBBO			BBO			ICPSO			GA_N2			EGA_OS			HGWO
	Median	SD (×10^–3)	Time(s)	Median	SD (×10^–3)	Time(s)	Median	SD (×10^–3)	Time(s)	Median	SD (×10^–3)	Time(s)	Median	SD (×10^–3)	Time(s)	Median	SD (×10^–3)	Time(s)
S01	0.6564	0.0000	3.0000	0.6534	3.8922	1.9610	0.6344	3.8507	1.9540	0.6475	2.4022	26.2110	0.6564	3.5856	3.1870	0.6555	0.0000	4.6460
S02	0.7533	5.9451	13.8730	0.7594	4.4957	5.0520	0.6747	23.7334	5.8510	0.6974	5.6114	72.0900	0.7503	6.8440	8.2290	0.6594	2.0899	12.1170
S03	0.6683	0.0000	1.7850	0.6613	3.2407	0.3920	0.6441	2.5924	0.4050	0.6535	3.5408	5.2360	0.6652	2.4920	0.6370	0.6528	2.3368	0.9060
M01	0.7288	1.7864	6.4280	0.7109	5.9784	2.4670	0.6453	3.5349	2.5590	0.6578	1.8853	32.9800	0.7066	3.6479	3.9390	0.6732	4.1734	5.8280
M02	0.7325	1.2526	6.4300	0.7182	3.3204	2.4610	0.6481	5.4815	2.5120	0.6624	2.2826	32.6940	0.7120	3.1568	3.9390	0.6725	3.4956	5.7840
M03	0.7304	2.7541	7.3430	0.7120	3.4385	2.8060	0.6378	5.4335	2.9010	0.6597	2.2686	37.2250	0.7078	2.3434	4.4650	0.6706	3.1269	6.5580
M04	0.7226	3.0136	6.3340	0.7083	1.9842	2.4190	0.6414	4.6508	2.4660	0.6573	2.1545	32.1830	0.7035	2.6249	3.8570	0.6650	4.3386	5.6750
M05	0.7432	2.1166	6.6330	0.7215	5.6257	2.5300	0.6583	5.2329	2.6440	0.6702	2.0336	33.8610	0.7172	2.4317	4.0220	0.6811	3.6217	5.9510
L01	0.7713	3.6224	16.8760	0.7711	4.7384	6.1890	0.6822	26.2060	7.3590	0.6941	4.0438	88.4140	0.7521	8.7690	9.9920	0.6615	1.6366	14.6650
L02	0.7673	4.9787	17.6360	0.7718	5.4956	6.6420	0.6853	38.3688	7.6130	0.6962	4.2076	92.0770	0.7623	5.0044	10.3740	0.6650	3.4842	15.3920
L03	0.7730	3.8203	18.4560	0.7546	6.5820	6.9040	0.6581	29.9405	8.1300	0.6778	4.7935	97.7610	0.7470	4.3609	11.1710	0.6541	2.2633	16.2870
L04	0.7530	3.9765	15.9690	0.7269	7.7586	5.8310	0.6682	3.3495	6.6140	0.6681	4.4233	84.5510	0.7281	4.0017	9.1630	0.6954	2.6397	13.9510
L05	0.7726	3.9314	17.3120	0.7492	8.4727	6.5830	0.6706	7.2653	7.6370	0.6706	4.2655	91.5000	0.7371	5.7331	10.4050	0.6545	2.4033	15.3030
L06	0.7641	1.6397	14.6220	0.7620	2.3506	5.5120	0.6795	4.9571	6.3180	0.6992	5.0447	77.4650	0.7529	6.2377	8.7860	0.6591	2.4600	13.1070
L07	0.7369	6.0202	14.8610	0.7158	8.6334	5.4930	0.6686	45.7748	6.0880	0.6688	5.6375	77.2190	0.7222	8.6170	8.5910	0.6937	8.3503	12.8960

Table 6

Statistical results of best, worst, and mean QoS values obtained by six algorithms when w₁ = 0.3, w₂ = 0.4, w₃ = 0.3

Case	IMPBBO			BBO			ICPSO			GA_N2			EGA_OS			HGWO
	Best	Worst	Mean	Best	Worst	Mean	Best	Worst	Mean	Best	Worst	Mean	Best	Worst	Mean	Best	Worst	Mean
S01	0.5579	0.5579	0.5579	0.5579	0.5251	0.5485	0.5394	0.5214	0.5296	0.5578	0.5529	0.5571	0.5579	0.5579	0.5579	0.5550	0.5550	0.5550
S02	0.6767	0.6718	0.6734	0.6741	0.6593	0.6695	0.5650	0.5304	0.5535	0.6372	0.6133	0.6253	0.6724	0.6491	0.6595	0.5415	0.5225	0.5281
S03	0.5498	0.5498	0.5498	0.5589	0.5402	0.5497	0.5411	0.5281	0.5338	0.5578	0.5457	0.5516	0.5664	0.5441	0.5531	0.5487	0.5385	0.5443
M01	0.6487	0.6425	0.6457	0.6421	0.6324	0.6379	0.5449	0.5298	0.5379	0.5987	0.5761	0.5867	0.6348	0.6272	0.6306	0.5939	0.5752	0.5822
M02	0.6290	0.6219	0.6254	0.6238	0.6101	0.6188	0.5398	0.5240	0.5335	0.5847	0.5488	0.5701	0.6190	0.6042	0.6140	0.5700	0.5574	0.5637
M03	0.6488	0.6430	0.6451	0.6441	0.6161	0.6380	0.5567	0.5417	0.5486	0.6115	0.5877	0.5999	0.6344	0.6030	0.6271	0.5951	0.5806	0.5868
M04	0.6256	0.6176	0.6212	0.6181	0.6006	0.6119	0.5470	0.5241	0.5336	0.5662	0.5416	0.5560	0.6128	0.5947	0.6053	0.5624	0.5438	0.5516
M05	0.6360	0.6236	0.6286	0.6295	0.6190	0.6241	0.5552	0.5357	0.5437	0.5884	0.5611	0.5781	0.6224	0.6078	0.6172	0.5842	0.5357	0.5713
L01	0.6860	0.6783	0.6815	0.6850	0.6659	0.6773	0.5637	0.4810	0.5447	0.6279	0.5966	0.6093	0.6736	0.6451	0.6596	0.5348	0.5234	0.5276
L02	0.6839	0.6780	0.6809	0.6836	0.6656	0.6775	0.5640	0.5206	0.5529	0.6246	0.6062	0.6155	0.6810	0.6553	0.6668	0.5352	0.5265	0.5302
L03	0.6841	0.6760	0.6821	0.6848	0.6745	0.6799	0.5711	0.5212	0.5586	0.6204	0.5956	0.6104	0.6745	0.6488	0.6584	0.5336	0.5251	0.5290
L04	0.6714	0.6674	0.6696	0.6565	0.6420	0.6476	0.5567	0.5358	0.5450	0.5878	0.5821	0.5846	0.6565	0.6404	0.6518	0.6540	0.5946	0.6076
L05	0.6849	0.6753	0.6822	0.6695	0.6466	0.6618	0.5564	0.5350	0.5432	0.6063	0.5726	0.5907	0.6566	0.6403	0.6480	0.5304	0.5179	0.5221
L06	0.6756	0.6729	0.6743	0.6766	0.6636	0.6713	0.5623	0.5419	0.5527	0.6436	0.6242	0.6329	0.6656	0.6420	0.6576	0.5354	0.5278	0.5317
L07	0.6683	0.6641	0.6665	0.6604	0.6474	0.6553	0.5611	0.5361	0.5512	0.6039	0.5821	0.5924	0.6602	0.6389	0.6481	0.6143	0.5458	0.5954

Table 7

Statistical results of median, and standard deviation QoS values and average computation time by six algorithms when w₁ = 0.3, w₂ = 0.4, w₃ = 0.3

Case	IMPBBO			BBO			ICPSO			GA_N2			EGA_OS			HGWO
	Median	SD (×10^–3)	Time (s)	Median	SD (×10^–3)	Time (s)	Median	SD (×10^–3)	Time (s)	Median	SD (×10^–3)	Time (s)	Median	SD (×10^–3)	Time (s)	Median	SD (×10^–3)	Time (s)
S01	0.5579	0.0000	2.9950	0.5520	10.9993	1.9260	0.5310	6.4975	1.9440	0.5578	1.5460	25.6100	0.5579	0.0000	3.1960	0.5550	0.0000	4.6060
S02	0.6727	1.6975	12.9460	0.6694	4.4915	5.0540	0.5569	11.2300	5.9060	0.6266	7.2090	69.0000	0.6603	7.4809	8.1850	0.5271	5.6961	12.1060
S03	0.5498	0.0000	1.7480	0.5498	4.9721	0.3760	0.5333	4.3347	0.4010	0.5515	4.4768	5.0700	0.5498	7.8735	0.6240	0.5438	2.8003	0.9040
M01	0.6461	1.9497	5.9660	0.6380	2.9712	2.3260	0.5373	5.3702	2.5350	0.5848	6.4879	31.5260	0.6305	2.6425	3.7740	0.5824	5.9203	5.6570
M02	0.6262	2.9036	6.0290	0.6192	3.8225	2.2880	0.5347	4.7930	2.4910	0.5763	15.4870	31.3930	0.6152	4.8769	3.7100	0.5626	4.4543	5.5880
M03	0.6448	1.6672	6.7550	0.6399	7.9592	2.5880	0.5466	5.4577	2.8750	0.6003	7.3794	34.8480	0.6314	11.0236	4.2080	0.5859	4.7386	6.3270
M04	0.6210	2.8307	6.1290	0.6147	6.5348	2.2800	0.5330	6.3526	2.4520	0.5573	7.1327	31.6320	0.6090	6.4964	3.6990	0.5514	5.2471	5.6170
M05	0.6289	3.6121	6.3130	0.6238	2.8316	2.4010	0.5415	5.9447	2.6330	0.5789	8.0208	32.7610	0.6185	4.4944	3.8630	0.5780	15.7391	5.8210
L01	0.6810	2.4131	16.3180	0.6773	5.3541	6.1500	0.5574	29.0181	7.4860	0.6080	9.5173	85.0380	0.6585	8.2705	9.9290	0.5273	2.9600	14.6670
L02	0.6810	1.9141	16.9020	0.6787	5.9964	6.3230	0.5579	12.6739	7.7200	0.6167	6.0626	88.0570	0.6661	8.2081	10.4690	0.5303	2.7661	15.1520
L03	0.6824	2.3577	18.0020	0.6809	3.7532	6.9170	0.5612	14.4474	8.2030	0.6098	6.9692	93.1640	0.6559	8.4615	11.0510	0.5286	2.6181	16.2790
L04	0.6696	1.0273	14.8100	0.6463	5.0378	5.7370	0.5430	8.1645	6.7130	0.5841	2.0767	80.8810	0.6529	4.5857	9.0170	0.6055	17.0783	13.8590
L05	0.6833	2.7588	16.6950	0.6639	7.2145	6.3440	0.5411	7.9234	7.6710	0.5901	10.2196	87.4970	0.6478	5.6222	10.3900	0.5212	4.3174	15.0170
L06	0.6743	1.0127	14.0240	0.6728	4.5931	5.4410	0.5513	6.8127	6.3270	0.6325	6.5805	73.3910	0.6597	7.7529	9.1670	0.5319	2.2406	13.0970
L07	0.6667	1.2803	13.5760	0.6558	3.5169	5.2230	0.5504	7.6766	6.0540	0.5921	6.4600	73.1250	0.6494	6.7799	8.3650	0.5989	18.1392	12.8100

Table 8

Statistical results of best, worst, and mean QoS values obtained by six algorithms when w₁ = 0.4, w₂ = 0.2, w₃ = 0.4

Case	IMPBBO			BBO			ICPSO			GA_N2			EGA_OS			HGWO
	Best	Worst	Mean	Best	Worst	Mean	Best	Worst	Mean	Best	Worst	Mean	Best	Worst	Mean	Best	Worst	Mean
S01	0.4935	0.4935	0.4935	0.4934	0.4880	0.4904	0.4837	0.4775	0.4796	0.4928	0.4868	0.4894	0.4935	0.4896	0.4923	0.4885	0.4885	0.4885
S02	0.5691	0.5624	0.5673	0.5732	0.5585	0.5681	0.5204	0.4964	0.5137	0.5321	0.5197	0.5234	0.5690	0.5577	0.5649	0.5095	0.5026	0.5063
S03	0.5013	0.5013	0.5013	0.5023	0.4931	0.4987	0.4907	0.4818	0.4867	0.4981	0.4888	0.4936	0.5032	0.4989	0.5008	0.4962	0.4922	0.4941
M01	0.5415	0.5372	0.5394	0.5312	0.5231	0.5286	0.4850	0.4745	0.4779	0.4939	0.4887	0.4910	0.5309	0.5199	0.5249	0.5058	0.4974	0.5010
M02	0.5434	0.5390	0.5417	0.5347	0.5291	0.5319	0.4852	0.4752	0.4788	0.4981	0.4931	0.4950	0.5326	0.5239	0.5265	0.5052	0.4990	0.5019
M03	0.5503	0.5449	0.5473	0.5404	0.5296	0.5352	0.4877	0.4822	0.4846	0.5024	0.4977	0.4995	0.5360	0.5294	0.5326	0.5091	0.5020	0.5067
M04	0.5445	0.5413	0.5433	0.5388	0.5289	0.5329	0.4908	0.4825	0.4855	0.5026	0.4961	0.4986	0.5310	0.5241	0.5279	0.5078	0.5027	0.5052
M05	0.5431	0.5389	0.5418	0.5335	0.5290	0.5308	0.4853	0.4782	0.4812	0.4969	0.4908	0.4935	0.5269	0.5241	0.5259	0.5054	0.4993	0.5023
L01	0.5851	0.5736	0.5798	0.5837	0.5719	0.5775	0.5283	0.5147	0.5189	0.5244	0.5190	0.5218	0.5709	0.5586	0.5661	0.5134	0.5081	0.5102
L02	0.5798	0.5738	0.5773	0.5802	0.5660	0.5728	0.5217	0.5060	0.5156	0.5294	0.5189	0.5233	0.5749	0.5591	0.5659	0.5090	0.5040	0.5063
L03	0.5832	0.5753	0.5802	0.5813	0.5636	0.5742	0.5243	0.4827	0.5106	0.5275	0.5168	0.5225	0.5736	0.5609	0.5659	0.5083	0.5043	0.5058
L04	0.5664	0.5581	0.5623	0.5511	0.5394	0.5447	0.5214	0.4401	0.5034	0.5155	0.5074	0.5104	0.5570	0.5435	0.5492	0.5322	0.4865	0.5242
L05	0.5804	0.5721	0.5770	0.5817	0.5639	0.5741	0.5317	0.4391	0.5099	0.5240	0.5163	0.5200	0.5750	0.5548	0.5679	0.5086	0.5054	0.5071
L06	0.5759	0.5644	0.5701	0.5752	0.5681	0.5715	0.5210	0.4500	0.5111	0.5326	0.5250	0.5296	0.5683	0.5545	0.5635	0.5080	0.5020	0.5056
L07	0.5604	0.5538	0.5560	0.5360	0.5249	0.5313	0.5110	0.4925	0.5044	0.5047	0.4986	0.5019	0.5398	0.5270	0.5315	0.5197	0.5058	0.5128

Table 9

Statistical results of median, and standard deviation QoS values and average computation time by six algorithms when w₁ = 0.4, w₂ = 0.2, w₃ = 0.4

Case	IMPBBO			BBO			ICPSO			GA_N2			EGA_OS			HGWO
	Median	SD (×10^–3)	Time(s)	Median	SD (×10^–3)	Time(s)	Median	SD (×10^–3)	Time(s)	Median	SD (×10^–3)	Time(s)	Median	SD (×10^–3)	Time(s)	Median	SD (×10^–3)	Time(s)
S01	0.4935	0.0000	2.7450	0.4894	2.2233	1.9180	0.4791	1.9085	1.9660	0.4891	2.0447	26.1060	0.4935	1.5738	2.9390	0.4885	0.0000	4.4520
S02	0.5676	1.9031	14.0770	0.5690	5.1697	5.3880	0.5157	7.5158	5.7530	0.5228	4.1136	72.1110	0.5661	4.1973	8.2400	0.5060	2.0627	12.3350
S03	0.5013	0.0000	1.7900	0.4995	3.0605	0.3910	0.4865	3.5490	0.4100	0.4934	2.8646	5.2370	0.5009	1.3070	0.6410	0.4942	1.2136	0.9050
M01	0.5394	1.2245	6.4930	0.5294	2.4746	2.4890	0.4769	3.1460	2.5530	0.4910	1.7172	33.1810	0.5247	3.3341	3.9480	0.5006	2.4143	5.8110
M02	0.5422	1.4602	6.4780	0.5321	1.7797	2.4760	0.4782	2.7925	2.5420	0.4948	1.6083	32.8450	0.5256	2.8816	3.9470	0.5018	1.6943	5.7800
M03	0.5472	1.6536	7.3980	0.5353	2.8242	2.8050	0.4847	1.5928	2.9130	0.4995	1.5290	37.3920	0.5327	2.1162	4.4720	0.5067	2.0247	6.5660
M04	0.5434	0.9380	6.3370	0.5327	2.8584	2.4480	0.4849	2.4087	2.5110	0.4980	2.2716	32.3670	0.5279	2.1211	3.8740	0.5056	1.8070	5.6960
M05	0.5422	1.2698	6.7590	0.5304	1.3619	2.5900	0.4808	2.1493	2.6580	0.4934	1.7416	34.2000	0.5259	0.8531	4.0990	0.5027	2.2983	6.0200
L01	0.5800	3.4697	16.3920	0.5773	3.6981	6.1880	0.5166	4.7093	7.3810	0.5216	1.6040	89.0780	0.5657	3.8374	9.6700	0.5098	1.8338	14.5990
L02	0.5779	1.8371	15.2090	0.5707	4.8033	6.0600	0.5171	5.0510	7.6870	0.5220	3.5574	91.4850	0.5655	5.3998	9.5170	0.5060	1.5581	14.2740
L03	0.5804	2.3629	15.2990	0.5751	5.6400	6.0760	0.5135	11.1825	8.1520	0.5229	3.1576	94.3110	0.5663	3.7561	9.0330	0.5057	1.3626	14.0020
L04	0.5622	2.7835	16.4830	0.5451	3.4394	5.8750	0.5147	26.3846	6.5610	0.5099	2.3157	84.2360	0.5487	4.1458	9.1330	0.5289	13.5139	13.9030
L05	0.5773	2.8138	15.3050	0.5734	5.3191	6.0250	0.5175	25.6137	7.5380	0.5195	2.2768	90.3200	0.5683	5.8846	9.4570	0.5072	1.2374	14.1490
L06	0.5702	3.2908	14.8520	0.5721	2.2750	5.4900	0.5174	21.5852	6.2580	0.5297	2.5096	77.9320	0.5639	4.3500	8.8440	0.5058	1.7131	13.0770
L07	0.5555	1.8102	15.6250	0.5321	3.3913	5.6200	0.5054	6.1533	6.0640	0.5015	1.8058	77.9100	0.5300	4.6839	8.9870	0.5128	4.2188	13.2230

Wilcoxon-test has been conducted to further demonstrate that the proposed IMPBBO algorithm performs better than the comparison algorithms for addressing CTS problems at 0.05 level of significance. The null hypothesis (H₀) has been defined as there is no difference between the performances of both algorithms. The alternative hypothesis (H₁) defined as there is a difference between the performances of both algorithms. The result of 20 independent runs was taken from each algorithm as a sampling data and the obtained p-values under three different weight combinations are listed in Tables 10 –12. It can be seen that the p-values for most cases are smaller than 0.05, showing that there is a significant difference for most cases. The H₀ is rejected with the strong evidence. In addition, when the scale is small, the performance difference between the IMPBBO algorithm and the comparison algorithm is more likely not significant. Because the algorithms are relatively likely to find the near optimal solution in a small search space. With the increase of the problem scale, the performance difference between the IMPBBO algorithm and comparison algorithms becomes more obvious, reflecting the stronger search ability of the IMPBBO algorithm. Thus, it can be concluded that the performance of the IMPBBO algorithm outperforms other comparison algorithms for solving CTS problems.

Table 10

Wilcoxon-test results when w₁ = 0.5, w₂ = 0.3, w₃ = 0.2

Case	IMPBBO vs. BBO	IMPBBO vs. ICPSO	IMPBBO vs. GA_N2	IMPBBO vs. EGA_OS	IMPBBO vs. HGWO
S01	0.000	0.000	0.000	0.183	0.000
S02	0.008	0.000	0.000	0.036	0.000
S03	0.000	0.000	0.000	0.000	0.000
M01	0.000	0.000	0.000	0.000	0.000
M02	0.000	0.000	0.000	0.000	0.000
M03	0.000	0.000	0.000	0.000	0.000
M04	0.000	0.000	0.000	0.000	0.000
M05	0.000	0.000	0.000	0.000	0.000
L01	0.093	0.000	0.000	0.000	0.000
L02	0.411	0.000	0.000	0.008	0.000
L03	0.000	0.000	0.000	0.000	0.000
L04	0.000	0.000	0.000	0.000	0.000
L05	0.000	0.000	0.000	0.000	0.000
L06	0.025	0.000	0.000	0.000	0.000
L07	0.000	0.000	0.000	0.000	0.000

Table 11

Wilcoxon-test results when w₁ = 0.3, w₂ = 0.4, w₃ = 0.3

Case	IMPBBO vs. BBO	IMPBBO vs. ICPSO	IMPBBO vs. GA_N2	IMPBBO vs. EGA_OS	IMPBBO vs. HGWO
S01	0.000	0.000	0.000	0.063	0.000
S02	0.001	0.000	0.000	0.000	0.000
S03	0.574	0.000	0.117	0.048	0.000
M01	0.000	0.000	0.000	0.000	0.000
M02	0.000	0.000	0.000	0.000	0.000
M03	0.000	0.000	0.000	0.000	0.000
M04	0.000	0.000	0.000	0.000	0.000
M05	0.000	0.000	0.000	0.000	0.000
L01	0.012	0.000	0.000	0.000	0.000
L02	0.017	0.000	0.000	0.000	0.000
L03	0.048	0.000	0.000	0.000	0.000
L04	0.000	0.000	0.000	0.000	0.000
L05	0.000	0.000	0.000	0.000	0.000
L06	0.012	0.000	0.000	0.000	0.000
L07	0.000	0.000	0.000	0.000	0.000

Table 12

Wilcoxon-test results when w₁ = 0.4, w₂ = 0.2, w₃ = 0.4

Case	IMPBBO vs. BBO	IMPBBO vs. ICPSO	IMPBBO vs. GA_N2	IMPBBO vs. EGA_OS	IMPBBO vs. HGWO
S01	0.000	0.000	0.000	0.005	0.000
S02	0.433	0.000	0.000	0.033	0.000
S03	0.000	0.000	0.000	0.112	0.000
M01	0.000	0.000	0.000	0.000	0.000
M02	0.000	0.000	0.000	0.000	0.000
M03	0.000	0.000	0.000	0.000	0.000
M04	0.000	0.000	0.000	0.000	0.000
M05	0.000	0.000	0.000	0.000	0.000
L01	0.036	0.000	0.000	0.000	0.000
L02	0.002	0.000	0.000	0.000	0.000
L03	0.000	0.000	0.000	0.000	0.000
L04	0.000	0.000	0.000	0.033	0.000
L05	0.005	0.000	0.000	0.000	0.000
L06	0.100	0.000	0.000	0.000	0.000
L07	0.000	0.000	0.000	0.000	0.000

5.4 Performance of the rescheduling strategies

We applied two rescheduling strategies with the IMPBBO algorithm for solving the proposed model, and we compared them on new 15 cases (R01–R15) which have the same data range as the cases that are generated in the experiments in sub-section 5.3. Moreover, considering the new task arrival in this sub-section, the data about the number of new tasks, and task arrival time were randomly generated between the intervals [1, 8], and [50, 300], respectively.

Table 13 list the comprehensive QoS values on 15 cases under different task arrival times and different weight combinations using two rescheduling strategies obtained by the IMPBBO algorithm.

Table 13
Comparison results of comprehensive QoS values under different task arrival times and weight combinations between RS1 and RS2

Case New task number Arrival time w₁ = 0.5, w₂ = 0.3, w₃ = 0.2 w₁ = 0.3, w₂ = 0.4, w₃ = 0.3 w₁ = 0.4, w₂ = 0.2, w₃ = 0.4

RS1 RS2 RS1 RS2 RS1 RS2

R01.1 2 50 0.6406 0.6409 0.5441 0.5443 0.4852 0.4857

R01.2 238 0.5355 0.5363 0.4242 0.4252 0.4125 0.4117

R02.1 3 100 0.6460 0.6444 0.5574 0.5578 0.4936 0.4938

R02.2 267 0.5293 0.5331 0.4639 0.4628 0.4159 0.4234

R03.1 3 104 0.7036 0.7040 0.5954 0.5977 0.5288 0.5288

R03.2 202 0.6689 0.6700 0.5615 0.5612 0.5043 0.5035

R04.1 4 108 0.6460 0.6444 0.5574 0.5578 0.4936 0.4938

R04.2 273 0.5293 0.5331 0.4639 0.4628 0.4159 0.4234

R05.1 4 139 0.5642 0.5679 0.4768 0.4768 0.4357 0.4367

R05.2 268 0.5073 0.5050 0.4125 0.4159 0.3981 0.4016

R01.1 3 127 0.7167 0.7171 0.6252 0.6252 0.5373 0.5374

R01.2 233 0.6830 0.6856 0.5861 0.5860 0.5078 0.5095

R02.1 5 160 0.7253 0.7252 0.6271 0.6273 0.5483 0.5483

R02.2 224 0.7050 0.7051 0.6040 0.6041 0.5342 0.5344

R03.1 4 110 0.6585 0.6625 0.5653 0.5652 0.5018 0.5022

R03.2 238 0.6141 0.6142 0.5128 0.5138 0.4694 0.4705

R04.1 4 160 0.7242 0.7244 0.6242 0.6244 0.5467 0.5467

R04.2 253 0.7110 0.7115 0.6096 0.6093 0.5371 0.5373

R05.1 2 150 0.7177 0.7172 0.6201 0.6195 0.5372 0.5360

R05.2 258 0.7102 0.7105 0.6101 0.6104 0.5293 0.5296

R06.1 7 125 0.7030 0.7031 0.5982 0.5987 0.5185 0.5198

R06.2 254 0.6576 0.6611 0.5411 0.5429 0.4785 0.4800

R07.1 4 143 0.7127 0.7130 0.6105 0.6103 0.5285 0.5292

R07.2 287 0.6825 0.6825 0.5752 0.5753 0.5016 0.5027

R08.1 2 150 0.7274 0.7275 0.6287 0.6287 0.5409 0.5409

R08.2 256 0.7199 0.7200 0.6188 0.6188 0.5336 0.5340

R09.1 3 104 0.7058 0.7058 0.6068 0.6068 0.5334 0.5335

R09.2 253 0.6437 0.6440 0.5519 0.5519 0.4916 0.4922

R10.1 3 169 0.7151 0.7152 0.6236 0.6235 0.5384 0.5383

R10.2 241 0.6804 0.6834 0.5934 0.5946 0.5150 0.5167

Case	New task number	Arrival time	w₁ = 0.5, w₂ = 0.3, w₃ = 0.2	w₁ = 0.3, w₂ = 0.4, w₃ = 0.3	w₁ = 0.4, w₂ = 0.2, w₃ = 0.4
R01.1	2	50	0.6406	0.6409	0.5441	0.5443	0.4852	0.4857
R01.2		238	0.5355	0.5363	0.4242	0.4252	0.4125	0.4117
R02.1	3	100	0.6460	0.6444	0.5574	0.5578	0.4936	0.4938
R02.2		267	0.5293	0.5331	0.4639	0.4628	0.4159	0.4234
R03.1	3	104	0.7036	0.7040	0.5954	0.5977	0.5288	0.5288
R03.2		202	0.6689	0.6700	0.5615	0.5612	0.5043	0.5035
R04.1	4	108	0.6460	0.6444	0.5574	0.5578	0.4936	0.4938
R04.2		273	0.5293	0.5331	0.4639	0.4628	0.4159	0.4234
R05.1	4	139	0.5642	0.5679	0.4768	0.4768	0.4357	0.4367
R05.2		268	0.5073	0.5050	0.4125	0.4159	0.3981	0.4016
R01.1	3	127	0.7167	0.7171	0.6252	0.6252	0.5373	0.5374
R01.2		233	0.6830	0.6856	0.5861	0.5860	0.5078	0.5095
R02.1	5	160	0.7253	0.7252	0.6271	0.6273	0.5483	0.5483
R02.2		224	0.7050	0.7051	0.6040	0.6041	0.5342	0.5344
R03.1	4	110	0.6585	0.6625	0.5653	0.5652	0.5018	0.5022
R03.2		238	0.6141	0.6142	0.5128	0.5138	0.4694	0.4705
R04.1	4	160	0.7242	0.7244	0.6242	0.6244	0.5467	0.5467
R04.2		253	0.7110	0.7115	0.6096	0.6093	0.5371	0.5373
R05.1	2	150	0.7177	0.7172	0.6201	0.6195	0.5372	0.5360
R05.2		258	0.7102	0.7105	0.6101	0.6104	0.5293	0.5296
R06.1	7	125	0.7030	0.7031	0.5982	0.5987	0.5185	0.5198
R06.2		254	0.6576	0.6611	0.5411	0.5429	0.4785	0.4800
R07.1	4	143	0.7127	0.7130	0.6105	0.6103	0.5285	0.5292
R07.2		287	0.6825	0.6825	0.5752	0.5753	0.5016	0.5027
R08.1	2	150	0.7274	0.7275	0.6287	0.6287	0.5409	0.5409
R08.2		256	0.7199	0.7200	0.6188	0.6188	0.5336	0.5340
R09.1	3	104	0.7058	0.7058	0.6068	0.6068	0.5334	0.5335
R09.2		253	0.6437	0.6440	0.5519	0.5519	0.4916	0.4922
R10.1	3	169	0.7151	0.7152	0.6236	0.6235	0.5384	0.5383
R10.2		241	0.6804	0.6834	0.5934	0.5946	0.5150	0.5167

The results from Table 13 show that RS2 can obtain better comprehensive QoS values in most cases because RS2 can make best use of the idle time of available services. However, in some cases with relatively few services, RS1 has a better performance because RS2 prefers to insert new tasks into the idle time of services while ignoring other better available candidate services. In addition, RS1 can be applied to deal with more dynamic events in the production process than RS2, such as service disruption and task cancel. Thus, two rescheduling strategies are both practical and can be applied in the practical manufacturing environment. Decision makers can choose any one according to their preference and the practical manufacturing environment.

Figure 7 indicates a Gantt chart of the optimal solution of the case R01 using the IMPBBO algorithm when w₁ = 0.5, w₂ = 0.3, w₃ = 0.2.

Fig. 7

Gantt chart of the optimal solution of the case R01 using the IMPBBO algorithm.

Figures 8 and 9 show the Gantt charts of the optimal solutions of the case R01.1 by RS1 and RS2, respectively, using IMPBBO algorithm when w₁ = 0.5, w₂ = 0.3, and w₃ = 0.2. The arrangement of previous existing subtasks remains unchanged. A new task arrives at time 50. In Fig. 8, new subtasks are executed by services whose assigned subtasks are completed after time 50, whereas in Fig. 9, two subtasks on the first supply chain and one subtask on the second supply chain of the new task are inserted into the idle time of available services after time 50.

Fig. 8

Gantt chart of the optimal solution of the case R01.1 by RS1 using the IMPBBO algorithm.

Fig. 9

Gantt chart of the optimal solution of the case R01.1 by RS2 using the IMPBBO algorithm.

6 Conclusion

Considering dynamic task arrival over time, this study proposed a novel multi-objective optimization mathematical model of the CTS problem with new task arrival, which explored the mode of multi-supply chain collaboration by considering both horizontal and vertical cooperation among service suppliers. To solve the model, a new IMPBBO algorithm was presented that uses a matrix-based solution representation, and integrates the multi-population strategy, local search for the best solution, and the collaboration mechanism.

The comparative experiments between the multi-supply chain collaboration and conventional single-supply chain mode indicated that the multi-supply chain collaboration can be applied in the practical manufacturing environment so as to obtain the better schedule. Furthermore, to demonstrate the effectiveness of the proposed IMPBBO algorithm, simulation experiments with different problem scales were conducted. The experimental results concerning best, worst, mean, median, and standard deviation showed that the proposed algorithm can obtain solutions with higher quality for solving the CTS model with new task arrival than the BBO algorithm, ICPSO, GA_N2, EGA_OS, and HGWO. Low standard deviation values of the IMPBBO algorithm indicated that it is reliable to solve the CTS problem in CMfg. Wilcoxon-test has been conducted to demonstrate that the performance of the IMPBBO algorithm is significantly better than other five comparison algorithms. Moreover, according to the experimental results of rescheduling strategies under different weight combinations, the final schedule and rescheduling strategies triggered after new task arrival can be determined. Therefore, the proposed CTS model and IMPBBO algorithm can be applied to task scheduling in CMfg platform, which can be helpful for improving the efficiency of service utilization and the quality of schedule plan decision making, and rescheduling strategies can provide valuable advice for decision makers when new tasks arrive.

However, this study continues to have some limitations to be improved upon in the future. For example, the subtasks of the same task can be undertaken by different number of services. Furthermore, more complex transportation network can be considered when realizing the task scheduling plan. In addition, the efficiency of the IMPBBO algorithm could be further enhanced. In the future, we intend to explore more scheduling methods for the dynamic task arrival over time, and further improve the performance of the algorithm for solving the task scheduling problem in CMfg.

Supporting information

All experimental data used in this study have been uploaded to the Figshare database (https://doi.org/10.6084/m9.figshare.13726507.v1).

References

Zhang

, Luo

Y.L.

, Tao

, Li

B.H.

, Ren

, Zhang

X.S.

, Guo

, Cheng

, Hu

A.R.

and Kui

Y.K.

, Cloud manufacturing: a new manufacturing paradigm, Enterprise Information Systems 8(2) (2014), 167–187.

, From cloud computing to cloud manufacturing, Robotics and Computer-Integrated Manufacturing 28(1) (2012), 75–86.

Liu

Y.K.

, Xu

, Zhang

, Wang

and Zhong

R.Y.

, Workload-based multi-task scheduling in cloud manufacturing, Robotics and Computer-Integrated Manufacturing 45 (2017), 3–20.

Liu

Y.K.

, Wang

L.H.

, Wang

X.V.

, Xu

and Zhang

, Scheduling in cloud manufacturing: state-of-the-art and research challenges, International Journal of Production Research 57(15–16) (2019), 4854–4879.

Liang

and Du

, Dynamic service selection with QoS constraints and inter-service correlations using cooperative coevolution, Future Generation Computer Systems 76 (2017), 119–135.

Garg

, A hybrid PSO-GA algorithm for constrained optimization problems, Applied Mathematics and Computation 274 (2016), 292–305.

Garg

, A hybrid GA-GSA algorithm for optimizing the performance of an industrial system by utilizing uncertain data, Handbook of Research on Artificial Intelligence Techniques and Algorithms IGI Global, (2015), 620–654.

Said

G.A.E.N.A.

, A comparative study of meta-heuristic algorithms for solving quadratic assignment problem, arXiv preprint arXiv:1407.4863 (2014).

Asghari

and Nima

N.J.

, Nature inspired meta-heuristic algorithms for solving the service composition problem in the cloud environments, International Journal of Communication Systems 31(12) (2018), e3708.

10.

Garg

, A hybrid GSA-GA algorithm for constrained optimization problems, Information Sciences 478 (2019), 499–523.

11.

Simon

, Biogeography-based optimization, IEEE Transactions on Evolutionary Computation 12(6) (2008), 702–713.

12.

Yang

, Zhang

, Yang

, Ji

, Dong

and Wang

, Automated classification of brain images using wavelet-energy and biogeography-based optimization, Multimedia Tools and Applications 75(23) (2016), 15601–15617.

13.

Sangaiah

A.K.

, Bian

G.B.

, Bozorgi

S.M.

, Suraki

M.Y.

, Hosseinabadi

A.A.R.

and Shareh

M.B.

, A novel quality-of-service-aware web services composition using biogeography-based optimization algorithm, Soft Computing 24(11) (2019), 8125–8137.

14.

Kaveh

and Mohammad

M.S.

, Improved biogeography-based optimization using migration process adjustment: An approach for location-allocation of ambulances, Computers & Industrial Engineering 135 (2019), 800–813.

15.

Tao

, Guo

, Zhang

and Cheng

, Modelling of combinable relationship-based composition service network and the theoretical proof of its scale-free characteristics, Enterprise Information Systems 6(4) (2012), 373–404.

16.

Lartigau

, Xu

X.F.

, Nie

L.S.

and Zhan

D.C.

, Cloud manufacturing service composition based on QoS with geo-perspective transportation using an improved Artificial Bee Colony optimisation algorithm, International Journal of Production Research 53(14) (2015), 4380–4404.

17.

X.R.

, Yu

S.H.

and Chu

J.J.

, Optimal selection of manufacturing services in cloud manufacturing: A novel hybrid MCDM approach based on rough ANP and rough TOPSIS, Journal of Intelligent & Fuzzy Systems 34(6) (2018), 4041–4056.

18.

Wang

, Laili

and Zhang

, A many-objective memetic algorithm for correlation-aware service composition in cloud manufacturing, International Journal of Production Research (2020) (early access). DOI: 10.1080/00207543.2020.1774678.

19.

Hosseinabadi

A.A.

, Vahidi

, Saemi

, Sangaiah

A.K.

and Elhoseny

, Extended genetic algorithm for solving open-shop scheduling problem, Soft Computing 23(13) (2019), 5099–5116.

20.

Cai

, Zhou

and Lei

, Fuzzy distributed two-stage hybrid flow shop scheduling problem with setup time: collaborative variable search, Journal of Intelligent & Fuzzy Systems 38(3) (2020), 3189–3199.

21.

Sawik

, Coordinated supply chain scheduling, International Journal of Production Economics 120(2) (2009), 437–451.

22.

Laili

, Zhang

and Tao

, Energy adaptive immune genetic algorithm for collaborative design task scheduling in cloud manufacturing system, In proceeding of 2011 IEEE International Conference on Industrial Engineering and Engineering Management, IEEE, Singapore, December 06–09, 2011.

23.

Lin

Y.K.

and Chong

C.S.

, Fast GA-based project scheduling for computing resources allocation in a cloud manufacturing system, Journal of Intelligent Manufacturing 28(5) (2017), 1189–1201.

24.

Zhou

L.F.

, Zhang

, Sarker

B.R.

, Laili

and Ren

, An event-triggered dynamic scheduling method for randomly arriving tasks in cloud manufacturing, International Journal of Computer Integrated Manufacturing 31(3) (2018), 318–333.

25.

Jian

C.F.

and Wang

, Batch task scheduling-oriented optimization modelling and simulation in cloud manufacturing, International Journal of Simulation Modelling 13(1) (2014), 93–101.

26.

W.X.

, Zhu

C.S.

, Yang

L.T.

, Lei

, Ngai

E.C.H.

and Ma

Y.J.

, Subtask scheduling for distributed robots in cloud manufacturing, IEEE Systems Journal 11(2) (2015), 941–950.

27.

Jiang

, Yi

J.J.

, Chen

S.L.

and Zhu

X.M.

, A multi-objective algorithm for task scheduling and resource allocation in cloud-based disassembly, Journal of Manufacturing Systems 41 (2016), 239–255.

28.

Ghomi

E.J.

, Rahmani

A.M.

and Qader

N.N.

, Service load balancing, scheduling, and logistics optimization in cloud manufacturing by using genetic algorithm, Concurrency and Computation Practice and Experience 31(2) (2019), e5329.

29.

, Liao

T.W.

and Zhang

, Two-level multi-task scheduling in a cloud manufacturing environment, Robotics and Computer-Integrated Manufacturing 56 (2019), 127–139.

30.

Laili

, Lin

and Tang

, Multi-phase integrated scheduling of hybrid tasks in cloud manufacturing environment, Robotics and Computer-Integrated Manufacturing 61 (2020), 101850.

31.

Cao

, Wang

, Kang

and Gao

, A TQCS-based service selection and scheduling strategy in cloud manufacturing, The International Journal of Advanced Manufacturing Technology 82(1–4) (2016), 235–251.

32.

Cheng

, Zhan

, Zhao

and Wan

, Multitask oriented virtual resource integration and optimal scheduling in cloud manufacturing, Journal of Applied Mathematics (2014), 369350.

33.

Yuan

, Deng

, Chaovalitwongse

W.A.

and Cheng

, Multi-objective optimal scheduling of reconfigurable assembly line for cloud manufacturing, Optimization Methods and Software 32(3) (2017), 581–593.

34.

Cowling

and Johansson

, Using real time information for effective dynamic scheduling, European Journal of Operational Research 139(2) (2002), 230–244.

35.

Nouiri

, Bekrar

, Jemai

, Trentesaux

, Ammari

A.C.

and Niar

, Two stage particle swarm optimization to solve the flexible job shop predictive scheduling problem considering possible machine breakdowns, Computers & Industrial Engineering 112 (2017), 595–606.

36.

Ivanov

and Sokolov

, Dynamic supply chain scheduling, Journal of Scheduling 15(2) (2012), 201–216.

37.

Wang

, Guo

S.S.

, Du

B.G.

, Li

X.X.

and Wu

, Rescheduling strategy of cloud service based on shuffled frog leading algorithm and Nash equilibrium, The International Journal of Advanced Manufacturing Technology 94(9) (2018), 3519–3535.

38.

Zeng

L.Z.

, Benatallah

, Ngu

A.H.

, Dumas

, Kalagnanam

and Chang

, QoS-aware middleware for web services composition, IEEE Transactions on Software Engineering 30(5) (2004), 311–327.

39.

Zhou

L.F.

, Zhang

, Zhao

, Laili

and Xu

L.D.

, Diverse task scheduling for individualized requirements in cloud manufacturing, Enterprise Information Systems 12(3) (2018), 300–318.

40.

Tao

, Zhao

D.M.

, Hu

Y.F.

and Zhou

Z.D.

, Resource service composition and its optimal-selection based on particle swarm optimization in manufacturing grid system, IEEE Transactions on Industrial Informatics 4(4) (2008), 315–327.

41.

Bouzary

and Chen

F.F.

, A hybrid grey wolf optimizer algorithm with evolutionary operators for optimal QoS-aware service composition and optimal selection in cloud manufacturing, The International Journal of Advanced Manufacturing Technology 101(9) (2019), 2771–2784.

42.

Zhang

, Yang

W.T.

, Zhang

W.Y.

and Chen

M.Z.

, A collaborative service group-based fuzzy QoS-aware manufacturing service composition using an extended flower pollination algorithm, Nonlinear Dynamics 95(4) (2019), 3091–3114.

43.

Zhang

, Xiao

, Zhang

, Lin

and Feng

, A utility-aware multi-task scheduling method in cloud manufacturing using extended NSGA-II embedded with game theory, International Journal of Computer Integrated Manufacturing (2021) (early access). DOI: 10.1080/0951192X.2020.1858502.

44.

Garg

, An efficient biogeography based optimization algorithm for solving reliability optimization problems, Swarm and Evolutionary Computation 24 (2015), 1–10.

45.

Zhang

, Kang

, Tu

, Cheng

and Wang

, Efficient and merged biogeography-based optimization algorithm for global optimization problems, Soft Computing 23(12) (2019), 4483–4502.

46.

Kim

S.S.

, Byeon

J.H.

, Yu

and Liu

, Biogeography-based optimization for optimal job scheduling in cloud computing, Applied Mathematics and Computation 247 (2014), 266–280.

47.

Paslar

, Ariffin

M.K.A.

, Tamjidy

and Hong

T.S.

, Biogeography-based optimisation for flexible manufacturing system scheduling problem, International Journal of Production Research 53(9) (2015), 2690–2706.

48.

Yang

G.Q.

, Liu

Y.K.

and Yang

, Multi-objective biogeography-based optimization for supply chain network design under uncertainty, Computers & Industrial Engineering 85 (2015), 145–156.

49.

Rifai

A.P.

, Nguyen

H.T.

, Aoyama

, Dawal

S.Z.M.

and Masruroh

N.A.

, Non-dominated sorting biogeography-based optimization for bi-objective reentrant flexible manufacturing system scheduling, Applied Soft Computing 62 (2018), 187–202.

50.

, Tian

, Liu

, Xie

, Zhou

and Pham

D.T.

, An improved discrete bees algorithm for correlation-aware service aggregation optimization in cloud manufacturing, The International Journal of Advanced Manufacturing Technology 84(1–4) (2016), 17–28.

51.

Fogel

D.B.

, An introduction to simulated evolutionary optimization, IEEE Transactions on Neural Networks 5(1) (1994), 3–14.

52.

Zhang

, Dai

, Zhang

, Wang

and Liu

, A new energy-aware flexible job shop scheduling method using modified biogeography-based optimization, Mathematical Problems in Engineering (2017), 7249876.