# PACAM: A Pairwise-Allocated Strategy and Capability Average Matrix-Based Task Scheduling Approach for Edge Computing

Authors: Feng Hong; Tianming Zhang; Bin Cao; Jing Fan
Journal: Security and Communication Networks
 (2022)

---

## Abstract

With the development of the smart Internet of Things (IoT), an increasing number of tasks are deployed on the edge of the network. Considering the substantially limited processing capability of IoT devices, task scheduling as an effective solution offers low latency and flexible computation to improve the system performance and increase the quality of services. However, limited computing resources make it challenging to assign the right tasks to the right devices at the edge of the network. To this end, we propose a polynomial-time solution, which consists of three steps, i.e., identifying available devices, estimating device quantity, and searching for feasible schedules. In order to shrink the number of potential schedules, we present a pairwise-allocated strategy (PA). Based on these, a capability average matrix (CAM)-based index is designed to further boost efficiency. In addition, we evaluate the schedules by the technique for order preference by similarity to an ideal solution (TOPSIS). Extensive experimental evaluation using both real and synthetic datasets demonstrates the efficiency and effectiveness of our proposed approach.


---

## Body

## 1. Introduction

As an essential function, task scheduling of edge computing has widespread applications in various domains such as the Internet of vehicle [1], transportation [2], health emergency [3], and smart homes [4]. With the development of the smart Internet of Things (IoT) [5–7], an increasing number of tasks deployed on the edge of the network and the IoT devices require to process the heavy tasks with finite response time. Considering the substantially limited processing capability, how to assign tasks to these devices is a significant issue to improve the performance of the system and increase the quality of services. In the following, we give a representative example.


### 1.1. Motivation Example

(Internet of vehicle) Unmanned aerial vehicles (UAVs) are one type of new IoT devices that are usually used for surveying and mapping services. The number of tasks containing surveying and mapping is large, and if most tasks are assigned to a small part of UAVs, this causes these UAVs to require much time to process tasks and other UAVs do a few tasks, even none. The time cost of services depends on the time point of finishing the last task, and such assignment making not full use of devices results in a longer response time of finishing a service. In addition, considering limited capability, UAVs are unable to execute the heavy tasks, which results in low quality of services since a few tasks are not finished. Given these limitations, an effective and efficient task scheduling helps to assign the right tasks to the right UAVs and reduce the time cost of finishing services on the premise of guaranteeing the quality of services.In past years, important research focused on the mathematically strict scheduling models and effective techniques for task scheduling problems of edge computing [8–10]. Few works consider the optimization goals in aspects of fairness; that is, most works consider the global result of each optimization goal in the whole schedule while ignoring its changing local results [11]. Besides, it is well known that task scheduling is an NP-hard problem [12]. Some existing works adopted mathematical programming, such as mixed-Integer programming (MIP [13–17]). Each of them ordinarily adopts the solvers to generate the feasible schedules, and this process requires prohibitive computations to be supported.In addition, there are many similar studies on task scheduling problems of edge computing [17–18], and they may suffer from one or more of the following drawbacks:(1)
Most of the studies model their problems and adopt a series of pruning techniques to shrink the number of potential schedules, such as substituting the precise solutions with approximate ones. Although this way can reduce a part of the computation burden, it remains to be time-consuming.(2)
The task scheduling problems usually involve more than one optimization goal, and the potential conflicts between objectives may exist; i.e., the improvement of one goal may lead to the performance degradation of another. Many studies convert multiple goals to one single objective by empirically using different weights over different goals. However, too much domain knowledge is needed in this way and the generated schedule may fail if the weights are changed.In our defined task scheduling problem, two categories of constraints are defined. (1) Hard constraint: we consider two hard constraints; i.e.,each device is assigned to at most one task per service and each device works at mostkconsecutive services. Any one of them is broken will lead to the invalidity of the schedule. (2) Soft constraint: that is, the total capabilities of the assigned devices for each type of task are equal to its workload, which should be maximally satisfied. To effectively evaluate the quality of a schedule, we define two optimization goals, i.e., the average coverage Ave_Coverage and the fairness of coverage Coverage_Fairness, where Ave_Coverage computes the coverage ratio of the whole schedule and Coverage_Fairness is utilized to measure that all the coverage ratios in the schedule get close to 1. The closer Ave_Coverage is to 1 and the smaller Coverage_Fairness is, the higher the quality of the schedule will be.Based on these, we propose a pairwise-allocated strategy and capability average matrix-based approach (PACAM), which is a polynomial solution. To be more specific, PACAM consists of three steps, i.e., identifying available devices, estimating device quantity, and searching for a feasible schedule. In the first step, for each device, PACAM checks whether it is available for tasks according to hard constraints. If one device broke any one of the hard constraints on one service, it will be identified to be unavailable and cannot be assigned to tasks on this service. Next, we need to assign them to tasks. When assigning available devices to tasks directly, we will face a large number of potential different device combinations, which contain plenty of obviously unfeasible device combinations; e.g., all the devices are assigned to the same type of tasks. Hence, in the second step, PACAM preestimates the number of devices for each type of task by the workload for each type of task and the average capability of devices. Then, in the third step, PACAM assigns the corresponding estimated number of devices to each type of task, which effectively reduces the potential device combinations by pruning obviously unfeasible device combinations in advance.However, evaluating each device combination for searching for the feasible schedule after the pruning technique still requires a great amount of computational consumption; thus, PACAM proposes the pairwise-allocated strategy (PA) to solve this problem. PA treats two devices as a device group and assigns device groups to the corresponding task according to their average capability. Note that the number of devices in these device groups for each task is equal to its estimated number. The reason is that the estimated number of devices for each task is computed by the workload of each task and average capability of devices, the closer the average capability of these device groups is to that of all the devices, the smaller the difference between the total capabilities of these device groups and the workload of the corresponding tasks is. To boost its efficiency, PACAM proposes the capability average matrix (CAM). Besides, PACAM introduces the technique for order preference by similarity to an ideal solution (TOPSIS, [19]) as the evaluation metric. The reason why we use TOPSIS is that it is a multicriteria decision analysis method [20] and is widely used in evaluating a solution with different dimensions. TOPSIS provides enough information for PACAM to generate a wise feasible schedule.We experimentally evaluate PACAM using a variety of real and synthetic datasets coming from China Telecom company. The real part of datasets contains daily call arrivals for six months of 2020, and the synthetic part is the devices and their capabilities in the corresponding months. We demonstrate the effectiveness and efficiency of PACAM on these datasets. It only takes a few minutes to search for a feasible schedule. In general, the contributions in this article are summarized as follows:(1)
We propose a polynomial-time solution to efficiently handle task scheduling problems.(2)
We present PACAM, where a pairwise-allocated (PA) strategy is proposed to shrink the number of potential device combinations and a CAM index is designed to boost efficiency further.(3)
We first introduce the TOPSIS to effectively evaluate the potential schedules and decide the final feasible schedule.(4)
Using real-life data (daily call arrivals in 6 months of 2020) and synthetic data (capabilities of devices), we experimentally verify the effectiveness and efficiency of our proposed method. Compared with five state-of-the-art methods for task scheduling, i.e., linear programming (LP [21]), integer programming (IP [22]), MIP [16]), improved particle swarm optimization (IPSO [23]), and multiobjective evolutionary algorithm-based decomposition (MOEAD [24]), we find that PACAM is at least two orders of magnitude faster than the above methods.The rest of this article is organized as follows. Section2 introduces several concepts and optimization goals and defines the problem formally. Section 3 elaborates a polynomial-time solution for task scheduling. Experimental results and our findings are reported in Section 4. Section 5 reviews related work. Finally, Section 6 concludes the article with some directions for future work.


## 1.1. Motivation Example

(Internet of vehicle) Unmanned aerial vehicles (UAVs) are one type of new IoT devices that are usually used for surveying and mapping services. The number of tasks containing surveying and mapping is large, and if most tasks are assigned to a small part of UAVs, this causes these UAVs to require much time to process tasks and other UAVs do a few tasks, even none. The time cost of services depends on the time point of finishing the last task, and such assignment making not full use of devices results in a longer response time of finishing a service. In addition, considering limited capability, UAVs are unable to execute the heavy tasks, which results in low quality of services since a few tasks are not finished. Given these limitations, an effective and efficient task scheduling helps to assign the right tasks to the right UAVs and reduce the time cost of finishing services on the premise of guaranteeing the quality of services.In past years, important research focused on the mathematically strict scheduling models and effective techniques for task scheduling problems of edge computing [8–10]. Few works consider the optimization goals in aspects of fairness; that is, most works consider the global result of each optimization goal in the whole schedule while ignoring its changing local results [11]. Besides, it is well known that task scheduling is an NP-hard problem [12]. Some existing works adopted mathematical programming, such as mixed-Integer programming (MIP [13–17]). Each of them ordinarily adopts the solvers to generate the feasible schedules, and this process requires prohibitive computations to be supported.In addition, there are many similar studies on task scheduling problems of edge computing [17–18], and they may suffer from one or more of the following drawbacks:(1)
Most of the studies model their problems and adopt a series of pruning techniques to shrink the number of potential schedules, such as substituting the precise solutions with approximate ones. Although this way can reduce a part of the computation burden, it remains to be time-consuming.(2)
The task scheduling problems usually involve more than one optimization goal, and the potential conflicts between objectives may exist; i.e., the improvement of one goal may lead to the performance degradation of another. Many studies convert multiple goals to one single objective by empirically using different weights over different goals. However, too much domain knowledge is needed in this way and the generated schedule may fail if the weights are changed.In our defined task scheduling problem, two categories of constraints are defined. (1) Hard constraint: we consider two hard constraints; i.e.,each device is assigned to at most one task per service and each device works at mostkconsecutive services. Any one of them is broken will lead to the invalidity of the schedule. (2) Soft constraint: that is, the total capabilities of the assigned devices for each type of task are equal to its workload, which should be maximally satisfied. To effectively evaluate the quality of a schedule, we define two optimization goals, i.e., the average coverage Ave_Coverage and the fairness of coverage Coverage_Fairness, where Ave_Coverage computes the coverage ratio of the whole schedule and Coverage_Fairness is utilized to measure that all the coverage ratios in the schedule get close to 1. The closer Ave_Coverage is to 1 and the smaller Coverage_Fairness is, the higher the quality of the schedule will be.Based on these, we propose a pairwise-allocated strategy and capability average matrix-based approach (PACAM), which is a polynomial solution. To be more specific, PACAM consists of three steps, i.e., identifying available devices, estimating device quantity, and searching for a feasible schedule. In the first step, for each device, PACAM checks whether it is available for tasks according to hard constraints. If one device broke any one of the hard constraints on one service, it will be identified to be unavailable and cannot be assigned to tasks on this service. Next, we need to assign them to tasks. When assigning available devices to tasks directly, we will face a large number of potential different device combinations, which contain plenty of obviously unfeasible device combinations; e.g., all the devices are assigned to the same type of tasks. Hence, in the second step, PACAM preestimates the number of devices for each type of task by the workload for each type of task and the average capability of devices. Then, in the third step, PACAM assigns the corresponding estimated number of devices to each type of task, which effectively reduces the potential device combinations by pruning obviously unfeasible device combinations in advance.However, evaluating each device combination for searching for the feasible schedule after the pruning technique still requires a great amount of computational consumption; thus, PACAM proposes the pairwise-allocated strategy (PA) to solve this problem. PA treats two devices as a device group and assigns device groups to the corresponding task according to their average capability. Note that the number of devices in these device groups for each task is equal to its estimated number. The reason is that the estimated number of devices for each task is computed by the workload of each task and average capability of devices, the closer the average capability of these device groups is to that of all the devices, the smaller the difference between the total capabilities of these device groups and the workload of the corresponding tasks is. To boost its efficiency, PACAM proposes the capability average matrix (CAM). Besides, PACAM introduces the technique for order preference by similarity to an ideal solution (TOPSIS, [19]) as the evaluation metric. The reason why we use TOPSIS is that it is a multicriteria decision analysis method [20] and is widely used in evaluating a solution with different dimensions. TOPSIS provides enough information for PACAM to generate a wise feasible schedule.We experimentally evaluate PACAM using a variety of real and synthetic datasets coming from China Telecom company. The real part of datasets contains daily call arrivals for six months of 2020, and the synthetic part is the devices and their capabilities in the corresponding months. We demonstrate the effectiveness and efficiency of PACAM on these datasets. It only takes a few minutes to search for a feasible schedule. In general, the contributions in this article are summarized as follows:(1)
We propose a polynomial-time solution to efficiently handle task scheduling problems.(2)
We present PACAM, where a pairwise-allocated (PA) strategy is proposed to shrink the number of potential device combinations and a CAM index is designed to boost efficiency further.(3)
We first introduce the TOPSIS to effectively evaluate the potential schedules and decide the final feasible schedule.(4)
Using real-life data (daily call arrivals in 6 months of 2020) and synthetic data (capabilities of devices), we experimentally verify the effectiveness and efficiency of our proposed method. Compared with five state-of-the-art methods for task scheduling, i.e., linear programming (LP [21]), integer programming (IP [22]), MIP [16]), improved particle swarm optimization (IPSO [23]), and multiobjective evolutionary algorithm-based decomposition (MOEAD [24]), we find that PACAM is at least two orders of magnitude faster than the above methods.The rest of this article is organized as follows. Section2 introduces several concepts and optimization goals and defines the problem formally. Section 3 elaborates a polynomial-time solution for task scheduling. Experimental results and our findings are reported in Section 4. Section 5 reviews related work. Finally, Section 6 concludes the article with some directions for future work.


## 2. Preliminaries

In this section, first, we present a series of basic concepts, i.e., scheduling horizon, devices, and scheduling constraints. Then, we introduce two optimization goals. Finally, we define the task scheduling problem. For ease of reference, Table1 summarizes the notations used frequently in this article.Table 1
Symbols and description.
AnnotationDescriptionS = {s1,s2,…,sn}A scheduling horizon ofn servicesDTi or NTiThe day or night tasks of the servicesiWDi or WNiThe workload of the day taskDTi or the night task NTiD  = {d1,d2,…,dm}A set ofm devicesC = {c1,c2,…,cm}The capabilities set ofm devicesHard1, Hard2The hard constraintsSoft1The soft constraintac_DTi / ac_NtiThe total capabilities of devices assigned to the day taskDTi or the night task NTitotal_ACThe total number of capabilities of available deviceskThe maximal number of consecutive servicesavailable_DThe set of devices that can be assigned to tasks(task_si−k+1,…,task_si)The previousk tasks of sinumber_DTi/number_NTiThe estimated number of devices for the day/night task ofsitotalac_siThe total quantity of capabilities that can be assigned to tasks ofsiDC_DTi/DC_NTiThe device combinations for the day and night tasks ofsi


### 2.1. Basic Concepts

We start with notations of each basic concept.


#### 2.1.1. Scheduling Horizon

A scheduling horizon is defined asS = {s1,s2,…,sn}, where si∈S represents a service. Each service si has two types of tasks, i.e., day task and night task, denoted as DTi and NTi, respectively. In addition, each type of task for si has a corresponding workload. Specifically, the workloads of the day task DTi and night task NTi are represented as WDi and WNi, respectively.


#### 2.1.2. Devices

Devices are defined asD = {d1,d2,…,dm}, where each device dj∈D has a capability cj. After devices are assigned to tasks, the total capabilities of the devices assigned to the day task DTi and the night task NTi are denoted as totalc_DTi and totalc_NTi, respectively.It is worth noting that the workload corresponds to the device’s capabilities. For example, a device whose capability is 2 is assigned to the day task, which means that the workload of this task this device finishes is 2.


#### 2.1.3. Scheduling Constraints

When assigning devices to tasks, constraints such as devices’ maintenance, business rules, and regulations are considered. They are divided into two types, i.e., hard constraints that can not be violated and soft constraint that should be maximally satisfied.In this article, we mainly consider two hard constraints and one soft constraint. Specifically, hard constraints include the following:(1)
Hard1, each device is assigned to at most one type of tasks per service.(2)
Hard2, each device works at most k consecutive services.The soft constraint is as follows:(1)
Soft1, the total capabilities of the assigned devices for each type of task are equal to its workload.


### 2.2. Optimization Goals

Following the principle that soft constraints should be maximally satisfied, we proposed two optimization goals:average workload coverage and coverage fairness.


#### 2.2.1. Average Workload Coverage

A feasible assignment should follow that the total capabilities of the assigned devices maximally satisfy the workloads of tasks. Hence, we defineAve_Coverage to compute the coverage ratio of the whole schedule.Given a scheduling horizonS = {s1,s2,…,sn} and a set of devices D = {d1,d2,…,dm}, devices are assigned to the day and night tasks, the Ave_Coverage is computed by(1)Ave_Coverage=12n×∑i=1nac_DTiWDi+ac_NTiWNi.Example 1.
The workload of the three services is listed in Table2 and the total capabilities for each type of task of each service are shown in Table 3. To compute Ave_Coverage, thus, according to equation (1), Ave_Coverage =  1/6×2.2/2.2+1.1/1.0+1.2/0.8+2.3/4.6+2.3/2.3+2.3/2.3 = 1.02.
Note thatAve_Coverage is used to compute the total average coverage ratio of the whole schedule, but the coverage ratios of some types of tasks are not close to 1; e.g., the coverage ratios of DT2 and NT2 are 1.5 and 0.5, which violate Soft1. Hence, we adopt Coverage_Fairness to ensure that the coverage ratio gets close to 1.Table 2
The workload for each type of task of each service.
HorizonWDiWNis12.21.0s20.84.6s32.32.3Table 3
The assigned capability of each type of task.
HorizonTotal assigned capabilityac_DTiac_NTis12.21.1s21.22.3s32.32.3


#### 2.2.2. Coverage Fairness

Given a scheduling horizonS = {s1,s2,…,sn} and a set of devices D = {d1,d2,…,dm}, the Coverage_Fairness is defined as follows:(2)Coverage_Fairness=12n×∑i=1nac_DTiWDi−Ave_Coverage2+ac_NTiWNi−Ave_Coverage21/2.Consider Example1, according to equation (2), Coverage_Fairness =  1/6×1−1.022+1.1−1.022+1.5−1.022+0.5−1.022+1−1.022+1−1.0221/2= 0.289.


### 2.3. Problem Definition

Based on the above concepts, we define the problem formally.


#### 2.3.1. Task Scheduling Problem

Given a scheduling horizonS = {s1,s2,…sn} and a set of devices D = {d1,d2,…,dm}, the task scheduling aims to assign the devices in D to the tasks of services in S, such that(1)
hard constrainsHard1 and Hard2 must be satisfied(2)
| 1-Ave_Coverage| is minimized(3)
the value ofCoverage_Fairness is minimized


## 2.1. Basic Concepts

We start with notations of each basic concept.


### 2.1.1. Scheduling Horizon

A scheduling horizon is defined asS = {s1,s2,…,sn}, where si∈S represents a service. Each service si has two types of tasks, i.e., day task and night task, denoted as DTi and NTi, respectively. In addition, each type of task for si has a corresponding workload. Specifically, the workloads of the day task DTi and night task NTi are represented as WDi and WNi, respectively.


### 2.1.2. Devices

Devices are defined asD = {d1,d2,…,dm}, where each device dj∈D has a capability cj. After devices are assigned to tasks, the total capabilities of the devices assigned to the day task DTi and the night task NTi are denoted as totalc_DTi and totalc_NTi, respectively.It is worth noting that the workload corresponds to the device’s capabilities. For example, a device whose capability is 2 is assigned to the day task, which means that the workload of this task this device finishes is 2.


### 2.1.3. Scheduling Constraints

When assigning devices to tasks, constraints such as devices’ maintenance, business rules, and regulations are considered. They are divided into two types, i.e., hard constraints that can not be violated and soft constraint that should be maximally satisfied.In this article, we mainly consider two hard constraints and one soft constraint. Specifically, hard constraints include the following:(1)
Hard1, each device is assigned to at most one type of tasks per service.(2)
Hard2, each device works at most k consecutive services.The soft constraint is as follows:(1)
Soft1, the total capabilities of the assigned devices for each type of task are equal to its workload.


## 2.1.1. Scheduling Horizon

A scheduling horizon is defined asS = {s1,s2,…,sn}, where si∈S represents a service. Each service si has two types of tasks, i.e., day task and night task, denoted as DTi and NTi, respectively. In addition, each type of task for si has a corresponding workload. Specifically, the workloads of the day task DTi and night task NTi are represented as WDi and WNi, respectively.


## 2.1.2. Devices

Devices are defined asD = {d1,d2,…,dm}, where each device dj∈D has a capability cj. After devices are assigned to tasks, the total capabilities of the devices assigned to the day task DTi and the night task NTi are denoted as totalc_DTi and totalc_NTi, respectively.It is worth noting that the workload corresponds to the device’s capabilities. For example, a device whose capability is 2 is assigned to the day task, which means that the workload of this task this device finishes is 2.


## 2.1.3. Scheduling Constraints

When assigning devices to tasks, constraints such as devices’ maintenance, business rules, and regulations are considered. They are divided into two types, i.e., hard constraints that can not be violated and soft constraint that should be maximally satisfied.In this article, we mainly consider two hard constraints and one soft constraint. Specifically, hard constraints include the following:(1)
Hard1, each device is assigned to at most one type of tasks per service.(2)
Hard2, each device works at most k consecutive services.The soft constraint is as follows:(1)
Soft1, the total capabilities of the assigned devices for each type of task are equal to its workload.


## 2.2. Optimization Goals

Following the principle that soft constraints should be maximally satisfied, we proposed two optimization goals:average workload coverage and coverage fairness.


### 2.2.1. Average Workload Coverage

A feasible assignment should follow that the total capabilities of the assigned devices maximally satisfy the workloads of tasks. Hence, we defineAve_Coverage to compute the coverage ratio of the whole schedule.Given a scheduling horizonS = {s1,s2,…,sn} and a set of devices D = {d1,d2,…,dm}, devices are assigned to the day and night tasks, the Ave_Coverage is computed by(1)Ave_Coverage=12n×∑i=1nac_DTiWDi+ac_NTiWNi.Example 1.
The workload of the three services is listed in Table2 and the total capabilities for each type of task of each service are shown in Table 3. To compute Ave_Coverage, thus, according to equation (1), Ave_Coverage =  1/6×2.2/2.2+1.1/1.0+1.2/0.8+2.3/4.6+2.3/2.3+2.3/2.3 = 1.02.
Note thatAve_Coverage is used to compute the total average coverage ratio of the whole schedule, but the coverage ratios of some types of tasks are not close to 1; e.g., the coverage ratios of DT2 and NT2 are 1.5 and 0.5, which violate Soft1. Hence, we adopt Coverage_Fairness to ensure that the coverage ratio gets close to 1.Table 2
The workload for each type of task of each service.
HorizonWDiWNis12.21.0s20.84.6s32.32.3Table 3
The assigned capability of each type of task.
HorizonTotal assigned capabilityac_DTiac_NTis12.21.1s21.22.3s32.32.3


### 2.2.2. Coverage Fairness

Given a scheduling horizonS = {s1,s2,…,sn} and a set of devices D = {d1,d2,…,dm}, the Coverage_Fairness is defined as follows:(2)Coverage_Fairness=12n×∑i=1nac_DTiWDi−Ave_Coverage2+ac_NTiWNi−Ave_Coverage21/2.Consider Example1, according to equation (2), Coverage_Fairness =  1/6×1−1.022+1.1−1.022+1.5−1.022+0.5−1.022+1−1.022+1−1.0221/2= 0.289.


## 2.2.1. Average Workload Coverage

A feasible assignment should follow that the total capabilities of the assigned devices maximally satisfy the workloads of tasks. Hence, we defineAve_Coverage to compute the coverage ratio of the whole schedule.Given a scheduling horizonS = {s1,s2,…,sn} and a set of devices D = {d1,d2,…,dm}, devices are assigned to the day and night tasks, the Ave_Coverage is computed by(1)Ave_Coverage=12n×∑i=1nac_DTiWDi+ac_NTiWNi.Example 1.
The workload of the three services is listed in Table2 and the total capabilities for each type of task of each service are shown in Table 3. To compute Ave_Coverage, thus, according to equation (1), Ave_Coverage =  1/6×2.2/2.2+1.1/1.0+1.2/0.8+2.3/4.6+2.3/2.3+2.3/2.3 = 1.02.
Note thatAve_Coverage is used to compute the total average coverage ratio of the whole schedule, but the coverage ratios of some types of tasks are not close to 1; e.g., the coverage ratios of DT2 and NT2 are 1.5 and 0.5, which violate Soft1. Hence, we adopt Coverage_Fairness to ensure that the coverage ratio gets close to 1.Table 2
The workload for each type of task of each service.
HorizonWDiWNis12.21.0s20.84.6s32.32.3Table 3
The assigned capability of each type of task.
HorizonTotal assigned capabilityac_DTiac_NTis12.21.1s21.22.3s32.32.3


## 2.2.2. Coverage Fairness

Given a scheduling horizonS = {s1,s2,…,sn} and a set of devices D = {d1,d2,…,dm}, the Coverage_Fairness is defined as follows:(2)Coverage_Fairness=12n×∑i=1nac_DTiWDi−Ave_Coverage2+ac_NTiWNi−Ave_Coverage21/2.Consider Example1, according to equation (2), Coverage_Fairness =  1/6×1−1.022+1.1−1.022+1.5−1.022+0.5−1.022+1−1.022+1−1.0221/2= 0.289.


## 2.3. Problem Definition

Based on the above concepts, we define the problem formally.


### 2.3.1. Task Scheduling Problem

Given a scheduling horizonS = {s1,s2,…sn} and a set of devices D = {d1,d2,…,dm}, the task scheduling aims to assign the devices in D to the tasks of services in S, such that(1)
hard constrainsHard1 and Hard2 must be satisfied(2)
| 1-Ave_Coverage| is minimized(3)
the value ofCoverage_Fairness is minimized


## 2.3.1. Task Scheduling Problem

Given a scheduling horizonS = {s1,s2,…sn} and a set of devices D = {d1,d2,…,dm}, the task scheduling aims to assign the devices in D to the tasks of services in S, such that(1)
hard constrainsHard1 and Hard2 must be satisfied(2)
| 1-Ave_Coverage| is minimized(3)
the value ofCoverage_Fairness is minimized


## 3. Algorithm

A naive way to find the optimal schedule is to first enumerate all the possible device combinations and then choose the best one that minimizes the values of|1−Ave_Coverage| and Coverage_Fairness. However, it is computationally intractable because the number of possible device combinations is exponential (i.e., |S|×2D), where S and D are cardinalities of the scheduling horizon S and the set D of device. To reduce the asymptotic complexity of device scheduling, we design a PA strategy that dramatically shrinks the number of potential device combinations and defines a CAM index to boost efficiency. Based on these, a polynomial-time solution is proposed. The pseudocode is shown in Algorithm 1.Algorithm 1: The overview of PACAM.
Input: The set of devices D; the workload WDi and WNi; the maximal consecutive services kOutput: The feasible schedule fs(1)
foreach servicesiinSdo(2)
available_D←identify_device (D, k, si)(3)
number_DTi←estimate_quantity (WDi, available_D)(4)
number_NTi←estimate_quantity (WNi, available_D)(5)
fs←search_schedule (WDi, WNi, number_DTi, number_NTi)(6)
ReturnfsSpecifically, we arrange the tasks by services (line 1); each service is composed of three procedures, namely, identifying available devicesidentify_device() (line 2), estimating device quantity estimate_quantity (lines 3-4), and searching for feasible schedule search_schedule (line 5). Device (D) will be input into identify_device() to generate a set of available devices (available_D). Then, available_E and the workload of each type of task will be computed by estimate_quantity() to estimate the number of devices for each type of task of the service si (the estimated quantity of devices for day/night tasks number_DTi/number_NTi). Next, search_schedule generates the feasible schedule according to the workload for each type of task of the service si (the workload of day/night task WDi/WNi) and the estimated quantity of devices for each type of task. In the following, we detail these three key procedures.


### 3.1. Identifying Available Device

For the servicesi (k≤i<n), not all the devices can be assigned to the tasks of si, since the hard constraint Hard2 rules that the maximal number of consecutive services cannot exceed k services for a device. Hence, for each device, the procedure identify_device() checks whether there is a Rest-status in its tasks of the previous k services (i.e., si−k+1,si−k+2,…,sk). If the answer is yes, the device is identified to be available for si. As for the service si (0<i<k), all devices are identified to be available, since even if the device dj is assigned to tasks during the previous i services, the maximal consecutive services of dj for si cannot be exceed k services.Next, we give an example to show how we identify available devices, combined with the procedure ofidentify_device(), which is presented in Algorithm 2.Algorithm 2: identify_device (D, k, si).
Input: The set of device D; the maximal consecutive services k; the ith service siOutput: The set of available devices available_Dsi)(1)
for each service si (k<i<n) do(2)
for each device dj in Ddo(3)
(task_si−k+1,task_si−k+2,…,task_sk) ← get tasks of the previous k services for dj;(4)
if (task_si−k+1,task_si−k+2,…,task_sk) contains a Rest-status then(5)
putdj into avaiable_D;(6)
for each service si (0<i≤k) do(7)
for each device djdo(8)
putdj into avaiable_D;(9)
Returnavailable_DExample 2.
Consider a scheduling example as shown in Table4, where there are 7 devices and all of them have been assigned to tasks of s1 and s2, suppose that the maximal number of consecutive services k is set to 2; now we need to identify the availability of devices for the service s3. From Table 4, since the service s3 (k<3<n, k=2), we get tasks of the previous 2 services for each device (line 3), then we traverse the tasks of each device to check for whether they contain a Rest-status (line 4). In this example, the tasks of the devices d1,d2,d3,d4,d5 contain a Rest-status and the others are not. The device with the tasks containing a Rest-status will be identified to be available and be stored in the set of available devices available_D (line 5). Thus, the devices d1,d2,d3,d4,d5 will be put into available_D, and the devices d6,d7 are identified to be unavailable for the service s3. As for the service si (0<i≤k, k=2), each device is available and will be stored in available_D (lines 6–8).Table 4
The assigned capability of each type of task.
DeviceServices1Services2Services3d1Day taskRest-statusAvailabled2Night taskRest-statusAvailabled3Rest-statusDay taskAvailabled4Rest-statusDay taskAvailabled5Rest-statusRest-statusAvailabled6Day taskNight taskUnavailabled7Night taskDay taskUnavailable


### 3.2. Estimating Device Quantity

After the available device ofsi is identified, we need to assign them to the tasks of si. To avoid enumerating the exponential device combinations, we invoke the procedure estimate_quantity() (as Algorithm 3 shows) to estimate the number of devices required for each type of task in advance. Specifically, Algorithm 3 takes the set of available devices and the workload of each type of task of si as inputs, and the output is the estimated quantity of available devices required for each type of task of si.First, according to the available device set, we compute their total capabilitytotal_AC and average capability average_AC (lines 1-2). Based on this, we estimate the number of devices required for each type of task. To avoid the understaffing/overstaffing problem, we need to confirm the total quantity of available capability totalac_si by the following equation:(3)totalac_si=total_AC,total_AC<WDi+WNi,WDi+WNi,total_AC≥WDi+WNi,where totalac_si is the total quantity of capabilities that can be assigned to tasks of si, total_AC denotes the total number of capabilities of all available devices of si, and WDi/WNi represents the workload of the day/night task of si. If total_AC<WDi+WNi, we assign all available devices to tasks and totalac_si = total_AC (lines 3 and 4). Otherwise, part of available devices will be assigned to tasks and totalac_siWDi+WNi (lines 5 and 6).Then based on the ratio of the workload of each task to that of all tasks, we compute the estimated quantity of each type of task, shown in the following equation (lines 7-8):(4)ac_DTi=totalac_si×WDiWDi+WNi,ac_NTi=totalac_si×WNiWDi+WNi,where ac_DTi and ac_NTi are the number of capabilities that can be assigned to the day and night tasks of si, totalac_si is the total quantity of capabilities that can be assigned to tasks of si, and WDi/WNi represents the workload of the day/night task of si.Next, according to equation (5), we estimate the number of devices required for each task of si (lines 9-10):(5)number_DTi=round_offac_DTiaverage_AC,number_NTi=round_offac_NTiaverage_AC,where number_DTi/number_NTi is the estimated quantity of available devices required for the day and night tasks, average_AC is the average capability of all available devices, and round_off is the function that rounds off the estimated quantity of devices. For example, round_off4.5=5 and round_off4.4=4.Subsequently, we use an example to illustrate howestimate_quantity() estimates the number of devices for each type of task of service.Example 4.
Combined with Example2, the capability of available devices, from d1 to d5, is 1.1, 1.21, 1.35, 1.25, and 1.26, respectively. Supposing that the workload for the day and night tasks of si is 5 and 3, we compute the total capability of all available devices. That is, total_AC = 1.1 + 1.21 + 1.35+1.25 + 1.26 = 6.17. Then, the average capability of these available average_AC = 6.17/5 = 1.234. According to equation (3), totalac_si = 6.17, since total_AC <WDi + WNi (6.17 < 5 + 3). Thus, we compute ac_DTi = 6.17 × 5/(5 + 3) = 3.86 and ac_NTi = 6.17 × 3/(5 + 3) = 2.31 as equation (4). Then, according to equation (5), we round off the estimated quantity of devices for each type of task of si, the estimated quantity of DTi and NTi is number_DTi = round_off (3.86/1.234) = 3 and number_NTi = round_off (2.31/1.234) = 2.Algorithm 3: estimate_number (available_D, WDi, WNi).
Input: The set of available devices available_D; the workload of day and night tasks WDi and WNiOutput: The estimated number of devices for each tasknumber_DTi and number_NTi(1)
total_AC← compute the total capabilities of all available devices;(2)
average_AC← compute the average capability of all available devices(3)
iftotal_AC<WDi + WNithen(4)
totalac_si = total_AC(5)
else(6)
totalac_si  = WDi+WNi(7)
ac_DTi  = total_AC×WDi/WDi+WNi;(8)
ac_NTi  = total_AC×WNi/WDi+WNi;(9)
number_DTi =  round_offac_DTi/average_AP;(10)
number_NTi  =  round_off (ac_NTi/average_AP);(11)
Return [ number_DTi, number_NTi];


### 3.3. Searching for a Feasible Schedule

Since the quantity of devices is estimated by the average capabilityaverage_AC of all available devices, procedure search_schedule() should ensure that the average capability of the actual assigned devices is as close to average_AC as possible. The more closer to average_AC the average capability of the actual assigned device is, the smaller the values of 1−Ave_Coverage and Coverage_Fairness are. To achieve this goal, we propose a PA strategy to search for a feasible schedule. Besides, we define a CAM as an index to further its efficiency. Next, we specify the main idea of PA and CAM with the following example, combined with the procedure search_schedule(), as shown in Algorithm 4.Algorithm 4: search_schedule (available_D, totalc_DTi, totalc_NTi, number_DTi, number_NTi).
Input: The capabilities of available devices AC; The estimated device quantity for each task number_DTi, number_NTiOutput: The feasible schedule Schedule(1)
AC←sort AC in ascending order;(2)
AC1,AC2←average_AC;(3)
CAM← compute the average value of any two capabilities in AC(4)
forcj∈AC1do(5)
forck∈AC2do(6)
L1,R1← (cj,ck);(7)
dp1¬ find the corresponding devices of cj,ck in AC(8)
Ep2¬2×average_AP−average_dp1;(9)
Removedp1∈CAM, AC1 and AC2;(10)
dp2← search in CAM;(11)
Removedp2∈CAM, AC1 and AC2;(12)
searchdpi until device quantity of {dp1,dp2,…,dpi−1} equals to number_DTi(13)
DC_DTi← {dp1,dp2,…,dpi−1};(14)
Replacenumber_DTi with number_NTi;(15)
DC_NTi¬ repeat the search operations of DTi(16)
add (DC_DTi,DC_NTi) into assignment(17)
the feasible schedulefs← TOPSIS(assignment)(18)
ReturnfsFirst, the capabilities of available device are sorted in ascending order (line 1). Then, as Figure1 shows, it is divided into two subsets (i.e., AC1 and AC2) by the value of average_AC (line 2). Thus, AC1 = {1.1, 1.21}, AC2 = {1.25, 1.26, 1.25}. Next, we adopt PA strategy. Specifically, we take the first capability in AC1 and AC2 (lines 4-5), denoted by {L1,R1} = 1.1,1.25 (line 6). Thus, the corresponding device group dp1 = {d1,d4} (line 7). The average capability of dp1average_dp1 (=1.1+1.25/2 = 1.175) is treated as a trigger to find the next device group cp2. To enable the average capability of dp1 and dp2 to maximally close to average_AC, the expected average capability of dp2Ep2=2×average_AC−average_dp1=2×1.234−1.175=1.293 (line 8). To quickly pick up such dp2, we precompute the CAM index as Figure 2 shows (line 3), which is defined as a square matrix of available_D. The PA strategy looks up the value that is closest to Ep2 (=1.293) in this CAM index. Note that, to follow the hard constraint Hard1 (i.e., each device is assigned to at most one task per service), dp2 is selected from at the available device except d1 and d4 (lines 9, 11) as Figure 3 shows. Hence, dp2 = {d3,d5}, because the average capability of d3 and d5 is 1.305, which is closest to 1.293 (line 10). Subsequently, the PA strategy computes the expected average capability of dpi (i≥3) and locates dpi in the same way until the total quantity of devices in the selected groups equals the estimated quantity (line 12). It is worth noting that if the estimated quantity of devices is odd, the last device is regarded as a group. Selecting the last device also follows the principle that the average capability of the group (i.e., the capability of the last device) is maximally close to the expected average capability. Thus, we generate a candidate assignment of device combinations (DC_DTi and DC_NTi), where the devices d1,d4,d5 are assigned to DTi and d2,d3 are assigned to NTi (lines 13–16). Subsequently, we select the first capability in AC1 and the second one in AC2, denoted by {L1,R2} = {1.1, 1.26}, and the corresponding device group dp1 = {d1,d5} is utilized to generate the next candidate assignment until all combinations of capability between AC1 and AC2 are listed.Figure 1
Dividing the capabilities set into two subsets.Figure 2
The example of establishing capability average matrix.Figure 3
The example of searchingdp2.These candidate assignments will be evaluated by TOPSIS [19] to select the feasible schedule (line 17). The reason why we use TOPSIS is that it is a multicriteria decision analysis method [20] and is widely used in evaluating a result with different dimensions. TOPSIS orthogonalizes optimization goals; that is, all optimization goals have the same direction of optimization. Next, TOPSIS standardizes all optimization goals since the optimization goals have different magnitudes. Finally, TOPSIS evaluates all candidate assignments and generates their scores; the higher the score is, the higher the quality of this assignment is. The detailed steps of TOPSIS will be described in the experiment section.


## 3.1. Identifying Available Device

For the servicesi (k≤i<n), not all the devices can be assigned to the tasks of si, since the hard constraint Hard2 rules that the maximal number of consecutive services cannot exceed k services for a device. Hence, for each device, the procedure identify_device() checks whether there is a Rest-status in its tasks of the previous k services (i.e., si−k+1,si−k+2,…,sk). If the answer is yes, the device is identified to be available for si. As for the service si (0<i<k), all devices are identified to be available, since even if the device dj is assigned to tasks during the previous i services, the maximal consecutive services of dj for si cannot be exceed k services.Next, we give an example to show how we identify available devices, combined with the procedure ofidentify_device(), which is presented in Algorithm 2.Algorithm 2: identify_device (D, k, si).
Input: The set of device D; the maximal consecutive services k; the ith service siOutput: The set of available devices available_Dsi)(1)
for each service si (k<i<n) do(2)
for each device dj in Ddo(3)
(task_si−k+1,task_si−k+2,…,task_sk) ← get tasks of the previous k services for dj;(4)
if (task_si−k+1,task_si−k+2,…,task_sk) contains a Rest-status then(5)
putdj into avaiable_D;(6)
for each service si (0<i≤k) do(7)
for each device djdo(8)
putdj into avaiable_D;(9)
Returnavailable_DExample 2.
Consider a scheduling example as shown in Table4, where there are 7 devices and all of them have been assigned to tasks of s1 and s2, suppose that the maximal number of consecutive services k is set to 2; now we need to identify the availability of devices for the service s3. From Table 4, since the service s3 (k<3<n, k=2), we get tasks of the previous 2 services for each device (line 3), then we traverse the tasks of each device to check for whether they contain a Rest-status (line 4). In this example, the tasks of the devices d1,d2,d3,d4,d5 contain a Rest-status and the others are not. The device with the tasks containing a Rest-status will be identified to be available and be stored in the set of available devices available_D (line 5). Thus, the devices d1,d2,d3,d4,d5 will be put into available_D, and the devices d6,d7 are identified to be unavailable for the service s3. As for the service si (0<i≤k, k=2), each device is available and will be stored in available_D (lines 6–8).Table 4
The assigned capability of each type of task.
DeviceServices1Services2Services3d1Day taskRest-statusAvailabled2Night taskRest-statusAvailabled3Rest-statusDay taskAvailabled4Rest-statusDay taskAvailabled5Rest-statusRest-statusAvailabled6Day taskNight taskUnavailabled7Night taskDay taskUnavailable


## 3.2. Estimating Device Quantity

After the available device ofsi is identified, we need to assign them to the tasks of si. To avoid enumerating the exponential device combinations, we invoke the procedure estimate_quantity() (as Algorithm 3 shows) to estimate the number of devices required for each type of task in advance. Specifically, Algorithm 3 takes the set of available devices and the workload of each type of task of si as inputs, and the output is the estimated quantity of available devices required for each type of task of si.First, according to the available device set, we compute their total capabilitytotal_AC and average capability average_AC (lines 1-2). Based on this, we estimate the number of devices required for each type of task. To avoid the understaffing/overstaffing problem, we need to confirm the total quantity of available capability totalac_si by the following equation:(3)totalac_si=total_AC,total_AC<WDi+WNi,WDi+WNi,total_AC≥WDi+WNi,where totalac_si is the total quantity of capabilities that can be assigned to tasks of si, total_AC denotes the total number of capabilities of all available devices of si, and WDi/WNi represents the workload of the day/night task of si. If total_AC<WDi+WNi, we assign all available devices to tasks and totalac_si = total_AC (lines 3 and 4). Otherwise, part of available devices will be assigned to tasks and totalac_siWDi+WNi (lines 5 and 6).Then based on the ratio of the workload of each task to that of all tasks, we compute the estimated quantity of each type of task, shown in the following equation (lines 7-8):(4)ac_DTi=totalac_si×WDiWDi+WNi,ac_NTi=totalac_si×WNiWDi+WNi,where ac_DTi and ac_NTi are the number of capabilities that can be assigned to the day and night tasks of si, totalac_si is the total quantity of capabilities that can be assigned to tasks of si, and WDi/WNi represents the workload of the day/night task of si.Next, according to equation (5), we estimate the number of devices required for each task of si (lines 9-10):(5)number_DTi=round_offac_DTiaverage_AC,number_NTi=round_offac_NTiaverage_AC,where number_DTi/number_NTi is the estimated quantity of available devices required for the day and night tasks, average_AC is the average capability of all available devices, and round_off is the function that rounds off the estimated quantity of devices. For example, round_off4.5=5 and round_off4.4=4.Subsequently, we use an example to illustrate howestimate_quantity() estimates the number of devices for each type of task of service.Example 4.
Combined with Example2, the capability of available devices, from d1 to d5, is 1.1, 1.21, 1.35, 1.25, and 1.26, respectively. Supposing that the workload for the day and night tasks of si is 5 and 3, we compute the total capability of all available devices. That is, total_AC = 1.1 + 1.21 + 1.35+1.25 + 1.26 = 6.17. Then, the average capability of these available average_AC = 6.17/5 = 1.234. According to equation (3), totalac_si = 6.17, since total_AC <WDi + WNi (6.17 < 5 + 3). Thus, we compute ac_DTi = 6.17 × 5/(5 + 3) = 3.86 and ac_NTi = 6.17 × 3/(5 + 3) = 2.31 as equation (4). Then, according to equation (5), we round off the estimated quantity of devices for each type of task of si, the estimated quantity of DTi and NTi is number_DTi = round_off (3.86/1.234) = 3 and number_NTi = round_off (2.31/1.234) = 2.Algorithm 3: estimate_number (available_D, WDi, WNi).
Input: The set of available devices available_D; the workload of day and night tasks WDi and WNiOutput: The estimated number of devices for each tasknumber_DTi and number_NTi(1)
total_AC← compute the total capabilities of all available devices;(2)
average_AC← compute the average capability of all available devices(3)
iftotal_AC<WDi + WNithen(4)
totalac_si = total_AC(5)
else(6)
totalac_si  = WDi+WNi(7)
ac_DTi  = total_AC×WDi/WDi+WNi;(8)
ac_NTi  = total_AC×WNi/WDi+WNi;(9)
number_DTi =  round_offac_DTi/average_AP;(10)
number_NTi  =  round_off (ac_NTi/average_AP);(11)
Return [ number_DTi, number_NTi];


## 3.3. Searching for a Feasible Schedule

Since the quantity of devices is estimated by the average capabilityaverage_AC of all available devices, procedure search_schedule() should ensure that the average capability of the actual assigned devices is as close to average_AC as possible. The more closer to average_AC the average capability of the actual assigned device is, the smaller the values of 1−Ave_Coverage and Coverage_Fairness are. To achieve this goal, we propose a PA strategy to search for a feasible schedule. Besides, we define a CAM as an index to further its efficiency. Next, we specify the main idea of PA and CAM with the following example, combined with the procedure search_schedule(), as shown in Algorithm 4.Algorithm 4: search_schedule (available_D, totalc_DTi, totalc_NTi, number_DTi, number_NTi).
Input: The capabilities of available devices AC; The estimated device quantity for each task number_DTi, number_NTiOutput: The feasible schedule Schedule(1)
AC←sort AC in ascending order;(2)
AC1,AC2←average_AC;(3)
CAM← compute the average value of any two capabilities in AC(4)
forcj∈AC1do(5)
forck∈AC2do(6)
L1,R1← (cj,ck);(7)
dp1¬ find the corresponding devices of cj,ck in AC(8)
Ep2¬2×average_AP−average_dp1;(9)
Removedp1∈CAM, AC1 and AC2;(10)
dp2← search in CAM;(11)
Removedp2∈CAM, AC1 and AC2;(12)
searchdpi until device quantity of {dp1,dp2,…,dpi−1} equals to number_DTi(13)
DC_DTi← {dp1,dp2,…,dpi−1};(14)
Replacenumber_DTi with number_NTi;(15)
DC_NTi¬ repeat the search operations of DTi(16)
add (DC_DTi,DC_NTi) into assignment(17)
the feasible schedulefs← TOPSIS(assignment)(18)
ReturnfsFirst, the capabilities of available device are sorted in ascending order (line 1). Then, as Figure1 shows, it is divided into two subsets (i.e., AC1 and AC2) by the value of average_AC (line 2). Thus, AC1 = {1.1, 1.21}, AC2 = {1.25, 1.26, 1.25}. Next, we adopt PA strategy. Specifically, we take the first capability in AC1 and AC2 (lines 4-5), denoted by {L1,R1} = 1.1,1.25 (line 6). Thus, the corresponding device group dp1 = {d1,d4} (line 7). The average capability of dp1average_dp1 (=1.1+1.25/2 = 1.175) is treated as a trigger to find the next device group cp2. To enable the average capability of dp1 and dp2 to maximally close to average_AC, the expected average capability of dp2Ep2=2×average_AC−average_dp1=2×1.234−1.175=1.293 (line 8). To quickly pick up such dp2, we precompute the CAM index as Figure 2 shows (line 3), which is defined as a square matrix of available_D. The PA strategy looks up the value that is closest to Ep2 (=1.293) in this CAM index. Note that, to follow the hard constraint Hard1 (i.e., each device is assigned to at most one task per service), dp2 is selected from at the available device except d1 and d4 (lines 9, 11) as Figure 3 shows. Hence, dp2 = {d3,d5}, because the average capability of d3 and d5 is 1.305, which is closest to 1.293 (line 10). Subsequently, the PA strategy computes the expected average capability of dpi (i≥3) and locates dpi in the same way until the total quantity of devices in the selected groups equals the estimated quantity (line 12). It is worth noting that if the estimated quantity of devices is odd, the last device is regarded as a group. Selecting the last device also follows the principle that the average capability of the group (i.e., the capability of the last device) is maximally close to the expected average capability. Thus, we generate a candidate assignment of device combinations (DC_DTi and DC_NTi), where the devices d1,d4,d5 are assigned to DTi and d2,d3 are assigned to NTi (lines 13–16). Subsequently, we select the first capability in AC1 and the second one in AC2, denoted by {L1,R2} = {1.1, 1.26}, and the corresponding device group dp1 = {d1,d5} is utilized to generate the next candidate assignment until all combinations of capability between AC1 and AC2 are listed.Figure 1
Dividing the capabilities set into two subsets.Figure 2
The example of establishing capability average matrix.Figure 3
The example of searchingdp2.These candidate assignments will be evaluated by TOPSIS [19] to select the feasible schedule (line 17). The reason why we use TOPSIS is that it is a multicriteria decision analysis method [20] and is widely used in evaluating a result with different dimensions. TOPSIS orthogonalizes optimization goals; that is, all optimization goals have the same direction of optimization. Next, TOPSIS standardizes all optimization goals since the optimization goals have different magnitudes. Finally, TOPSIS evaluates all candidate assignments and generates their scores; the higher the score is, the higher the quality of this assignment is. The detailed steps of TOPSIS will be described in the experiment section.


## 4. Discussion

We discuss the space and time complexities below.


### 4.1. Space Complexity Comparison

In the worst case, the space of our approach isO (n·m2/2), where n denotes the number of services in the scheduling horizon S and m represents the number of devices. As for the method of enumerating all possible schedules, its space is O (n·∑t=0,1,…,m2t·Cmt), where n denotes the number of services in the scheduling horizon S, t is the number of devices whose capabilities maximally minimize 1−Ave_Coverage and Fairness_Coverage, and Cmt represents the number of combinations of selecting t devices from the devices set whose size is m. Hence, the space of our approach is square, and that of traversing is exponential.(6)limn⟶∞n×m22/n×∑t=0,1,…,m2t·Cmt≤limm⟶∞m2∑t=0,1,…,mCmt=limm⟶∞m22m=0.


### 4.2. Time Complexity

Our approach generates a feasible assignment by theCAM index, which is composed of m2 average capabilities. Hence, a feasible assignment requires O (m2) time and all feasible assignments of n services need O (n·m4) time. As for enumerating all possible schedules, it requires O (n·∑t=0,1,…,m2t·Cmt) time. This time complexity is more than O (2m), and O (2m)>rbinO (m4).


## 4.1. Space Complexity Comparison

In the worst case, the space of our approach isO (n·m2/2), where n denotes the number of services in the scheduling horizon S and m represents the number of devices. As for the method of enumerating all possible schedules, its space is O (n·∑t=0,1,…,m2t·Cmt), where n denotes the number of services in the scheduling horizon S, t is the number of devices whose capabilities maximally minimize 1−Ave_Coverage and Fairness_Coverage, and Cmt represents the number of combinations of selecting t devices from the devices set whose size is m. Hence, the space of our approach is square, and that of traversing is exponential.(6)limn⟶∞n×m22/n×∑t=0,1,…,m2t·Cmt≤limm⟶∞m2∑t=0,1,…,mCmt=limm⟶∞m22m=0.


## 4.2. Time Complexity

Our approach generates a feasible assignment by theCAM index, which is composed of m2 average capabilities. Hence, a feasible assignment requires O (m2) time and all feasible assignments of n services need O (n·m4) time. As for enumerating all possible schedules, it requires O (n·∑t=0,1,…,m2t·Cmt) time. This time complexity is more than O (2m), and O (2m)>rbinO (m4).


## 5. Experiments

In this section, we experimentally evaluate the efficiency and effectiveness of our proposed solutionPACAM against the state-of-the-art methods. We implement our algorithm in Python and adopt the Python implementation of all competitors based on the following methods: (1) LP [21], (2) IP [22], (3) MIP [16], (4) IPSO [23], and (5) MOEAD [24]. The solver used in this article is Gurobi solver 9.1 [25]. It is worth noting that since all the above-mentioned approaches are universal methods, they can not be used directly; we make minor modifications to adapt them to our studied problem. In addition, to compare the performance of PACAM with the other five methods, we (1) report the response time of each method generating the same feasible schedule results and (2) report the TOPSIS score of each method under the same response time, in order to have a fairer and more accurate comparison.Besides, all evaluations in this section are based on a mixture of real and synthetic datasets, which are presented in Table5. The real part comes from the China Telecom company, containing the tasks of six months from July 2020 to December 2020. In Table 5, the number of services of each dataset is listed; it is worth noting that the tasks of each service si in each dataset are divided into two parts, treated as the workloads WDi and WNi for the day and night tasks of si, respectively. The synthetic part is the devices, which are synthesized from the real devices of China Telecom company, as shown in Table 5. Specifically, each month contains five synthetic device sets, whose quantities are 20, 40, 60, 80, and 100. Each device in these device sets has a capability. Note that each experiment will randomly choose the corresponding quantity of devices for ten times to be executed, and the average measurement is reported. All the experiments are conducted on a server machine with an Intel(R) Xeon(R) CPU E5-2637 3.50 GHz processor and 8 GB RAM, running Windows 10 with Python 3.8.Table 5
The datasets used in experiments.
DatasetsServicesTasksDevice quantityJuly 20203037,69181Aug. 20203138,03760Sept. 20203135,99176Oct. 20203037,11070Nov. 20203138,13386Dec. 20203036,51079


### 5.1. Metrics

Each potential schedule will be evaluated for facilitating generating the feasible schedule, and we adopt TOPSIS [19] to achieve this step. The main step of TOPSIS is presented as follows.First, the optimization goals need to be transformed into such an indicator, whose value is larger, resulting in a feasible with better quality, as TOPSIS asks. Hence, we transformAve_Coverage according to the following equation: (7)xi¯=1−xi−xbestM,s.t.M=maxxi−xbest,where xi denotes the value of Ave_Coverage for the ith schedule and xbest is the best value of Ave_Coverage for all schedules.Coverage_Fairness is transformed based on the following equation:(8)yi¯=1yi,where yi denotes the value of Coverage_Fairness for ith schedule.Next, we normalize these transformed optimization goals as follows:(9)normalized_valueij=valueij∑i=1nvalueij2,where valueij is the value of ith optimization goal for jth potential schedule and n denotes the number of potential schedules.Then, we compute the distance between the optimal/worst schedule and each potential schedule, according to the following:(10)distance_opt=∑j=12opt−normalized_valueij2,distance_wor=∑j=12wor−normalized_valueij2,where opt/wor denotes the values of optimization goals for the optimal/worst schedule among all potential schedules.Finally, we score each potential schedule according to the following equation and select the feasible schedule:(11)scorei=distance_wordistance_opt+distance_wor.


### 5.2. Experiment Setting

We perform nine sets of experiments to evaluate the performance of PACAM, where EXP1 to EXP6 are used to evaluate the overall performance among PACAM and five alternatives and EXP7 to EXP9 present the internal performance of PACAM. The parameters in each experiment are illustrated in Table6.Table 6
The parameters used in experiments.
EXPsDataNumber ofkSameSamesetsdevicesrun timequalityEXP1—1004✓EXP2—1004✓EXP3Nov.100—✓EXP4Nov.100—✓EXP5Nov.—4✓EXP6Nov.—4✓EXP7—1004✓EXP8Nov.100—✓EXP7Nov.—4✓EXP1 and EXP2 evaluate the impact of varying the datasets; we fix the number of devices to 100 and set the maximal consecutive servicesk to 4 services. Note that EXP1 generates the schedule with the same quality on all six datasets to report the response time, and EXP2 runs the same response time on all six datasets to report the quality of the generated schedule. EXP3 and EXP4 evaluate the impact of varying k; we fix the number of devices to 100 and run EXP3 on November to report the response time for generating the schedule with the same quality and run EXP4 on November to report the quality of generated schedule with the same running time. EXP5 and EXP6 evaluate the impact of varying the number of devices; we set the maximal consecutive services k to 4 and run EXP5 on November to report the response time for generating the schedule with the same quality and run EXP6 to report the quality of generated schedule with the same running time.All internal experiments (i.e., from EXP7 to EXP9) are performed, considering generating the schedule with the same quality as the end signal. Besides, EXP7 evaluates the internal impact of varying the datasets for PACAM; we fix the number of devices to 100, set the maximal consecutive services to 4, and report the response time. EXP8 evaluates the internal impact of varyingk; we fix the number of devices to 100 and run it on November to report response time. EXP9 evaluates the internal impact of varying the number of devices; we set the maximal consecutive services to 4 and run it on November to report the response time.


### 5.3. Overall Performance

#### 5.3.1. EXP 1: Search Efficiency

The first set of experiments verifies the performance of PACAM by varying datasets compared with the other five alternative methods. The result is illustrated in Figure4(a). The first observation is that PACAM is the best in all cases, with IP, LP, and MIP in the second place, they are comparable, and then IPSO and MOEAD are the worst. Particularly, on all six datasets, PACAM outperforms IP, LP, and MIP by two orders of magnitude, and it is faster than IPSO and MOEAD by 316.23 and 2511.89 times at least, respectively. This is because that IP, LP, and MIP need to consider all the potential schedules and MOEAD and IPSO need a large number of iterations to generate a feasible schedule due to the random nature of searching strategies, while PACAM preestimates the number of devices required for each type of task, which effectively shrinks the number of potential schedules. The second observation is that PACAM is more stable than MOEAD because PACAM searches for the feasible schedule within a small search range, owing to its preestimating strategy. While MOEAD generates the optimal schedule by mutation and crossover operations, these operations contain a random mechanism, which results in the instability of newly generated solutions.Figure 4
Overall effectiveness and efficiency with different datasets. (a) Fixing schedule quality. (b) Fixing response time.
(a)(b)


#### 5.3.2. EXP 2: Search Effectiveness on Running the Same Time

Compared with EXP 1, EXP 2 runs under the condition of running the same time and reports the TOPSIS score of each method as illustrated in Figure4(b). It is seen that when varying datasets, the TOPSIS score of PACAM changes slightly, and it is the highest. The reason is that PACAM adopts the pairwise-allocated strategy, which assigns devices to the tasks following the principle that the total capabilities of devices assigned to one task should be maximally close to the workload of this task. This guarantees that the average coverage will be maximally close to 1 and the coverage fairness will be reduced to the minimum. Hence, the corresponding TOPSIS will perform best. Three mathematical methods consider a prohibitive number of potential schedules, and thus they need more time to generate the feasible schedule. IPSO searches for the feasible schedule according to one previous solution nearest to the fixed schedule, which easily leads to locally optimal solutions. As for MOEAD, the limited running time does not allow MOEAD to perform enough generation operations, which influences the quality of the generated schedule.


#### 5.3.3. EXP 3: Effect ofk on Search Efficiency

The third set of experiments aims to explore the impact of varying maximal consecutive servicesk on search performance. The result is shown in Figure 5(a). The first observation is that the running time of all methods, except MOEAD, changes slightly with the growth of k. This is because PACAM uses the preestimating strategy so that varying the maximal consecutive services has nearly no effect on its efficiency. IP, LP, and MIP search for the feasible schedule in a huge range; the internal algorithms in solvers such as the branch and bound method help generate stable solutions. IPSO falls into a local optimum since its search strategy is based on the previous solution nearest to the fixed schedule. On the other hand, MOEAD generates a feasible schedule based on the random nature of the search strategy, and its response time is dependent on this rather than k. Thus, the response time of MOEAD fluctuates greatly. The second observation is that PACAM has the lowest elapsed time. The reason lies in two aspects. First, while searching for the feasible schedule, PACAM preprunes a large number of potential schedules and finds the feasible schedule based on pairwise-allocated strategy. Second, CAM is established to boost efficiency.Figure 5
Overall effectiveness and efficiency with varyingk. (a) Fixing schedule quality. (b) Fixing response time.
(a)(b)


#### 5.3.4. EXP 4: Effect ofk on Search Effectiveness with Same Running Time

EXP 4 runs under the same condition as EXP3 and reports the TOPSIS score of each method. The result is plotted in Figure5(b). The first observation is that the TOPSIS score of PACAM increases as k ascends. The reason is that a larger k means fewer rest services in a scheduling horizon and more available devices to be assigned in a day, leading to the total capabilities of devices assigned to one task being closer to its workload, and hence a higher TOPSIS score. The second observation is that the TOPSIS score of PACAM is still the highest under the different k. It is because the pairwise-allocated strategy in PACAM follows the principle that the selected device group should be the one making the average capability of all selected device groups nearest to that of all devices. Thus, the total capabilities of all assigned devices are maximally equal to the workload of the corresponding tasks.


#### 5.3.5. EXP 5: Effect of the Number of Devices on Search Efficiency

The fifth set of experiments evaluates the impact of the number of devices on search efficiency. The result is depicted in Figure6(a). The first observation is that the response time of PACAM, IP, LP, and MIP increases as the number of devices grows. The reason is that, for PACAM, an increasing number of devices means more potential device groups, which requires PACAM to spend more time searching for the suitable device group. Three mathematical methods require more response time since the number of potential device group combinations increases with the number of devices grows. The second observation is that the running time of MOEAD and IPSO fluctuates with the increase in the number of devices. The reason is that to search for the feasible schedule, MOEAD and IPSO need a large number of generation and iteration operations, where there is a great deal of randomness.Figure 6
Overall effectiveness and efficiency with the number of devices. (a) Fixing schedule quality. (b) Fixing response time.
(a)(b)


#### 5.3.6. EXP 6: Effect of the Number of Devices on Search Effectiveness

Figure6(b) shows the result of each method by varying the number of devices. It is observed that the TOPSIS score of PACAM increases as the number of devices grows. It is because that more device groups are available with an increasing number of devices, which means there is a higher possibility for PACAM selecting the device groups whose capability is nearest to the workload of tasks. As for the others, under limited running time, their mechanisms are time-consuming, and the generated feasible schedules are of low quality. Again, the TOPSIS score of PACAM is the highest in all cases.


### 5.4. Internal Performance

#### 5.4.1. EXP 7: Internal Performance vs. Different Datasets

The seventh set of experiments evaluates the internal impact of the performance of thePA strategy and CAM by varying the datasets. We compare PACAM with two alternative methods, i.e., PACAM-NoCAM and Traverse, respectively. PACAM-NoCAM removes the CAM, and Traverse evaluates all potential schedules. The result is illustrated in Figure 7(a). It is observed that PACAM is faster than PACAM-NoCAM and Traverse on all datasets. In particular, PACAM is 380 times faster than PACAM-NoCAM and outperforms Traverse by two orders of magnitude on average, respectively. This is because, compared to Traverse, PACAM and PACAM-NoCAM contain PA, which greatly reduces the number of potential schedules. This indicates that PA effectively shrinks search range and improves efficiency. In addition, PACAM adopts CAM to boost efficiency, and based on CAM, PACAM outperforms PACAM-NoCAM by 4.47 times; this finding indicates that CAM further improves the efficiency of search.Figure 7
Internal performance of PACAM by varying parameters. (a) Response time vs. different data sets. (b) Response time vs.k. (c) Response time vs. the number of devices.
(a)(b)(c)


#### 5.4.2. EXP 8: Internal Performance vs.k

The eighth set of experiments verifies the internal performance for PACAM by varyingk. The result is illustrated in Figure 7(b). The first observation is that the response time of all methods remains stable as the number of consecutive services grows. It is because both PACAM and PACAM-NoCAM adopt the pairwise-allocated strategy, shrink the number of potential schedules, and search for the feasible schedule in a small search range, which provides the stability of PACAM and PACAM-NoCAM. As for Traverse, once it finds the schedule, the response time is reported. Hence, the response time of Traverse remains stable. The second observation is that PACAM is the best in all cases, with PACAM-NoCAM in the second place, and then Traverse is the worst. The reason is that the number of potential schedules that are evaluated by Traverse is large; hence, Traverse requires a large amount of time consumption. PACAM-NoCAM adopts the PA strategy to reduce the number of potential schedules and searches for the feasible schedule in a small range, which effectively reduces the time cost. In addition, based on the PA strategy, PACAM utilizes the CAM to improve efficiency further.


#### 5.4.3. EXP 9: Internal Performance vs. the Number of Devices

The ninth set of experiments explores the effect of the number of devices on the internal performance of PACAM. The result is plotted in Figure7(c). The first observation is that the response time of traversing is exponential because the number of potential schedules grows exponentially as the number of devices increases. The second observation is that the response time of PACAM and PACAM-NoCAM keeps stable since estimating the number of devices prunes plenty of unfeasible schedules, leading to less time in selecting suitable device groups. The third observation is that compared with PACAM-NoCAM, the response time of PACAM is much shorter. The reason is that PACAM uses CAM for fast finding the suitable device groups.


## 5.1. Metrics

Each potential schedule will be evaluated for facilitating generating the feasible schedule, and we adopt TOPSIS [19] to achieve this step. The main step of TOPSIS is presented as follows.First, the optimization goals need to be transformed into such an indicator, whose value is larger, resulting in a feasible with better quality, as TOPSIS asks. Hence, we transformAve_Coverage according to the following equation: (7)xi¯=1−xi−xbestM,s.t.M=maxxi−xbest,where xi denotes the value of Ave_Coverage for the ith schedule and xbest is the best value of Ave_Coverage for all schedules.Coverage_Fairness is transformed based on the following equation:(8)yi¯=1yi,where yi denotes the value of Coverage_Fairness for ith schedule.Next, we normalize these transformed optimization goals as follows:(9)normalized_valueij=valueij∑i=1nvalueij2,where valueij is the value of ith optimization goal for jth potential schedule and n denotes the number of potential schedules.Then, we compute the distance between the optimal/worst schedule and each potential schedule, according to the following:(10)distance_opt=∑j=12opt−normalized_valueij2,distance_wor=∑j=12wor−normalized_valueij2,where opt/wor denotes the values of optimization goals for the optimal/worst schedule among all potential schedules.Finally, we score each potential schedule according to the following equation and select the feasible schedule:(11)scorei=distance_wordistance_opt+distance_wor.


## 5.2. Experiment Setting

We perform nine sets of experiments to evaluate the performance of PACAM, where EXP1 to EXP6 are used to evaluate the overall performance among PACAM and five alternatives and EXP7 to EXP9 present the internal performance of PACAM. The parameters in each experiment are illustrated in Table6.Table 6
The parameters used in experiments.
EXPsDataNumber ofkSameSamesetsdevicesrun timequalityEXP1—1004✓EXP2—1004✓EXP3Nov.100—✓EXP4Nov.100—✓EXP5Nov.—4✓EXP6Nov.—4✓EXP7—1004✓EXP8Nov.100—✓EXP7Nov.—4✓EXP1 and EXP2 evaluate the impact of varying the datasets; we fix the number of devices to 100 and set the maximal consecutive servicesk to 4 services. Note that EXP1 generates the schedule with the same quality on all six datasets to report the response time, and EXP2 runs the same response time on all six datasets to report the quality of the generated schedule. EXP3 and EXP4 evaluate the impact of varying k; we fix the number of devices to 100 and run EXP3 on November to report the response time for generating the schedule with the same quality and run EXP4 on November to report the quality of generated schedule with the same running time. EXP5 and EXP6 evaluate the impact of varying the number of devices; we set the maximal consecutive services k to 4 and run EXP5 on November to report the response time for generating the schedule with the same quality and run EXP6 to report the quality of generated schedule with the same running time.All internal experiments (i.e., from EXP7 to EXP9) are performed, considering generating the schedule with the same quality as the end signal. Besides, EXP7 evaluates the internal impact of varying the datasets for PACAM; we fix the number of devices to 100, set the maximal consecutive services to 4, and report the response time. EXP8 evaluates the internal impact of varyingk; we fix the number of devices to 100 and run it on November to report response time. EXP9 evaluates the internal impact of varying the number of devices; we set the maximal consecutive services to 4 and run it on November to report the response time.


## 5.3. Overall Performance

### 5.3.1. EXP 1: Search Efficiency

The first set of experiments verifies the performance of PACAM by varying datasets compared with the other five alternative methods. The result is illustrated in Figure4(a). The first observation is that PACAM is the best in all cases, with IP, LP, and MIP in the second place, they are comparable, and then IPSO and MOEAD are the worst. Particularly, on all six datasets, PACAM outperforms IP, LP, and MIP by two orders of magnitude, and it is faster than IPSO and MOEAD by 316.23 and 2511.89 times at least, respectively. This is because that IP, LP, and MIP need to consider all the potential schedules and MOEAD and IPSO need a large number of iterations to generate a feasible schedule due to the random nature of searching strategies, while PACAM preestimates the number of devices required for each type of task, which effectively shrinks the number of potential schedules. The second observation is that PACAM is more stable than MOEAD because PACAM searches for the feasible schedule within a small search range, owing to its preestimating strategy. While MOEAD generates the optimal schedule by mutation and crossover operations, these operations contain a random mechanism, which results in the instability of newly generated solutions.Figure 4
Overall effectiveness and efficiency with different datasets. (a) Fixing schedule quality. (b) Fixing response time.
(a)(b)


### 5.3.2. EXP 2: Search Effectiveness on Running the Same Time

Compared with EXP 1, EXP 2 runs under the condition of running the same time and reports the TOPSIS score of each method as illustrated in Figure4(b). It is seen that when varying datasets, the TOPSIS score of PACAM changes slightly, and it is the highest. The reason is that PACAM adopts the pairwise-allocated strategy, which assigns devices to the tasks following the principle that the total capabilities of devices assigned to one task should be maximally close to the workload of this task. This guarantees that the average coverage will be maximally close to 1 and the coverage fairness will be reduced to the minimum. Hence, the corresponding TOPSIS will perform best. Three mathematical methods consider a prohibitive number of potential schedules, and thus they need more time to generate the feasible schedule. IPSO searches for the feasible schedule according to one previous solution nearest to the fixed schedule, which easily leads to locally optimal solutions. As for MOEAD, the limited running time does not allow MOEAD to perform enough generation operations, which influences the quality of the generated schedule.


### 5.3.3. EXP 3: Effect ofk on Search Efficiency

The third set of experiments aims to explore the impact of varying maximal consecutive servicesk on search performance. The result is shown in Figure 5(a). The first observation is that the running time of all methods, except MOEAD, changes slightly with the growth of k. This is because PACAM uses the preestimating strategy so that varying the maximal consecutive services has nearly no effect on its efficiency. IP, LP, and MIP search for the feasible schedule in a huge range; the internal algorithms in solvers such as the branch and bound method help generate stable solutions. IPSO falls into a local optimum since its search strategy is based on the previous solution nearest to the fixed schedule. On the other hand, MOEAD generates a feasible schedule based on the random nature of the search strategy, and its response time is dependent on this rather than k. Thus, the response time of MOEAD fluctuates greatly. The second observation is that PACAM has the lowest elapsed time. The reason lies in two aspects. First, while searching for the feasible schedule, PACAM preprunes a large number of potential schedules and finds the feasible schedule based on pairwise-allocated strategy. Second, CAM is established to boost efficiency.Figure 5
Overall effectiveness and efficiency with varyingk. (a) Fixing schedule quality. (b) Fixing response time.
(a)(b)


### 5.3.4. EXP 4: Effect ofk on Search Effectiveness with Same Running Time

EXP 4 runs under the same condition as EXP3 and reports the TOPSIS score of each method. The result is plotted in Figure5(b). The first observation is that the TOPSIS score of PACAM increases as k ascends. The reason is that a larger k means fewer rest services in a scheduling horizon and more available devices to be assigned in a day, leading to the total capabilities of devices assigned to one task being closer to its workload, and hence a higher TOPSIS score. The second observation is that the TOPSIS score of PACAM is still the highest under the different k. It is because the pairwise-allocated strategy in PACAM follows the principle that the selected device group should be the one making the average capability of all selected device groups nearest to that of all devices. Thus, the total capabilities of all assigned devices are maximally equal to the workload of the corresponding tasks.


### 5.3.5. EXP 5: Effect of the Number of Devices on Search Efficiency

The fifth set of experiments evaluates the impact of the number of devices on search efficiency. The result is depicted in Figure6(a). The first observation is that the response time of PACAM, IP, LP, and MIP increases as the number of devices grows. The reason is that, for PACAM, an increasing number of devices means more potential device groups, which requires PACAM to spend more time searching for the suitable device group. Three mathematical methods require more response time since the number of potential device group combinations increases with the number of devices grows. The second observation is that the running time of MOEAD and IPSO fluctuates with the increase in the number of devices. The reason is that to search for the feasible schedule, MOEAD and IPSO need a large number of generation and iteration operations, where there is a great deal of randomness.Figure 6
Overall effectiveness and efficiency with the number of devices. (a) Fixing schedule quality. (b) Fixing response time.
(a)(b)


### 5.3.6. EXP 6: Effect of the Number of Devices on Search Effectiveness

Figure6(b) shows the result of each method by varying the number of devices. It is observed that the TOPSIS score of PACAM increases as the number of devices grows. It is because that more device groups are available with an increasing number of devices, which means there is a higher possibility for PACAM selecting the device groups whose capability is nearest to the workload of tasks. As for the others, under limited running time, their mechanisms are time-consuming, and the generated feasible schedules are of low quality. Again, the TOPSIS score of PACAM is the highest in all cases.


## 5.3.1. EXP 1: Search Efficiency

The first set of experiments verifies the performance of PACAM by varying datasets compared with the other five alternative methods. The result is illustrated in Figure4(a). The first observation is that PACAM is the best in all cases, with IP, LP, and MIP in the second place, they are comparable, and then IPSO and MOEAD are the worst. Particularly, on all six datasets, PACAM outperforms IP, LP, and MIP by two orders of magnitude, and it is faster than IPSO and MOEAD by 316.23 and 2511.89 times at least, respectively. This is because that IP, LP, and MIP need to consider all the potential schedules and MOEAD and IPSO need a large number of iterations to generate a feasible schedule due to the random nature of searching strategies, while PACAM preestimates the number of devices required for each type of task, which effectively shrinks the number of potential schedules. The second observation is that PACAM is more stable than MOEAD because PACAM searches for the feasible schedule within a small search range, owing to its preestimating strategy. While MOEAD generates the optimal schedule by mutation and crossover operations, these operations contain a random mechanism, which results in the instability of newly generated solutions.Figure 4
Overall effectiveness and efficiency with different datasets. (a) Fixing schedule quality. (b) Fixing response time.
(a)(b)


## 5.3.2. EXP 2: Search Effectiveness on Running the Same Time

Compared with EXP 1, EXP 2 runs under the condition of running the same time and reports the TOPSIS score of each method as illustrated in Figure4(b). It is seen that when varying datasets, the TOPSIS score of PACAM changes slightly, and it is the highest. The reason is that PACAM adopts the pairwise-allocated strategy, which assigns devices to the tasks following the principle that the total capabilities of devices assigned to one task should be maximally close to the workload of this task. This guarantees that the average coverage will be maximally close to 1 and the coverage fairness will be reduced to the minimum. Hence, the corresponding TOPSIS will perform best. Three mathematical methods consider a prohibitive number of potential schedules, and thus they need more time to generate the feasible schedule. IPSO searches for the feasible schedule according to one previous solution nearest to the fixed schedule, which easily leads to locally optimal solutions. As for MOEAD, the limited running time does not allow MOEAD to perform enough generation operations, which influences the quality of the generated schedule.


## 5.3.3. EXP 3: Effect ofk on Search Efficiency

The third set of experiments aims to explore the impact of varying maximal consecutive servicesk on search performance. The result is shown in Figure 5(a). The first observation is that the running time of all methods, except MOEAD, changes slightly with the growth of k. This is because PACAM uses the preestimating strategy so that varying the maximal consecutive services has nearly no effect on its efficiency. IP, LP, and MIP search for the feasible schedule in a huge range; the internal algorithms in solvers such as the branch and bound method help generate stable solutions. IPSO falls into a local optimum since its search strategy is based on the previous solution nearest to the fixed schedule. On the other hand, MOEAD generates a feasible schedule based on the random nature of the search strategy, and its response time is dependent on this rather than k. Thus, the response time of MOEAD fluctuates greatly. The second observation is that PACAM has the lowest elapsed time. The reason lies in two aspects. First, while searching for the feasible schedule, PACAM preprunes a large number of potential schedules and finds the feasible schedule based on pairwise-allocated strategy. Second, CAM is established to boost efficiency.Figure 5
Overall effectiveness and efficiency with varyingk. (a) Fixing schedule quality. (b) Fixing response time.
(a)(b)


## 5.3.4. EXP 4: Effect ofk on Search Effectiveness with Same Running Time

EXP 4 runs under the same condition as EXP3 and reports the TOPSIS score of each method. The result is plotted in Figure5(b). The first observation is that the TOPSIS score of PACAM increases as k ascends. The reason is that a larger k means fewer rest services in a scheduling horizon and more available devices to be assigned in a day, leading to the total capabilities of devices assigned to one task being closer to its workload, and hence a higher TOPSIS score. The second observation is that the TOPSIS score of PACAM is still the highest under the different k. It is because the pairwise-allocated strategy in PACAM follows the principle that the selected device group should be the one making the average capability of all selected device groups nearest to that of all devices. Thus, the total capabilities of all assigned devices are maximally equal to the workload of the corresponding tasks.


## 5.3.5. EXP 5: Effect of the Number of Devices on Search Efficiency

The fifth set of experiments evaluates the impact of the number of devices on search efficiency. The result is depicted in Figure6(a). The first observation is that the response time of PACAM, IP, LP, and MIP increases as the number of devices grows. The reason is that, for PACAM, an increasing number of devices means more potential device groups, which requires PACAM to spend more time searching for the suitable device group. Three mathematical methods require more response time since the number of potential device group combinations increases with the number of devices grows. The second observation is that the running time of MOEAD and IPSO fluctuates with the increase in the number of devices. The reason is that to search for the feasible schedule, MOEAD and IPSO need a large number of generation and iteration operations, where there is a great deal of randomness.Figure 6
Overall effectiveness and efficiency with the number of devices. (a) Fixing schedule quality. (b) Fixing response time.
(a)(b)


## 5.3.6. EXP 6: Effect of the Number of Devices on Search Effectiveness

Figure6(b) shows the result of each method by varying the number of devices. It is observed that the TOPSIS score of PACAM increases as the number of devices grows. It is because that more device groups are available with an increasing number of devices, which means there is a higher possibility for PACAM selecting the device groups whose capability is nearest to the workload of tasks. As for the others, under limited running time, their mechanisms are time-consuming, and the generated feasible schedules are of low quality. Again, the TOPSIS score of PACAM is the highest in all cases.


## 5.4. Internal Performance

### 5.4.1. EXP 7: Internal Performance vs. Different Datasets

The seventh set of experiments evaluates the internal impact of the performance of thePA strategy and CAM by varying the datasets. We compare PACAM with two alternative methods, i.e., PACAM-NoCAM and Traverse, respectively. PACAM-NoCAM removes the CAM, and Traverse evaluates all potential schedules. The result is illustrated in Figure 7(a). It is observed that PACAM is faster than PACAM-NoCAM and Traverse on all datasets. In particular, PACAM is 380 times faster than PACAM-NoCAM and outperforms Traverse by two orders of magnitude on average, respectively. This is because, compared to Traverse, PACAM and PACAM-NoCAM contain PA, which greatly reduces the number of potential schedules. This indicates that PA effectively shrinks search range and improves efficiency. In addition, PACAM adopts CAM to boost efficiency, and based on CAM, PACAM outperforms PACAM-NoCAM by 4.47 times; this finding indicates that CAM further improves the efficiency of search.Figure 7
Internal performance of PACAM by varying parameters. (a) Response time vs. different data sets. (b) Response time vs.k. (c) Response time vs. the number of devices.
(a)(b)(c)


### 5.4.2. EXP 8: Internal Performance vs.k

The eighth set of experiments verifies the internal performance for PACAM by varyingk. The result is illustrated in Figure 7(b). The first observation is that the response time of all methods remains stable as the number of consecutive services grows. It is because both PACAM and PACAM-NoCAM adopt the pairwise-allocated strategy, shrink the number of potential schedules, and search for the feasible schedule in a small search range, which provides the stability of PACAM and PACAM-NoCAM. As for Traverse, once it finds the schedule, the response time is reported. Hence, the response time of Traverse remains stable. The second observation is that PACAM is the best in all cases, with PACAM-NoCAM in the second place, and then Traverse is the worst. The reason is that the number of potential schedules that are evaluated by Traverse is large; hence, Traverse requires a large amount of time consumption. PACAM-NoCAM adopts the PA strategy to reduce the number of potential schedules and searches for the feasible schedule in a small range, which effectively reduces the time cost. In addition, based on the PA strategy, PACAM utilizes the CAM to improve efficiency further.


### 5.4.3. EXP 9: Internal Performance vs. the Number of Devices

The ninth set of experiments explores the effect of the number of devices on the internal performance of PACAM. The result is plotted in Figure7(c). The first observation is that the response time of traversing is exponential because the number of potential schedules grows exponentially as the number of devices increases. The second observation is that the response time of PACAM and PACAM-NoCAM keeps stable since estimating the number of devices prunes plenty of unfeasible schedules, leading to less time in selecting suitable device groups. The third observation is that compared with PACAM-NoCAM, the response time of PACAM is much shorter. The reason is that PACAM uses CAM for fast finding the suitable device groups.


## 5.4.1. EXP 7: Internal Performance vs. Different Datasets

The seventh set of experiments evaluates the internal impact of the performance of thePA strategy and CAM by varying the datasets. We compare PACAM with two alternative methods, i.e., PACAM-NoCAM and Traverse, respectively. PACAM-NoCAM removes the CAM, and Traverse evaluates all potential schedules. The result is illustrated in Figure 7(a). It is observed that PACAM is faster than PACAM-NoCAM and Traverse on all datasets. In particular, PACAM is 380 times faster than PACAM-NoCAM and outperforms Traverse by two orders of magnitude on average, respectively. This is because, compared to Traverse, PACAM and PACAM-NoCAM contain PA, which greatly reduces the number of potential schedules. This indicates that PA effectively shrinks search range and improves efficiency. In addition, PACAM adopts CAM to boost efficiency, and based on CAM, PACAM outperforms PACAM-NoCAM by 4.47 times; this finding indicates that CAM further improves the efficiency of search.Figure 7
Internal performance of PACAM by varying parameters. (a) Response time vs. different data sets. (b) Response time vs.k. (c) Response time vs. the number of devices.
(a)(b)(c)


## 5.4.2. EXP 8: Internal Performance vs.k

The eighth set of experiments verifies the internal performance for PACAM by varyingk. The result is illustrated in Figure 7(b). The first observation is that the response time of all methods remains stable as the number of consecutive services grows. It is because both PACAM and PACAM-NoCAM adopt the pairwise-allocated strategy, shrink the number of potential schedules, and search for the feasible schedule in a small search range, which provides the stability of PACAM and PACAM-NoCAM. As for Traverse, once it finds the schedule, the response time is reported. Hence, the response time of Traverse remains stable. The second observation is that PACAM is the best in all cases, with PACAM-NoCAM in the second place, and then Traverse is the worst. The reason is that the number of potential schedules that are evaluated by Traverse is large; hence, Traverse requires a large amount of time consumption. PACAM-NoCAM adopts the PA strategy to reduce the number of potential schedules and searches for the feasible schedule in a small range, which effectively reduces the time cost. In addition, based on the PA strategy, PACAM utilizes the CAM to improve efficiency further.


## 5.4.3. EXP 9: Internal Performance vs. the Number of Devices

The ninth set of experiments explores the effect of the number of devices on the internal performance of PACAM. The result is plotted in Figure7(c). The first observation is that the response time of traversing is exponential because the number of potential schedules grows exponentially as the number of devices increases. The second observation is that the response time of PACAM and PACAM-NoCAM keeps stable since estimating the number of devices prunes plenty of unfeasible schedules, leading to less time in selecting suitable device groups. The third observation is that compared with PACAM-NoCAM, the response time of PACAM is much shorter. The reason is that PACAM uses CAM for fast finding the suitable device groups.


## 6. Related Work

Currently, algorithms to address task scheduling problems of edge computing are divided into three categories. The first category is to adopt the method of mathematical programming. Regularly, it models the task scheduling problem by complex mathematical models, then computes the feasible schedules by operating a series of solvers like MIP solver [13–17] on this problem model. Although this category of the method has high effectiveness, a large amount of computation leads to low efficiency and high response time. These methods do not provide the allocated strategy and search strategy as PACAM does and limi themselves to similar trips or other mathematical methods.The second category is the approximate algorithm. Many studies are adopting approximate algorithms in such resource scheduling. Badri et al. [26] modeled the application placement of the MEC system and adopted the parallel sample averaging approximation (SAA) algorithm to solve it. Guo et al. [27] treated the edge-cloud placement problem as a multiobjective optimization problem and addressed it by k-means and hybrid quadratic programming. Fang [28] described a multiuser resource allocation problem in edge computing and proposed an approximate algorithm for local search to solve this problem. The basic idea of these algorithms is to model their problem and adopt the existing approximate methods for generating feasible solutions. In addition, some works assigned tasks to devices with proper skill type by collaborative filtering mechanism [29], but it is out of our consideration. In summary, these methods have shortages, such that they are easy to fall into a local optimum and the performance of the solutions can not be guaranteed due to randomness. Moreover, in our work, we propose PACAM, which strategically assigns devices and defines a matrix-based index to speed up searching for the feasible schedule.The third category is the heuristic algorithm. Nowadays, an increasing number of ways to solve task scheduling problems in edge computing is heuristic algorithms. Considering some phenomenons in nature, heuristic algorithms abstracted this similarity into their methods to address the task scheduling problem [30]. Hong et al. [24] modeled their resource scheduling problem as a multiobjective problem and adopted the multiobjective evolutionary algorithm based on decomposition (MOEAD) to generate feasible solutions. In addition, some works [31, 32] used the nondominated sorting genetic algorithm (NSGA) to deal with the task scheduling problem containing multiple objectives. Besides, the authors in [23] proposed a PSO-based heuristic strategy to solve the joint problem of service placement and task provisioning. This algorithm solved the resource scheduling problem by greedy-based and genetic-based algorithms. However, they are easy to fall into a local optimal solution. Besides, most of them require too much domain knowledge to adjust the parameters, and it is impossible to get feasible parameters efficiently. In our work, PACAM preestimates the number of devices required for each type of task, which avoids wide-range search. PACAM adopts a series of strategies to shrink the number of potential schedules, such as the PA strategy and CAM and effectively assign devices to the corresponding tasks of each day.


## 7. Conclusion

This article proposes PACAM, a PA strategy and CAM-based approach, to solving the task scheduling problem. Devices are assigned to tasks of each service in the scheduling horizon; meanwhile, the hard constraints must be followed and the soft constraint should be maximally satisfied. Based on these, PACAM estimates the number of devices required for each type of task of each service in the scheduling horizon. Then, PACAM adopts the PA strategy to assign the corresponding number of devices to tasks. To facilitate finding the device groups we need, PACAM takes CAM as an index to speed up this process. Thus, we just spent a few computations to find the final feasible schedule. Extensive experimental evaluation demonstrates the effectiveness and efficiency of our proposed approach. In the future, we intend to explore how to assign large-scale devices to tasks with more optimization goals.



---

*Source: 6430612-2022-01-11.xml*