Crimson Publishers Publish With Us Reprints e-Books Video articles

Full Text

Research & Development in Material Science

A New Approach for Job Scheduling Using Hybrid GA-ST Optimization

Monika, Krishan Kumar and Himanshu Monga*

Department of Computer Science Engineering, Jan Nayak Chaudhary Devi Lal Memorial College of Engineering, India

*Corresponding author: Himanshu Monga, Department of Computer Science Engineering, Jan Nayak Chaudhary Devi Lal Memorial College of Engineering, India

Submission: November 10, 2017; Published: December 12, 2017

DOI: 10.31031/RDMS.2017.02.000541

ISSN : 2576-8840
Volume2 Issue4

Abstract

In the proposed method, the GA-ST has applied over the number of processes regardless of their size as well as priority. Thus, the scheduling is done without considering their types and performs accordingly. The performance of proposed and traditional techniques is compared over different workloads. This work is to maximize the efficiency of the system with the discovery of efficient operating scenario that can handle the load with effective response time. The experimental results are performed using MATLAB software under different mean arrival time i.e. 24, 26 and 28. From the analysis it confirms that proposed technique of scheduling outperforms the other traditional scheduling algorithms and performs expertly in varying workloads.

Keywords: Job scheduling; FCFS; SJF; GA-ST optimization algorithm

Introduction

Scheduling is a process which is known for its arrangements, controlling and optimizing the works as well as workloads in a process of production. These are basically used to allocate the resources to the processors for the completion of time. Thus, it is considered to be a vital tool in manufacturing and engineering.

Likewise, it has a primary impact on the computing where there are number of jobs and tasks come to the processor for the competition. These tasks are measured as a requests coming from users to the CPU. To manage these requests, there are schedulers available that accomplish this process. The main aim of the scheduling is to maximize the efficiency of the operation while reducing the costs.

The term scheduler can also be described as a hardware that performs scheduling task. Advantages associated with schedulers are: it helps in keeping all the resources of computer unit busy. It also helps in creation of multi-user environment so that more than one user shares the resources of system simultaneously [1]. It also helps in maintaining the high QoS of the system. Scheduling uses the concept of calculation for allocation of task, and also it is a software part in the computer system that helps in increasing the efficiency of computer. The idea behind scheduling is to do multiple works simultaneously and by using only one processing unit. In order to schedule the jobs in several scheduling algorithms have used. Job scheduling algorithms are used to select a particular job for execution from a long queue. The basic job selection technique is based on dispatching rules. FCFS stands for first come first serve and it schedules the process on the basis of order in which jobs are assigned [2]. SPTF stands for Shortest Processing Time First and it is also known as Short-Job-First that is abbreviated as SJF, this algorithm used to allocate the job on the basis of job priority. Largest job first abbreviated as LJF, it allocates the highest priority to the process that need large time for execution. EDF stands for Earliest Deadline First used to allocate the highest priority to that job which have fixed deadline for execution. These techniques are simulated under the results section along with the proposed technique. In the existing techniques, distribution criterion or combination of different techniques was used to obtain minimum response time in completion of the jobs but this method does not perform well in varying load. So the concept of optimization has introduced in this work where the optimum solution is find out or continues the process until the maximum fitness value is not achieved. Thus, proposed technique is compared with the traditional technique to ensure the performance of individual technique. The major focus of job scheduling is to choose the optimum processors in a grid to allocate different jobs. In case of each processor, the creation of job schedulers is totally dependent on management system [3]. In grid scheduling the optimum calculation and process scheduling is major challenge.

Background

From the literature it is studied that many researchers have introduced many algorithms for the job scheduling process. The job allocation depends on many factors as need of those systems are to finish the jobs on or before deadline the systems need to have consider all quality parameters. As the major need are to

    a. Finish jobs on time

    b. Over all waiting time should be less

    c. Over all turnaround time (Finish Time) should be less

By taking these terms under consideration the algorithm name FCFS, SJF, Round robin etc many algorithm had been developed. But still as the number of requirements and the jobs are increasing daily researchers put their efforts to develop new algorithms. In the reference paper the work is done on combining the two algorithms to prepare the hybrid model of scheduling. But those algorithm are valid upto an extent, as the requirements are to updated at some intervals then these algorithm might be unable to schedule the process efficiently. So there is need to find such a solution which can randomly provide solution with much efficient requirement handling approach.

Proposed Work

As there is need to find such a solution which can randomly provide solution with much efficient requirement handling approach. It is proposed that the work can be done on the Swarm intelligence in which many algorithm are existing in the research world. Some Common names those are much popular are Genetic algorithm, Ant colony optimization, Particle swarm optimization. These algorithms are capable to solve the problem that we are facing in existing systems but further enhancements of these algorithms are also possible. So an Advanced Genetic Algorithm with multiple "data updation cases" will be used. This proposed methodology works on combining two optimization algorithms that are GA and ST means genetic algorithm and State Transition [4].

Virtues of using proposed method

a. Combining two optimization algorithms that are GA and ST will help the existing system to get number of solutions for the problem and will select the best out of all.

b. Optimization algorithm will be dependent on fitness function so can be dynamic as many time the requirement change it will be successful

c. Because of random solution approach the best case for all results can be achieved [5].

Methodology

The methodology of the proposed work has shown in the below steps which are followed to acquire the results.

a. Initially, the information regarding each job is attained with their respective deadlines to identify their total time taken to execute the job.

b. Secondly, get the requirements from the user in order to solve the job scheduling or to initialize each process with corresponding jobs.

c. Now apply the proposed algorithm over the schedule process which has done through the existing algorithms.

d. Now in this step, let the proposed optimization technique to find the best random solution for the given problem and attained the best solution.

e. Lastly compare the solution attained through the proposed algorithm with the traditional technique in order to assure the effectiveness of the proposed technique with respect to the traditional technique (Figure 1) [6].

Figure 1: Framework of the proposed work.

Experimental Results

Figure 2: Comparison between traditional (FCFS-SJF) and proposed with 24 mean arrival time.

In this section of paper, the results are acquired after performing traditional and the proposed technique and the obtained results are shown below in terms of mean response time. For the simulation purpose, different average arrival rate i.e. 24, 26 and 28. The traditional techniques which are used to perform comparisons are First Come First Serve, Shortest Job First, 50% of jobs were executed through FCFS and 50% are from Shortest Job first, 75 % of FCFS and 25% of SJF, 10 % through FCFS and 10% through SJF with the proposed technique i.e. GA-ST. the experimental analysis have performed and results acquired from this simulation is presented below [7].

The Figure 2 shows the comparison between different techniques with respect to mean arrival time 24. The comparison has done using FCFS with SJF technique with the proposed GA-ST technique with respect to mean response time.

Firstly, jobs are accomplished using FCFS technique, then SJF technique has applied over the jobs and then distribution of different techniques according to the number of processes is applied. From the results, it concludes that FCFS complete its task with the response time at 4 whereas the distribution of different techniques such as FCFS50-SJF50, FCFS75-SJF25 and FCFS10-SJF10 positioned with highest response time 5 which is not appropriate for the system's efficiency. Alternatively, proposed GA-ST takes least time i.e. consequently with the load i.e. 24 proposed technique outperforms. The graph 3 shows the comparison between different traditional techniques with proposed technique. The experimental analysis is performed using the load 26 with respect to response time. From the Fig it ensures that proposed technique performs effectively in comparison with other traditional techniques. The FCFS technique works not accordingly as the load increases so its performance degrades. Similarly, the other proportional techniques perform in inefficient manner with maximum response time. But consider the shortest job first technique which performs better as compared to other techniques. On the whole, proposed GA-ST technique stands out in terms of rapidly competition of job in the system with 2.5 approx (Figure 3) [8].

Figure 3: Comparison between traditional (FCFS-SJF) and proposed with 26 mean arrival time.

Figure 4 depicts the results acquired from the traditional techniques and proposed technique. Among all the techniques, proposed technique surpasses the other traditional techniques. FCFS does not perform effectively with the increase amount of load in the system. All the processes reach at 28 in the system. The technique with the less response time is considered as the most accurate technique and from the Fig it can be clearly seen that combination of GA-ST performs best and respond within less time i.e. 2.5 approx despite the load in the system.

Figure 4: Comparison between traditional (FCFS-SJF) and proposed with 28 mean arrival time.

Initially, the shortest job collaborated with first come first serve technique was evaluated to consider their performance. Now FCFS with Shortest job first technique performance is evaluated with varying arrival time i.e. 24, 26 and 28 [9].

Figure 5: Comparison between traditional (FCFS-LJF) and proposed with 24 mean arrival time.

The Figure 5 shows the performance of FCFS, LJF, FCFS50- LJF50, FCFS75-LJF 25, FCFS10-LJF10 and proposed GA-ST. From the graph it has shown that among all the techniques, FCFS evaluates results and responds in less time i.e. 4 but other techniques with distribution performs does not appropriately and wrap up its job with highest time taken. Alternatively, GA-ST performed better with less response time i.e. 2.

Figure 6: Comparison between traditional (FCFS-LJF) and proposed with 26 mean arrival time.

The Figure 6 exemplifies the results carried out with 26 mean arrival time. Hence, the results are acquired and shown in the below Fig. It concludes that every technique except LJF completes their task within less response time i.e. below 6 so distributions of processes within FCFS and LJF produces remarkable results but proposed GA-ST perform outstandingly with response time at 2 [10].

Figure 7: Comparison between traditional (FCFS-LJF) and proposed with 28 mean arrival time.

The Figure 7 evaluates their performance with the load of 28. From the results acquired it ensures that proposed technique surpasses all the traditional techniques with least response time in responding and completion of task.

The Figure 8 portrays the performance of traditional techniques and proposed technique with mean arrival time 24. From the results acquired, the GA-ST performs better and responds in less time in comparison with other techniques where all of them stable at 1700 approx response time which means that the existing techniques are not efficient for the system [11].

Figure 8: Comparison between traditional and proposed techniques with 24 mean arrival time.

Conclusion and Future Scope

This work studies the performance of different traditional techniques which uses the policies of equal distributions among three job scheduling algorithms such as First Come First Serve, Shortest Job First and Largest Job First. These algorithms are combined together with one another using equal or unequal distribution. For the comparison purpose, these algorithms are compared with the proposed GA-ST algorithm. Comparing two job policies such as FCFS-SJF and FCFS-LJF, it has found that SJF performs better than LJF as the mean repose time with LJF varying from 6 to 8 which is quite higher and inappropriate for the system. Another factor which is considered in this work is with the increase in load the variability in service demand times is also increasing. Among all the traditional techniques SJF surpasses the other methods. Alternatively, the traditional methods have compared with the proposed GA-ST technique and it concludes that proposed technique outperforms the SJF also yielding the lower mean job response time as it was expected. Though, SJF performs better but proposed method performs well at high service demand variability. As the proposed technique has the capability to find best random solution for solving given problem so it works effectively with existing algorithms of job scheduling. Moreover, it is considered as the fairest as it performs on both short jobs as well as large jobs in queues. Additionally, there is slightly increment in average response time with respect to increase in workload X. On the whole, LJF scheduling algorithm performs worst not only alone but with combined FCFS as well [12-17].

The proposed method can be extended with recent optimization algorithms with minimum response time. Moreover, the jobs which have hard deadlines can be considered in future to produce most efficient results.

References

  1. Skenteridou K, Karatza HD (2017) Job scheduling in a grid cluster. IEEE/ ACIS 16th International Conference, pp. 535-537.
  2. Yadav K (2013) Job scheduling in grid computing. International Journal of Computer Applications 69(22): 13-16.
  3. Bhoyar AA, Dharmik RC (2015) Design and implementation of job scheduling in grid environment over IPv6. IJCSMC 4(4): 243-250.
  4. Dipti S, Mittal P (2013) Job scheduling algorithm for computational grid in grid computing environment. IJARCSSE 3(5): 735-743.
  5. Prajapati HB, Vipul AS (2014) Scheduling in grid computing environment. IEEE.
  6. Sakellariou R, Yarmolenko V (2006) Job scheduling on the grid: towards SLA-based scheduling. High Performance Computing Workshop, pp. 207-222. Kathrine J, Mansoor IU (2012) Job scheduling algorithms in grid computing- Survey. IJERT 1(7): 1-5.
  7. Balajee M, Suresh B, Suneetha M, Rani VV, Veerraju G (2010) Premptive job scheduling with priorities and starvation cum congestion avoidance in clusters. ICMLC.
  8. Jorge Manuel GB, Belmiro Daniel RM (2009) Dynamic job scheduling on heterogeneous clusters. ISPDC.
  9. Yichao Yang, Yanbo Zhou, Zhili Sun, Cruickshank H (2013) Heuristic scheduling algorithms for allocation of virtualized network and computing resources. JSEA 6(1): 1-13.
  10. scheduling algorithms for allocation of virtualized network and computing resources. JSEA 6(1): 1-13.
  11. Jing Mei, Kenli Li, Keqin Li (2014) A resource-aware scheduling algorithm with reduced task duplication on heterogeneous computing systems. The Journal of Supercomputing 68(3): 1347-1377.
  12. Suraj Pandey, Siddeswara MG, Rajkumar B (2010) A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments. 24th IEEE International Conference on Advanced Information Networking and Applications pp. 400-407.
  13. Ruay-Shiung C, Jih-Sheng C, Po-Sheng L (2009) An ant algorithm for balanced job scheduling in grids. Future Generation Computer Systems 25(1): 20-27.
  14. Chawla M, Kriti Singh, Chiranjeev Kumar (2016) Attitudinal data based server job scheduling using genetic algorithms: Client-centric job scheduling for single threaded servers. Contemporary Computing (IC3).
  15. Mondal PK, Nazmul Ahsan AMM, Quayum KA (2013) An approach to develop an effective job rotation schedule by using genetic algorithm. EICT.
  16. Limwanich B, Wongsathan R (2011) Efficiency improvement of job scheduling by using Genetic Algorithm: A case study in electronic industry. IEEM.
  17. Shih-Pang T (2011) Job shop scheduling based on ACO with a hybrid solution construction strategy. FUZZ.

© 2017 Monika, et al. This is an open access article distributed under the terms of the Creative Commons Attribution License , which permits unrestricted use, distribution, and build upon your work non-commercially.