heuristic algorithm

With the advent of Internet of Things (IoT) applications, the number of processing requests has dramatically increased. In order to response to these requests, the Fog-Cloud environment has recently been introduced as a hybrid computing system. Although, the Fog-Cloud is a very promising environment for processing IoT requests, it faces many challenges. In this regard, task scheduling problem is one of the key challenges which has a significant impact on the efficiency and overall system cost. Motivated by this, in this paper, we first present a multi-objective optimization model including makespan, energy consumption and processing cost for scheduling tasks in an integrated Fog-Cloud environment. Then we propose a heuristic algorithm to efficiently solve the model. Simulation results demonstrate that our proposed algorithm significantly reduces all the aforementioned metrics and can achieve a good tradeoff between them. Specifically, the proposed algorithm improves the objective function around 98%, 43% and 32% in comparison with the random, genetic and the power of two choices algorithms, respectively.

Task Scheduling (TS) poses a challenging problem in distributed systems from multiple perspectives such as the uncertainty in resource capacity and topology, heterogeneity of processors, computational complexity as well as theoretical performance analysis. To reach timely solutions, current approaches, whether classic approaches, which are based on list scheduling, or intelligent approaches, which are generally based on evolutionary algorithms, either impose extra constraints or ignore some aspects of the reality of this problem. Furthermore, they generally depend on numerical performance evaluation and lack the ability to reach clear theoretical conclusions. Here, we address the problem of theoretical analysis by proposing a new paradigm based on system engineering. This new modeling paradigm is promising due to its extensive theoretical developments. In its general form, TS is inherently nonlinear because of its many nonlinear constraints. In this paper, we demonstrate how TS can be mapped via nonlinear state space and, through theoretical analysis, show stability of the resulting system. Then, a suitable transformation is devised to convert this model to linear switching state space with some nonlinear constraints. It is shown that the resulting model can suitably represent uncertainty in resource capacity. We then present a systematic method to determine control vectors based on this model. Finally, the proposed method is compared against HEFT (heterogeneous earliest finish time) scheme on several random experiments and demonstrate comparative performance.