Improved Heuristic Job Scheduling Method to Enhance Throughput for Big Data Analytics

To decrease the average JCT, we further explore the cause why the SJF method performs worse than the heuristic method, as shown in Fig. 1 . If jobs with short JCT may consume a large amount of resources, the SJF method prolongs the completion of the majority of jobs, which have a request for a small amount of resources. To sum up, the SJF method does not consider the resources capacity of the cluster. As a result, the number of parallel jobs may decrease. To address this problem, we propose an improved heuristic job scheduling method to pack as many jobs as possible into the job set and then determine the scheduling priority of the job set according to the job completion efficiency. The job completion efficiency is defined as follows.

Definition 1 (job completion efficiency). Given that a batch of jobs $j_1$ , $j_2$ , $\mathrm{\dots }$ , $j_N$ are executed in parallel and packed into the set of jobs $J$ . Let $T$ denote the time span that all jobs in $J$ are completed. The job completion efficiency is as follows:

(1) $$\text{JCE}={\displaystyle \frac{N}{T}}$$

where $N$ is the number of jobs.

In Fig. 1 , the heuristic method packs Jobs 2-5 together. We regard such packed jobs as the set of jobs. Although the heuristic method takes 4.2 s to complete jobs in the job set, the number of completed jobs is four. This achieves a high job completion efficiency (up to approximately 0.95). By contrast, the SJF method prefers to execute Job 1. This condition leads to a low job completion efficiency (i.e., 0.25). To sum up, we leverage the job completion efficiency as a priority to schedule the set of jobs. Definition 1 indicates that the value of the job completion efficiency is equivalent to the system throughput, i.e., how many jobs are completed in a given amount of time. Next, we prove that such a scheduling order, which is determined according to the job completion efficiency, achieves the smallest average JCT.

Theorem 1 Given a batch of jobs, we pack them into two sets of jobs $J_1$ and $J_2$ . Note that $J_1$ and $J_2$ are executed in a successive order. If the job set with a higher job completion efficiency for scheduling, then the average JCT is smaller. Let ${\text{JCE}}_1$ and ${\text{JCE}}_2$ denote the job completion efficiency of $J_1$ and $J_2$ , respectively. If ${\text{JCE}}_1>{\text{JCE}}_2$ , then the scheduling order $J_1\to J_2$ achieves a smaller average JCT than another scheduling order $J_2\to J_1$ .

Proof We list the information about the set of jobs in Table 1 . $N_1$ and $N_2$ denote the number of jobs in $J_1$ and $J_2$ , respectively. $T_1$ and $T_2$ denote the time span of $J_1$ and $J_2$ , respectively.

Case 1 If a scheduler prefers to schedule the job set with a higher job completion efficiency, then the scheduling preference is $J_1\to J_2$ . The completion time of $J_1$ is $T_1$ . The sum of JCT of all jobs in $J_1$ is approximately $N_1\times T_1$ . Similarly, the completion time of $J_2$ is $T_1+T_2$ . The sum of JCT in $J_2$ is approximately $N_2\times (T_1+T_2)$ . In this case, the sum of JCT in $J_1$ and $J_2$ is

(2) $$N_1\times T_1+N_2\times (T_1+T_2)$$

Case 2 If a scheduler prefers to schedule the job set with a smaller job completion efficiency, then the scheduling preference is $J_2\to J_1$ . The completion time of $J_2$ is $T_2$ . The sum of JCT of all jobs in $J_2$ is approximately $N_2\times T_2$ . Similarly, the completion time of $J_1$ is $T_1+T_2$ . The sum of JCT in $J_1$ is approximately $N_1\times (T_1+T_2)$ . In this case, the sum of JCT in $J_1$ and $J_2$ is

(3) $$N_2\times T_2+N_1\times (T_1+T_2)$$

Because $J_1$ has a larger job completion efficiency than $J_2$ , we have $N_1/T_1>N_2/T_2$ . Hence, we have $N_1\times T_2>N_2\times T_1$ . We compare Formula ( 2 ) with Formula ( 3 ). The sum of JCT in Case 1 is smaller than that in Case 2. We make a conclusion that for any two job sets $J_1$ and $J_2$ , the job set with a larger job completion efficiency should be preferred for scheduling to achieve a smaller average JCT.

We extend the above conclusion to a new case where three job sets are scheduled. To extend the conclusion, we introduce the following lemma.

Lemma 1 Given that any two job sets $J_{\text{a}}$ and $J_{\text{b}}$ can be executed serially, the two job sets are scheduled in a successive order. We regard $J_{\text{a}}$ and $J_{\text{b}}$ as a new job set, denoted by $J_{\text{c}}$ . Let ${\text{JCE}}_{\text{a}}$ and ${\text{JCE}}_{\text{b}}$ denote the job completion efficiency of $J_{\text{a}}$ and $J_{\text{b}}$ , respectively. We have

$$\min \{{\text{JCE}}_{\text{a}},{\text{JCE}}_{\text{b}}\}<{\text{JCE}}_{\text{c}}<\max \{{\text{JCE}}_{\text{a}},{\text{JCE}}_{\text{b}}\}.$$

Proof Let $N_{\text{a}}$ and $N_{\text{b}}$ denote the number of jobs in $J_{\text{a}}$ and $J_{\text{b}}$ , respectively. Let $T_{\text{a}}$ and $T_{\text{b}}$ denote the time span of $J_{\text{a}}$ and $J_{\text{b}}$ , respectively. We have ${\text{JCE}}_{\text{a}}=N_{\text{a}}/T_{\text{a}}$ and ${\text{JCE}}_{\text{b}}=N_{\text{b}}/T_{\text{b}}$ . For the job set $J_{\text{c}}$ , the number of jobs in $J_{\text{c}}$ is $N_{\text{a}}+N_{\text{b}}$ . The time span of $J_{\text{c}}$ is $T_{\text{a}}+T_{\text{b}}$ . Thus, the job completion efficiency of $J_{\text{c}}$ is ${\text{JCE}}_{\text{c}}=(N_{\text{a}}+N_{\text{b}})/(T_{\text{a}}+T_{\text{b}})$ . Assume that the job completion efficiency of $J_{\text{a}}$ is larger than that of $J_{\text{b}}$ . Owing to ${\text{JCE}}_{\text{a}}>{\text{JCE}}_{\text{b}}$ , i.e., $N_{\text{a}}/T_{\text{a}}>N_{\text{b}}/T_{\text{b}}$ , we have $N_{\text{a}}\times T_{\text{b}}>N_{\text{b}}\times T_{\text{a}}$ . Hence, we have $(N_{\text{a}}+N_{\text{b}})\times T_{\text{b}}>N_{\text{b}}\times (T_{\text{a}}+T_{\text{b}})$ . The following formula holds:

(4) $$(N_{\text{a}}+N_{\text{b}})/(T_{\text{a}}+T_{\text{b}})>N_{\text{b}}/T_{\text{b}}$$

Hence, ${\text{JCE}}_{\text{c}}>{\text{JCE}}_{\text{b}}$ is proven.

Similarly, because $N_{\text{a}}\times T_{\text{b}}>N_{\text{b}}\times T_{\text{a}}$ , we have $N_{\text{a}}\times (T_{\text{a}}+T_{\text{b}})>(N_{\text{a}}+N_{\text{b}})\times T_{\text{a}}$ ,

(5) $$N_{\text{a}}/T_{\text{a}}>(N_{\text{a}}+N_{\text{b}})/(T_{\text{a}}+T_{\text{b}})$$

Hence, ${\text{JCE}}_{\text{a}}>{\text{JCE}}_{\text{c}}$ is proven.

Next, we expand Theorem 1 to the case where over three job sets, i.e., $J_1$ , $J_2$ , and $J_3$ , are scheduled. We sort them by the value of the job completion efficiency. Assume that ${\text{JCE}}_1>{\text{JCE}}_2>{\text{JCE}}_3$ . According to Lemma 1, we regard $J_2$ and $J_3$ as a new set of jobs. Let $J_2^{\prime }$ denote the new job set. ${\text{JCE}}_2^{\prime }$ denotes the job completion efficiency of $J_2^{\prime }$ . According to Lemma 1, we have ${\text{JCE}}_2>{\text{JCE}}_2^{\prime }>{\text{JCE}}_3$ . Then the scheduling problem becomes the case in Theorem 1, where two job sets, $J_1$ and $J_2^{\prime }$ , are scheduled. According to Theorem 1, we prefer to schedule $J_1$ because the job completion efficiency of $J_1$ is larger than those of the other job sets. Similarly, after scheduling $J_1$ , we prefer to schedule $J_2$ rather than $J_3$ . The final scheduling preference is $J_1\to J_2\to J_3$ , which achieves the smallest average JCT.

To sum up, Theorem 1 can be recursively applied in multiple-job-set cases. We make the following general theorem.

Theorem 2 Given multiple job sets, the job set with the largest job completion efficiency should be scheduled with the highest priority to decrease the average JCT.

The job packing method adopts the $k$ -means clustering algorithm to group a batch of JCT according to the length of JCT. The $k$ -means clustering algorithm is a well-known data mining and machine learning tool, which is used to assign data points (i.e., the JCT of multiple jobs) into groups without any prior knowledge of those relationships. The $k$ -means clustering algorithm attempts to learn the difference between data points and finds which group, a data point belongs to. The $k$ -means clustering algorithm is one of the simplest clustering techniques, which is widely used in biometrics, medical imaging, and related fields. The $k$ -means clustering algorithm determines the group where data points should be assigned into rather than the user instructing to build the group of data points based on heuristic rules.

We are motivated to leverage the $k$ -means clustering algorithm^{[ 12 ]} to group jobs with different JCT. Algorithm 2 shows the main steps of the JCT clustering algorithm. The $k$ -means clustering based job packing method places a job to the group of jobs if the sum of the difference between the centroid of the group and the JCT of the jobs is at a minimum. A less variation in the group results in the jobs within the group to have similar JCT. The $k$ -means based JCT clustering algorithm is known to have a time complexity of $O(N^2)$ ^{[ 13 ]}.

In addition to the JCT alignment, the job packing method should increase the number of jobs packed in the job set. Given a group of jobs, the job packing method prefers to pack jobs that request a small amount of resources. This method aims to enhance the number of parallel jobs in the job set. In Fig. 5 , $n_1$ is the number of jobs, of which the JCT is smaller than $X_1$ . Similarly, $n_2$ is the number of jobs, of which the JCT is smaller than $X_2$ . Assume that we pack the jobs, of which the JCT is larger than $X_1$ but smaller than $X_2$ , into a new job set. The number of jobs in the job set is $n_2-n_1$ . The time span of the job set is $X_2$ . Thus, the job completion efficiency of the job set is $(n_2-n_1)/X_2$ . To enhance the value of the job completion efficiency, the job packing method maximizes the value of $n_2-n_1$ .

Algorithm 3 shows the main steps of the job packing method. After the JCT clustering method outputs the group of jobs, the job packing method packs jobs into the job set. The job packing method calculates the average JCT of each group. Then the job group that has smaller average JCT is preferred to be used in Algorithm 3. Within each group, the job packing method sorts jobs by the amount of resources. Jobs that request a small amount of resources are packed into the job set with high priorities. If the remaining resources is not enough for packing a job into the job set, then the job is packed into the next job set. When the last job is packed, the job packing method stops. Algorithm 3 has two For loops. The complexity of the job packing method is $O(GN)$ , where $G$ is the number of groups.

The job packing method adopts the $k$ -means clustering algorithm to group a batch of JCT according to the length of JCT. The $k$ -means clustering algorithm is a well-known data mining and machine learning tool, which is used to assign data points (i.e., the JCT of multiple jobs) into groups without any prior knowledge of those relationships. The $k$ -means clustering algorithm attempts to learn the difference between data points and finds which group, a data point belongs to. The $k$ -means clustering algorithm is one of the simplest clustering techniques, which is widely used in biometrics, medical imaging, and related fields. The $k$ -means clustering algorithm determines the group where data points should be assigned into rather than the user instructing to build the group of data points based on heuristic rules.

We are motivated to leverage the $k$ -means clustering algorithm^{[ 12 ]} to group jobs with different JCT. Algorithm 2 shows the main steps of the JCT clustering algorithm. The $k$ -means clustering based job packing method places a job to the group of jobs if the sum of the difference between the centroid of the group and the JCT of the jobs is at a minimum. A less variation in the group results in the jobs within the group to have similar JCT. The $k$ -means based JCT clustering algorithm is known to have a time complexity of $O(N^2)$ ^{[ 13 ]}.

In addition to the JCT alignment, the job packing method should increase the number of jobs packed in the job set. Given a group of jobs, the job packing method prefers to pack jobs that request a small amount of resources. This method aims to enhance the number of parallel jobs in the job set. In Fig. 5 , $n_1$ is the number of jobs, of which the JCT is smaller than $X_1$ . Similarly, $n_2$ is the number of jobs, of which the JCT is smaller than $X_2$ . Assume that we pack the jobs, of which the JCT is larger than $X_1$ but smaller than $X_2$ , into a new job set. The number of jobs in the job set is $n_2-n_1$ . The time span of the job set is $X_2$ . Thus, the job completion efficiency of the job set is $(n_2-n_1)/X_2$ . To enhance the value of the job completion efficiency, the job packing method maximizes the value of $n_2-n_1$ .

Algorithm 3 shows the main steps of the job packing method. After the JCT clustering method outputs the group of jobs, the job packing method packs jobs into the job set. The job packing method calculates the average JCT of each group. Then the job group that has smaller average JCT is preferred to be used in Algorithm 3. Within each group, the job packing method sorts jobs by the amount of resources. Jobs that request a small amount of resources are packed into the job set with high priorities. If the remaining resources is not enough for packing a job into the job set, then the job is packed into the next job set. When the last job is packed, the job packing method stops. Algorithm 3 has two For loops. The complexity of the job packing method is $O(GN)$ , where $G$ is the number of groups.