Printer Friendly

Optimized job scheduling approach based on genetic algorithms in smart grid environment.

Abstract. The advances in communications and information technologies have been playing a major role in all aspects of our lives. One of those majors' aspects that affect our daily lives is the power grids which lead to what we call Smart Grids. One of the major challenges in these grids is to optimize the consumption and resources. This paper presents an optimized job scheduling approach using genetic algorithm which provides a minimum cost for completing different tasks in a grid environment. In grid environment different independent appliances are sharing the same resources depending on the availability of resources and the need of these appliances to run. There are different job scheduling approached starting from typical strategies, Ant Colony (AC) and Genetic Algorithm (GA). In this paper we present a cost optimized Genetic Algorithm approach for appliances job scheduling by considering different parameters like job duration time, the resources availability and the job priority to start. The proposed approach is tested using a simulator written in c++ programming language. The results show that the total saving in cost is better than the previous approaches.

Keywords: Smart Grid, Job Scheduling, Genetic Algorithms, Sensor networks.

1. Introduction

Grid Computing technologies are considered as a new evolution in distributed heterogeneous systems [5]. It focuses on sharing and utilization of the available resources to different applications. It is used to solve complex problems such as scientific, engineering and business. Resources in grids are dynamic and the applications (appliances) can run at any time. Hence, the job scheduling is an important issue in grids. Due the nature of appliances connected to the grid, traditional task (job) scheduling is a time consuming, while the introduction of genetic algorithm to take the task of scheduling will shorten the task scheduling time and the cost and improvement of the grid performance [6].

Using electrical devices that consume electricity to run their operation, such as Dryer, Dishwasher, Air conditioner, Coffee maker embedded with sensors. These electrical devices have a diversity of power consumption amount and even the same device with different programs have different power consumption and if scheduled according to time of starting in, it will reduce the final cost. Each device is attached to a wireless sensor to gather information share it with the grid, these sensors should be deployed carefully in order not to impair the lifetime [16] of the grids which is represented by grids.

Each device has its own duration time and amount of energy consumption level for each run. Examples of appliances and the amount of power need to run in a specified duration time are shown in table 1[10].

According to [12] rechargeable battery (PHEV) can be considered as an appliance because it needs to be charged when empty.

Different appliances with different power consumption and different priority to run are the main components of grids. These appliances need to run in an optimized manner to make sure all appliances got the required power to run with the minimum cost.

In Grid environment jobs are scheduled by using traditional scheduling algorithms to achieve the goal of cost minimizing, some traditional scheduling algorithms are: First Come First Served (FCFS) and Shortest Job First (SJF) which will not perform well with grid environment. Modern algorithms are introduced to perform job scheduling in a professional way; it is Genetic algorithms.

Genetic algorithm is technique that used in computing field for propose search to find the best solution that are known as exact or approximate solution to approve the optimization and search problems. The genetic algorithms are categorized as global search heuristics, the operation model based on biological evaluation such as selection, crossover, and mutation.

The genetic algorithms approach is usually consisting of the following steps:

--Creation an initial population

--Computing the fitness of each individual

--While (not stopping condition) do

** Select parents from population.

** Execute crossover to produce offspring.

** Perform mutations.

** Compute fitness of each individual.

** Replace the parents by the corresponding offspring in new generation.

--Repeat

2. Related work

[2] have proposed system to monitor and control an office environment that connected with smart grid to schedule the tasks according to policies defined by the user.

They applied and tested the system in a living lab environment. The results showed show an interesting economic savings of an average of about 35%. And another interesting result is the power saving is about 10% to 20% in building that also contains renewable generation plants.

The authors in [12] proposed frame work for scheduling residential energy consumption. Authors claim that this proposed framework helps to decrease the cost of energy bill and minimize the waiting time to operate each device. The period that taken by authors to study the consumption is between September 1st 2009 to December 31st 2009 (122 days approximately four months). They used in their experiments variable number of electrical devices for each day from 10 to 25, which can be categorized into two parts: fixed consumption devices like lighting and electric stove the other part is varying consumption energy such as dishwasher and PHEV.

The results showed reducing the user cost with reduction of the peak time to average ratio in load demand.

The authors in [1] studied an offline scheduling task that depends on the user to send a request to run his appliance during a time slot and the proposed approach will find the best and the minimum cost for his request. The objective of this problem it is able to schedule all requests with minimum total electricity cost. For this reason, they proposed polynomial time offline algorithm in order to achieve the optimal solution and it is able to optimize the time complexity to O (n T log n) where the time complexity before the optimization is O (n2T).

In [13] the authors proposed new technique to group a set of jobs that have common features and then schedule these jobs by using an enhanced genetic algorithm, the group process depends on some features that such as mobility, resource availability and job completion time. The results show a performance improvement in job scheduling and minimize the job completion time

In [15] the authors developed new efficient method to get the fairness requirement for any operating system. They proposed a Distributed Weighted Round-Robin approach that based on genetic algorithms to distribute the tasks for CPU in a multiprocessor computer in a fair way. The scheduling complexity problem dependents on the number of processors (p), task processing time (Ti) and precedence constraints.

In [17] the authors mentioned that Genetic algorithms can be used for searching good solutions for different kind of problems, although this paper focus on find good solution for tailbiting codes, they give good indication about Genetic algorithms and their use in searching optimal solutions.

The experiments are applied on two computers: the first is sun ultra on 140 MHz with 64 MB RAMS and the second is Alpha station 600 on 333MHz and 256 MB RAM.

The Test problem consist with two problems are problem with 452 tasks which scheduled onto 20 processor and problem with 473 tasks which scheduled using 4 processors. They claimed that proposed approach shows achieve accurate proportional fairness and high performance for a diverse set of workloads.

In [8] the authors investigated the genetic algorithm (GA) in order to optimize sensor node's energy consumption. They used multi-objective algorithm that establish optimal number of sensor clusters with cluster heads and decreasing the cost of transmission.

The parameters that used to compute the performance of GA are affected through number of factors such as: the population size, the probability of mutation and crossover, and the method of replacement. Tables 1 and 2 indicate the WSN parameters and final GA parameters, respectively.

They used MATLAP simulator to implement number of experiments with different values of these parameters. The experimental results showed that their approach can generate optimal clusters and minimizes the cost of transmission.

In power grid, generation capacity is considered as important topic to meet the peak hour load demand. The smart grid has been proposed by update the traditional grid to achieve new type of electricity grid with more reliability economically and sustainability electricity service.

The load demand through on-peak hours is much larger than the load demand through off-peak hours, so when the load demand is high, the power consumption cost will be high.

The previous work it was achieved one objective of this problem with minimize customer's cost. After that the authors in[Melike E. and Hussein M. 2011] resolved the load scheduling problem with multi-objective optimization problem (CMOP).

And they evaluated the performance of two algorithms are: load scheduling with EA (LSEA) and load scheduling with E-approximate (LSEA), that are implemented by using Matlab 2011b software on computer machine with certain specification, the capacity of CPU is 3.4 GHZ and 4 GB of the RAM memory.

The results showed the objectives that optimized like minimize the energy consumption cost and maximize the certain utility.

3. System Description

This paper considers a smart grid that connects a set of inelastic appliances power supply. The power supply in this system is of two types the ordinary power supply that came from Generation Company, and a battery bank at the consumers' end for energy storage. Because of the continuous charging and discharging of battery bank the operating life will be affected. To overcome this limitation a controller can be used to control and regulate the charging process in the battery bank. Also an inverter is used to convert the DC in battery to an AC before supplying the appliances. A detailed description of system component is discussed in the following subsections.

3.1 Grid power supply

This power supply is the traditional power supply comes through wires to be used by consumers. This power supply cost is calculated by a smart meter as a part of the grid, and this power supply has two main prices; peak hours and off-peak hours.

3.2 Battery Bank

The battery bank is used in the consumer side to store power during the off--peak time and this power is used by the appliance as a priority at the peak time. We assumed that this power supply is fully charged at the first time used and the price of this power supply is added to the cost of the consumer power cost with an assumption of 10 years life of battery.

Most of the appliances met the amount of power in this power supply and as mentioned this power supply will be recharged at off-peak time with low price power supply, the discharge amount is limited to maximum of 2/3 of the power stored in this power supply.

3.3 Energy Demand

This proposed approach considers the power demand to at a particular time instance with a particular amount. If the demand is at off--peak hours it will be supplied by the grid on the other hand if the demand is at peak hours the priority to supply is for battery if the amount is partially or totally covers the demand otherwise the grid will cover the remaining demand or the whole demand depending on the battery status.

This optimization approach runs for 24 hours power demand. The main goal of this approach is to minimize the total cost so at any time the demand is requested the power supplies should give the demand requests either by battery or the grid power supply as discussed before.

4. Proposed Optimization Algorithm

Evolutionary Algorithms (EA) are a group of optimization and global search procedure which use the main three principles of natural evolution: natural selection, reproduction and diversity of the species [4]. Genetic Algorithm (GA) is part of Evolutionary algorithms which use the probabilistic rule translation, i.e stochastic algorithms.

This paper uses Genetic algorithms [14] to minimize the total cost of running a set of appliance in a home by creating the best order string (child) of running appliances.

In our work we consider the power cost as a real-time task scheduling problem where each task has a starting time (release time), duration time and end time. The task will start at starting time and take a duration time running and finishes at stop time, during this process the cost is calculated and added to the total cost for all appliances.

As finding the optimal solution in our proposed approach is an NP -hard because you need to find all possible solutions and find the best. Thus in our proposed approach we cut the searching space by using the Evolutionary Algorithms (EA) especially the Genetic Algorithms (GA); discussed before; a global probabilistic search method based on natural selection and the population genetics, is used in [3].

The main goal of our job scheduling approach is to minimize the power cost after running the appliances in a period of time; in general the use of Genetic Algorithms (GA) is done in five steps.

1. Initialization

An initial population is randomly generated; the contents of each generated string should be unique. Each string is generated depending on some variables such as completion time, priority of execution and delay of starting.

2. Fitness functions (Evaluation)

At this step each string initialized in the previous step is evaluated. As the objective of our approach is to minimize the cost depending on the order of appliances run and completion time we used fitness function of time developed and used in [6].

3. Selection

At this step a selection operation is executed to select the higher two strings to be the parents for generating the new string (child), for selection the traditional roulette wheel selection is used to select the best strings (parents).

4. Crossover

At this step two parts of each string are exchanged to form new and hopefully best parents. Our proposed approach uses Blend crossover (BLX)[7]. Figure 1 shows an example of crossover operation.

[FIGURE 1 OMITTED]

5. Mutation

This step is used to prevent the parent selection from randomness and local minimum.

[FIGURE 2 OMITTED]

It works as a background step to ensure the diversity of genetic population. There are various types of mutation; Flipping, Interchanging, Reversing, Uniform mutation and non-uniform mutation. This paper uses non-uniform mutation used in [4]. Figure 2 shows an example of mutation operation.

The proposed work stars by collecting the events (jobs) from appliances through sensors to generate the initial populations then these populations are used by genetic algorithms and steps discussed before to find the best and optimized order of events to be run depending of a set of constraints discussed before. The new child generated from initial parents is tested and evaluated in the next section.

5. Experimental Results and analysis

In this section the performance of the proposed scheme is discussed by running different experiments. The main performance metric used to evaluate the proposed scheme versus the other schemes is the total cost in Jordan Dinar (JD) for running the home appliances over different periods of time.

Table 3 summarizes the parameters used during the simulation study. Our simulator is written using C++ programming language running under Ubuntu operating system.

In this section we will discuss the results for the proposed scheduling scheme against the schemes proposed in[8] [ Firas Al Balas et al. 2016]

[FIGURE 3 OMITTED]

The comparison is done by running the proposed scheme on different scenarios including changing the number of appliances and also make some appliances repeat its power request more than once a day. The scenarios cover the average and high demand on power supply at homes to make sure that the proposed scheme is able to run in high power demands.

Figure 3 show the result of the first experiment which include the comparison between the proposed scheme and results from [11]. This scenario runs using 6 devices running during off-peak and peak. The results show that there is a large saving in cost especially when run for a long time. This cost reduction is due to using genetic algorithms for scheduling by finding the best order of appliance running period that avoids peak time while trying to get benefit from battery bank during the peak hours.

Figure 4 show the result of the second experiment which include the comparison between the proposed scheme and results from [18]. In this scenario the 6 devices run during off-peak and peak hours with the support of Solar Photovoltaic (PV) Batteries in comparison with the proposed scheme. The results show that the proposed scheme gets a distinguished cost reduction because of using the best appliance running order without affecting the request time. This is also due to the optimization of off-peak time and battery bank in the proposed scheme.

[FIGURE 4 OMITTED]

Figure 5 show the third experiment results by comparing the traditional with proposed scheme by adding more devices to the scalability of the proposed scheme.

[FIGURE 5 OMITTED]

It can be noticed that the increase of cost when doubling the number of devices is reasonable in the proposed scheme where in traditional power consumption it increases in high rates. The reason why the proposed scheme acts well in this scenario is the use of genetic algorithm to find the best order of device during the off-peak and using the bank battery.

Figure 6 shows the experiment results by making high demand on power by allowing each device to make up to requests at the same day during off-peak and peak hours. This scenario is done to make sure that the proposed scheme can coup with the high demand and able to schedule these demands in a way with low power consumption which will at the end will reduce the total cost.

[FIGURE 6 OMITTED]

6. Conclusion

In this work, a study of using genetic algorithms to schedule the appliances requests for running during off-peak and peak hours. The proposed scheme runs over 210 days for different number of devices and find the total cost at each time.

This proposed scheme shows an enhancement in saving the cost of power supply on different scenarios starting from changing the number of devices and repeating the demand request.

This proposed scheme proves that the correct use of scheduling the appliances at home will give a high saving in power consumption which at the end will save the cost.

7. Acknowledgement

This research is supported by Jordan University of Science and Technology / faculty of research. Grant number 74/2016

References

[1] Burcea, M., Hon, W.-K., Liu, H.H., Wong, P. W. H., & Yau, D. K. Y. "Scheduling for electricity cost in smart grid.: In P. Widmayer, Y. Xu, & B. Zhu (Eds.), Combinatorial Optimization and Applications, Vol. 8287, pp. 306-317. Zurich: Springer., 2013.

[2] Georgievski, I., Degeler, V., Giuliano, G., Lazovik, A., Aiello, M., "Optimizing Energy Costs for Offices Connected to the Smart Grid", IEEE Transactions on Smart Grid, Vol: 2, Issue: 4, pp: 2273-2285, 2012.

[3] Goldberg, D.: Genetic algorithms in search, optimization, and machine learning, Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA [C]1989

[4] Gundi, M., Rajarajeswari, R.. "Smart Grid Cost Optimization Using Genetic Algorithm." International Journal of Research in Engineering and Technology, Vol.: 3 Special Issue: 07, 2014

[5] Ian, F., Carl, K.. "The Grid: Blueprint for a New Computing Infrastructure edited by I. Foster and C. Kesselman, 279-309. San Francisco: Morgan Kaufmann 1999.

[6] Jiang, G., Wu, X., Yang, H., "Task Scheduling based on Genetic Algorithm in Mobile Grid" International Conference on Computer Science and Service System pp. 719-722 11-13 Aug. 2012.

[7] Masato, T., Hajime, K., "A Crossover Operator Using Independent Component Analysis for Real-Coded Genetic Algorithms ", Proceedings of the IEEE Congress on Evolutionary Computation Seoul, Korea, pp 643-638 May 27-30, 2001

[8] Melike, E., Hussein, M., "Wireless Sensor Networks for Smart Grid Applications." Saudi International Electronics, Communications and Photonics Conference (SIECPC). PP. 1-6, 2011.

[9] Melike E., Husseink, M. "Using wireless sensor networks for energy-aware homes in smart grids." IEEE Symposium on Computers and Communications, pp. 456-458, 2010

[10] Rainer S, "Synergy Potential of Smart Appliances" d2.3 of wp 2 From the Smart-A Project, 2008., University of Bonn, March 2009.

[11] Melike, E., Hussein, M.O "Wireless Sensor Networks for Domestic Energy Management in Smart Grids." IEEE 25th Biennial Symposium on Communications: pp. 63-66. 2010

[12] Mohsenian, A., Leon, A.."Optimal Residential Load Control With Price Prediction in Real-Time Electricity Pricing Environments." IEEE Transaction on Smart Grid.; vol. 1:pp. 120-133, Sep. 2010.

[13] Sarvanan, G. Gopalakrisanan, V., "Improved Genetic Algorithm for Group-Based Job Scheduling in Mobile Grids." Journal of Theoretical and Applied Information Technology, Vol. 67 No.2, 2014.

[14] SungHo, C., Taeweon S., HeonChang Y. "Genetic Algorithm based Scheduling Method for Efficiency and Reliability in Mobile Grid." IEEE Transactions on Parallel and Distributed Systems,pp.928-934, 2009.

[15] Tong, L., Dan, B., Scott, H.. "Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin." Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, pp. 65-74, 2009.

[16] F. Frattolillo, "A Deterministic Algorithm for the Deployment of Wireless Sensor Networks", International Journal of Communication Networks and Information Security, Vol.8, No.1, 2016.

[17] P. Remlein, D. Szlapka, "Genetic Algorithm used in Search of good Tailbiting Codes", International Journal of Communication Networks and Information Security IJCNIS, Vol. 1, No. 3, December 2009.

[18] F. Al Balas, Wail Mardini, Yaser Khamayseh, Dua'a Ah.K.Bani-Salameh (2016), "Improved Appliance Coordination Scheme with Waiting Time in Smart Grids," International Journal of Advanced Computer Science and Applications, vol. 7, no. 4, pp. 16-30, 2016

Firas Albalas, Wail Mardini and Dua'a Bani-salameh

Department of Computer Science, Jordan University of Science and Technology
Table 1. Energy consumption and cycle durations of the appliances. [10]

Appliance     Energy consumption  Duration (min)
              (kWh)

Washer        0.89                30
Dishwasher    1.19                90
Dryer         2.46                60
Coffee Maker  0.4                 10
PHEV          9.9                 60
AC            1.5                 60

Table 2. WSN and GA parameters used in [6]

                         WSN PARAMATERS
Parameter                                Value

Node distribution                          30*30 [m.sup.2]
Initial population size                     4
Bit for representing every sensor nodes     3
Battery capacity                           (0,15)
Location of sink node                      (0,0)
Number of sensor nodes                    100, 200, 400,
                                          600

                         GA PARAMATERS
Parameter                                Value

Mutation rate                              0.004
Crossover rate                             0.7
Max Generations                         1000

Table 3. WSN and GA parameters used

Parameter              Value

Simulation Time        20-210 days
Number of devices       4, 6 devices
Power Prices (Jordan)  On peak 0.62 $/Kwh
                       Off Peak 0.52 $/Kwh
COPYRIGHT 2017 Kohat University of Science and Technology
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2017 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Albalas, Firas; Mardini, Wail; Bani-salameh, Dua'a
Publication:International Journal of Communication Networks and Information Security (IJCNIS)
Article Type:Report
Date:Aug 1, 2017
Words:3740
Previous Article:Detection of illegal traffic pattern using hybrid improved CART and multiple extreme learning machine approach.
Next Article:Quantum phase shift for energy conserved secured data communication in MANET.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters