Keywords

1 Introduction

Scheduling algorithm allows us to manage the sequencing of tasks, confine the scheduled task, time management, and optimizing effort and assignments in any production or manufacturing process. Scheduling is used to allocate machinery resources to tasks. Processor scheduling is required for the high performance of computing systems. There are different heuristic methods existing for processor scheduling. Multiprocessor scheduling is considered as NP-hard problems, which are very difficult to solve with conventional techniques. Processor scheduling is classified into two categories: local processor scheduling and global processor scheduling. Conventional techniques mostly use local processor scheduling. Global processor scheduling is grouped into several families depending on scheduling processor techniques. These heuristic scheduling methods are biologically inspired and can be further grouped into several classes of heuristic approaches like an ant colony, bee colony, genetic algorithm, particle swarm optimization, etc. Local processor scheduling is scheduled upon the single-processor platform and also uses list scheduling to construct a schedule, one cycle at a time, whereas in global scheduling it uses the multiprocessor environment. In real-time task scheduling problem on multiprocessor, it has goal of meeting the deadline, and infrequent arrival of task has implicit deadline and such type of scheduling problems is handled by global static processor scheduling techniques. Static processor scheduling is deterministic scheduling policy. It is classified into two subclasses: optimal processor scheduling and suboptimal processor scheduling. Optimal processor scheduling is used when the job executed at that scheduler should know information about the requirement of processor and state of processors. Optimal scheduling reached NP-complete problem, so researchers focused on suboptimal processor scheduling that is classified as approximation and heuristic algorithm. Approximation scheduling uses the computational techniques for searching of entire solution space for an optimal solution. Heuristic approaches such as ant colony optimization, genetic algorithm, etc. provide feasible solutions to a scheduling problem which cannot give the optimal solution. Global dynamic scheduling had better to physically be inherent in a single processor. In dynamic processor scheduling techniques, a number of processors vary during execution. Dynamic processor scheduling leads to degradation of performance because of high run-time overhead. It has two subclasses: physically non-distributed processor scheduling and physically distributed processor scheduling. Physically non-distributed system includes the responsibility for the task scheduling, whereas in physically distributed system the work involved in decision-making should be physically spread among the various processors. Physically distributed processor scheduling is divided into two classes: (i) cooperative processor scheduling and (ii) non-cooperative processor scheduling. In non-cooperative processor scheduling, each separate processor acts as autonomous entities and it works as a decision-making for various resources running independently which affects the decision of rest system. In cooperative system, the goal of each processor is to carry its own part of scheduling and its work toward a common system. In the case of static system, the decision is taken for the taxonomy tree which reaches to the optimal, and for the consideration of the system the suboptimal heuristic solution is to be taken. Non-cooperative processor scheduling is classified into two categories: (i) approximation processor scheduling and (ii) heuristic processor scheduling. In the case of approximate processor scheduling, it is presented for the independent tasks and runs on different processors with different speeds in a multiprocessor environment. Approximation scheduling provides the low polynomial time complexity to the problems. These types of scheduling processes are secure by obtaining the solutions which are closest to the optimal solution. Heuristic processor scheduling approaches are used to find the suboptimal solution in considerable computation time. Heuristic-based method provide nearest optimal solution, and as a result of its appearance, computation time in GA is very less. The rest of this paper is organized as follows: Sect. 2 included processor scheduling techniques. Section 3 contains the literature survey of existing methods for processor scheduling. Section 4 contains problem statement. Section 5 concludes the discussion of comparison of different algorithms. Section 6 concludes about the future implementation and outlines the future scope of this work.

2 Processor Scheduling

Processor scheduling is classified into two categories: local processor scheduling and global processor scheduling. Conventional techniques mostly use local processor scheduling. Figure 1 shows the classification of process scheduling.

Fig. 1
figure 1

Classification of processor scheduling

Full size image

2.1 Global Processor Scheduling

Global processor scheduling is grouped into several families depending on scheduling processor techniques. These heuristic scheduling methods are biologically inspired and can be further grouped into several classes of heuristic approaches like an ant colony, bee colony, genetic algorithm, particle swarm optimization, etc.

2.2 Local Processor Scheduling

Local processor scheduling is scheduled upon the single-processor platform and also uses list scheduling to construct a schedule, one cycle at a time, whereas global scheduling processor is scheduled upon multiprocessor platform. In real-time task scheduling problem, the goal of multiprocessor is to meet deadlines, whereas the arrival of tasks is infrequent which has implicit deadlines. To deal with this type of scheduling problem, a global static processor scheduling technique is used.

2.3 Static Processor Scheduling

Static processor scheduling [1, 2] is deterministic scheduling policy. Optimal processor scheduling is used when the job executed at that scheduler should know information about the requirement of the processor and state of processors. The static processor scheduling is divided into two categories: (i) optimal scheduling and (ii) suboptimal processor scheduling. Optimal scheduling reached NP-complete problem, and researchers focused on suboptimal processor scheduling that is classified as approximation and heuristic algorithm. Approximation scheduling technique uses the computational methods for searching of entire solution space for an optimal solution. Heuristic approaches such as ant colony optimization, genetic algorithm, etc. provide feasible solutions to a scheduling problem which cannot give the optimal solution. Suboptimal processor scheduling has two sub-branches: (i) approximate processor scheduling and (ii) heuristic processor scheduling. In multiprocessor environment, the approximate processor scheduling is used to plan the independent tasks where the speed of the processors varies. Approximation scheduling provides the low polynomial complexity to the problems. By using approximation scheduling, we are assured to achieve the optimal solutions. Heuristic processor scheduling approaches find the suboptimal solution in significant time. In heuristic-based approaches, the results of computational time are very optimal and the initial population size is considerably nearby to the solution.

2.4 Dynamic Processor Scheduling

In dynamic processor scheduling techniques [3, 4], the allocated number of processors varies during execution. Dynamic processor scheduling leads to the degradation of performance because of high run-time overhead. Dynamic processor scheduling is divided into two categories: (i) physical distributed processor scheduling and (ii) physical non-distributed processor scheduling. For responsible task scheduling, the physically non-distributed processor scheduling is required, whereas, while using the global dynamic scheduling which is inherent in a single processor and also known as a physically non-distributed, the work involved is to make a decision which should be physically distributed among the processor. The physical distributed processor scheduling is divided into two subcategories: (i) non-cooperative processor scheduling (ii) cooperative processor scheduling. In non-cooperative processor scheduling the individual processor acts as autonomous entities, arrives at decision-making, and makes a choice to select the resources which are independent in nature which affects the decision of the rest system, and in cooperative processor scheduling the goal of each processor is to carry out its own portion of task, whereas all processors are working toward the common system. The same discussion has to be presented in the static case and applies for the dynamic case also. When the taxonomy tree reaches the bottom, we have to consider an optimal [3], suboptimal, and heuristic [3] solutions for the multiprocessor.

3 Literature Survey

There are various research has been done in this field such as C. Jianer and L. Chung Yee proposed a model for processor scheduling in which several alternatives are used a process job and each alternative several machine process the assigned job to them. They invented pseudo-polynomial algorithm [3] to solve optimally two-machine processor problem and also provide a heuristic scheduling algorithm to solve the three-machine processor problem to minimize the completion time for all jobs. X. Yuming and L. Kenli address the task scheduling problems and suggested multiple priorities queuing genetic scheduling [5] for distributed system as well as parallel heterogeneous computing system. They used HEFT approach to search an optimal solution for mapping task of the processor. L. Shih-Tang et al. presented a modified ACO approach DDACS [6] to minimize precedence and resource constraint in multiprocessor scheduling problem. Here, to represent the scheduling problem, a matrix graph is adopted. This matrix graph is used to minimize makespan schedule. A. Hadi Lotfi et al. proposed new coarse-grain genetic algorithm [7] to schedule the tasks and reduce the solution search space and to prevent the speedy convergence between the subpopulation. The initial population is divided into multiple subpopulations and the experimental results of this paper show that the proposed technique will reduce the makespan and it also achieves a better scheduling method in comparison with the other existing methods such as MCP and genetic algorithm. K. Yan and Z. Zhenchao proposed an activity-based genetic scheduling algorithm [8] in which the scheduled tasks run on the heterogeneous grid system network that is signified by directed acyclic graphs (DAGs). First, this approach list all the nodes according to the scheduling algorithm to generate the initial population of GA and it also represents the possible operation sequences so that it reduces the coding space when compared to permutation representation. This approach assigns tasks as activity on the processor to improve quality of the random probability solution and the activity is added to crossover and mutation operator. In Table 1, represent the various techniques proposed by different researchers for solving the problem of processor scheduling.

Table 1 Summary of research development in the field of processor scheduling
Full size table

There are various methods like DSC, MCP, LC, PGA, etc. used for scheduling algorithm. The linear clustering (LC) algorithm uses the recursive grouping of all the nodes in the critical path while zeroing all the edges on the path in one step. In the second step, it schedules the same processor for all partitions that do not execute concurrently. Dominant sequence clustering (DSC) uses the two major ideas: (i) to directly reduce the dominant sequence of the graph and (ii) to create an algorithm with low computational complexity. DSC keeps track of the dominant sequence to reduce parallel time. The complexity order of the algorithm is also reduced. We need to specify certain constraints and definitions to describe DSC such as (i) scheduled: if a processor has been assigned to a node, it should be scheduled; (ii) free: if the processor is unscheduled and all its predecessors are arranged, then the node is free; and (iii) partial free: if it is unscheduled and at least one of its predecessors is unscheduled, then the node is partially free. In this algorithm, the complexity is reduced by confining the range of edges to be zero. Priority-based genetic algorithm (PGA) is based on genetic algorithm, whereas the gene location is used to signify the task node and construct the scheduler among candidate, and the priority of the task node value is used. The proposed PGA method [9] first generates the initial random chromosome, whereas each chromosome is called a gene and each gene is used in the priority node in the DAG structure. According to this technique, it easily validates any encoding permutation to the corresponding scheduler, so that the most recent operator is used for the encoding. Modified critical path algorithm (MCP) explains that the precedence list is prepared on the basis of the “highest bot-level first” ordering. The reason behind is that if the same task has same priority, then to overcome with the critical path the algorithm breaks the task and ties by using the highest priority to the successor tasks and the second highest priority of its successors, and so on. The major objective of this algorithm is to minimize the implementation time so that it becomes more cost-effective. Calculate the cost function of the algorithm in the parallel time environment which is equal to

$${\text{PT}} = {\max} \left( {{\text{ST}}( {nj} ) + Tj} \right) \le {\max} {\text{ST}}( {n_{j} }) + {\max} Ti.$$

This above equation shows that if we minimize the initial time of the last task then we can get the result in the decline of the overall parallel time.

4 Problem Statement

From the available literature, it is observed that performance of the different techniques on a particular scenario exhibits as shown in Fig. 2. In multiprocessor scheduling, the critical problem is how to provide the task precedence relation between tasks and processor so that program’s execution time is minimized. In real time, the most scheduling problems are NP-hard in nature and it is a very complex problem. For that, performance from the start of the algorithm is very poor. This problem is extremely hard to solve. Most scheduling problems are NP-hard [10] in nature. Scheduling algorithms for processors in hard real time are also complex problem. For such large-scale scheduling problem, the performance of state-of-the-art algorithms is very poor. It is observed that evolutionary and swarm-based algorithms exhibit better performance for large-scale combinatorial problems. Our objective is to analyze, study, apply, and implement possible improvements in the said application using evolutionary and swarm-based algorithms. After an exhaustive study of the different research papers and case studies, we like to propose a hybrid system based on ACO and GA with HEFT for task scheduling on heterogeneous nodes and processors. The framework consists of two parts: in the first part, ACO and HEFT which are combined and used for finding the local pheromone and global pheromone, whereas in the second part the result of the ACO and HEFT is taken as input for the GA and applied to the selection, crossover, and mutation process.

Fig. 2
figure 2

Flowchart of hybrid system based on ACO and GA with HEFT for task scheduling on heterogeneous nodes and processors

Full size image

5 Discussion

Evolutionary techniques effectively solve the scheduling problems. These methods apply the skills of evolutionary and it is observed that performance of the different techniques on particular scenario exhibits superiority of GA over traditional heuristic approaches as shown in  Fig. 2. Generally, genetic algorithm is more efficient to solve NP-complete problem of multiprocessor scheduling problems. Here, in this paper, we have discussed some of the processor scheduling algorithms inspired by evolutionary techniques. A comparative study was carried out, and merit and demerit areas are highlighted. Previously, it is observed that increasing the number of task increases the value of makespan as compared to GA [11] and LA [12] methods. After that, coarse-grain genetic algorithm [13] shows that it has the lower makespan value of proposed algorithm than other algorithms. To make this comparison, various algorithms and different parameters have been taken for the execution.

Figure 3 shows that the makespan of MCP is higher than the other five algorithms, whereas DSC, DCP, and MD have the similar makespan, but the number of processors is higher for DSC to achieve the results of MD and DCP algorithm. The GA and PMC have used the same number of processor to achieve the same makespan. The comparison of this technique gave the overall scenario for the processor scheduling environment.

Fig. 3
figure 3

Comparison between different algorithms

Full size image

6 Conclusion

In this paper, a survey is drawn between different traditional scheduling algorithms used in the parallel multiprocessor system. And it is proven that by using the evolutionary technique such as GA we get the better results. Here, in this paper, we proposed a framework for the multiprocessor task scheduling model using ACO and HEFT. The hybrid structure will generate the best possible result in conventional CPU time. And it also forms the suboptimal solution for allocating the tasks to the homogeneous parallel multiprocessor system. Performance of the hybrid ACO and HEFT scheduling algorithm will produce the better result than GA and other traditional approaches for job scheduling in a multiprocessor environment.