Back
 CS  Vol.7 No.4 , April 2016
Trust Based Meta-Heuristics Workflow Scheduling in Cloud Service Environment
Abstract: Cloud computing has emerged as a new style of computing in distributed environment. An efficient and dependable Workflow Scheduling is crucial for achieving high performance and incorporating with enterprise systems. As an effective security services aggregation methodology, Trust Work-flow Technology (TWT) has been used to construct composite services. However, in cloud environment, the existing closed network services are maintained and functioned by third-party organizations or enterprises. Therefore service-oriented trust strategies must be considered in workflow scheduling. TWFS related algorithms consist of trust policies and strategies to overcome the threats of the application with heuristic workflow scheduling. As a significance of this work, trust based Meta heuristic workflow scheduling (TMWS) is proposed. The TMWS algorithm will improve the efficiency and reliability of the operation in the cloud system and the results show that the TMWS approach is effective and feasible.

Received 29 February 2016; accepted 26 April 2016; published 29 April 2016

1. Introduction

In recent years the resources can be accessed from anywhere at any time through Internet without any burden. Cloud computing is an emerging trend for information access in parallel and distributed computing. It offers services to the end users that enable the requirement of the system to perform tasks without the knowledge of resource management and maintenance [1] [2] . Here the information is scalable and dynamic. Based on the services the parameters are included to give efficient services with less cost, investment and maintenance. The execution of the process is based on the workflow which consists of workflow scheduling. It maps the tasks with its available resources to meet some predefined criteria.

To exploit the performance of workflow for execution, it can be moved to cloud services and scheduled with multi-objective. Meta-heuristic approaches have been included for workflow scheduling. The end users can manage or develop the application in cloud environment where the resources are maintained and managed by it [3] .

In parallel and distributed systems, scheduling of task is a challenging one. It is based on trust accuracy and the resource status. The provider will manage the resources in central database which is to be scheduled for quick access. Nowadays, the providers are rapidly increasing in commercial cloud environment [4] where they are focusing on their revenue but not on user’s requirement which leads to untrustworthiness of the resources. In solving large-scale issues occurring through Internet and providers, self-cloud providers focus on their private resources information [5] .

Each provider will have private function to interact and design the process to use in different ways. Depending on the GAIN and LOSS mechanism outcome is evaluated. The cost of the mechanism will be varied according to the design of the provider. There will be a conflict between the providers. To overcome these issues truthful mechanism is implemented to make the providers tell the truth of the resources. For computational services workflow application is an attractive paradigm. In commercial multi-cloud environment the workflow scheduling is reported using mechanism design. An efficient equipoise of scheduling is required in a response time [6] .

To meet the requirements of the industry services the integration of the system is carried out. The services are extended as supply chain environment and the services are promising technique in cloud environment [7] [8] . So far, the system is collaborative in the industry which provides the resources through Internet as virtualized and enthusiastically scalable service. Some integrated services are hard to be in composite service for business process. In the system the workflow is integrated as services and provides process management of the organization [9] . Trust service oriented workflow scheduling (TWFS) is a trust based scheduling to allocate work flow task to the cloud services.

In many large-scale systems the scheduling algorithm is integrated with new style and development. Most of the algorithms are based on time and cost but TWFS is focused on the time, cost and trust on cloud environment. The services are operated and owned by the organization in cloud environment. The workflow application operation often poses bullying by inherent insecurity and irregularity in the system [10] . Scheduling is more important in services environment and the failure may occur by the providers without interaction; they may cause failure to the system [11] . Trust between providers is essential and TWFS model will optimize the trust. It is an NP-hard problem and it has some policies to balance the requirement at a time in the cloud environment. The parameters of WFS like deadline-Markov Decision Process (MDP), LOSS and GAIN are taken in this model.

In this paper, the strategies of scheduling in enterprise system are developed to optimize the trust factors, cost and time, in order to specify the issues of TWFS and WFS model in a reliable way and to meet the integration necessities of ES. The rest of this paper is structured as follows. Section 2 reviews the literature of TWFS, WFS and Trust strategies. The multi-objective workflow model, TWFS model, WFS model and heuristic model are discussed in Section 3. Section 4 presents the proposed work TMWS and the scheduling model algorithm is presented Section 5. The results and the performance analysis are discussed in Section 6, while the conclusion and future work are in Section 7.

2. Literature Survey

In this section, the literature survey of scheduling is categorized in three main areas: WFS, TWFS and Trust strategies and computing [12] .

2.1. Workflow Scheduling (WFS)

In unrestricted network environment, the services are public source to every organization [13] . Without considering the monetary cost and user requirements the best effort based scheduling is designed to minimize the time of scheduling execution. In this scheduling max-min, earliest-finish-time and min-min algorithms are introduced [14] . In cloud computing the scheduling process cost is minimized and the scheduling budget is based on the GAIN and LOSS. It start up with the performance and then with the switching. The services are optimized for different criterion and mainly focused on time and cost factors only [15] .

Deadline-MDP is considered to minimize the execution cost while meeting deadline; it consists of cost based WFS algorithm to distribute the deadline equally over each task partition. Deadline bottom level (DBL) determined each level of the task by maximum finishing time and finishing time as deadline top level (DTL); as time interval of the deadline is segmented. Unfortunately, event failure may occur during the processing of workflow applications. Therefore the cloud services must strongly be trustworthy services. TWFS model is developed with the expectation of the enterprises and to balance the services in the environment with better performance.

2.2. Trust Service Oriented Workflow Scheduling (TWFS)

In cloud network, the scheduling of the workflow consists with the WFS. TWFS model is designed with the factors trust, cost and time. The time and cost factors are same as WFS and the trust is based on the objective related to direct and recommended trust [12] . Combining both the trusts with the objectives provide an efficient trust metric that too give a reliable services to the users in the cloud environment. The trust is evaluated based on the weight, rating by user, and similarity between users. The time and cost of execution is calculated. The evaluation takes place by using max-min algorithm to satisfy the objective. The cost is saved in descending order as per the time and list is in ascending order as per cost.

2.3. Trust Strategies and Computing

Trust is an essential part in the workflow scheduling. It provides trust between the providers to avoid the issues in cloud environment [16] . Secure access of resource transaction to users take place with rating the producers by users. Based on feedback rating the trust is evaluated by considering the authority model and the mathematical form in another way. Research work on trust consisting of trustworthy sharing peers has been done.

The Eigen Trust algorithm is used to work out the global trust value based on transaction success. Binary rating model maintain the rating of users and by Dempster-Shafer belief theory the subjective rating is evaluated. To enhance the execution time WFS is proposed. The trust aggregation is taken as direct trust and QoS values envisaging by Collaborating filtering (CF) model to service as recommendations trust [17] . It is well known to all organization environments like health care, education.

The recommendations are based on user rating; it is effective for service structure and miscellany. In cloud services trust issue may occur in workflow application from time to time. Only few trust factors are taken in this application. The proposed scheduling algorithm consists of trust metrics with factors, time and cost. Compared to the existing survey the proposed model will provide better performance and access to the end users in cloud environment.

3. Structural Model

The problem related to the TMWS models is discussed in this section, which includes TWFS, WFS, multi-objective workflow modeling and heuristic modeling. Workflow application is modeled as a directed acyclic graph. A cloud directory service is designed to store the resources details and content. The TMWS model is intended to decide the resources based on the time, cost and trust of the services to end users. In mixed service oriented system, understanding of trust is inaugurated with the context role, flexible collaboration and interaction types. The trust metric has been taken into consideration in this work with related concepts.

3.1. Problem Statement

The application workflow representation in DAG denoted the components as and the resources as. The output of the mapping takes place as per the execution of DAG in cloud environment.

3.2. Approach

The approach we have taken to solve the issues in scheduling take place with components. The execution time, execution cost and the trust metrics are evaluated in TWFS and WFS approach are defined as below,

(1)

(2)

(3)

3.3. Notations

In order to put into words the notations are defined as follows:

Ef-Earliest finish time of task execution

Ls-Latest start time of execution task

Lf-latest finish time of task execution

Di-Duration of tasks execution

Es-Earliest start time of task execution

DT(Si)-Direct trust of the ith service

RT(Si)-Recommended trust of the ith service

wi-Weight of trust service for ith service

-Maximum cost value of the ith service

-Minimum costvalue of the ith service

-Costs for ith service

T, C-Time & Cost constraint of task execution

Tr-Trust constraint of task execution

3.4. Heuristic Approach

In scheduling, heuristic approach is applied to find the optimal mapping of resource [18] . Estimation of time and cost are considered with the resource components for scheduling. The workflow of this approach will plot corresponding module instead of choosing minimum constraint. Based on minimum values the scheduling will execute in priority wise. In order to improve the efficiency of scheduling and its performance, high suffrage value has been chosen for execution process. Based on current resources availability the mapping is done in real environment.

In distributed system, using heuristics the complexity is hiding in the workflow scheduling and NP problem is take place. By using the methods like programming, graphical method and optimization method; the scheduling problem is transformed to single objective optimization problem. It is optimized based on the GAIN and LOSS schedule. The execution cost is minimized while the deadlines are met in workflow task by using bi-criteria workflow scheduling method. As well in genetic algorithm time complexity is high, selection of solution from pareto will remain the same problem. The pareto solution is decided by the user based on the constraints and weight. To analyze the objectives like make span, cost, energy and reliability the algorithm is modified [19] .

In cloud, the capacity of computation is extended with resources to satisfy application deadline. In workflow scheduling heuristic is provisioning to meet stated budget. Dynamic load of information is not supported in all static algorithms. In commercial cloud the information provided by the providers will be doubtful, as deliberated before. In real environment to balance the issues occurrence in the system; different existing models have to be recalled for designing proposed model to provide better performance. In presence of selfish provider in commercial environment, efficient trust mechanism is proposed for dynamic workflow scheduling. The proposed algorithm will assign the resources to the workflow application based on the task and resources priority. The TMWS work provides a better solution than existing and analyzed to ensure efficient system. To find the overall component of the trust and flow of trust, schedule is performed as shown in Figure 1.

4. Trust Based Meta-Heuristics Workflow Scheduling (TMWS) Model

In Section 4, the scheduling of workflow application system is defined with the TMWS model to improve the performance analysis of strategies like time, trust and cost based on resources availability in cloud environment.

4.1. Trust Evaluation

In distributed system we present a Trust based Meta-Heuristics Workflow Scheduling algorithm to maintain the reliability services and to avoid the discrete events workflow application failure. Equation (1) takes place the metrics of trust with the recommendation and direct trust. wi specify the weight of trust metrics. Recommendation system provides the services with the trust relationship. The computation of the trust metrics

Figure 1. Flow of trust schedule.

services is defined as follow:

(5)

(6)

Recommendation system is defined with the prediction algorithm to describe the services. It consists of average rating of the recommended user. The weight of the similarity of user is obtained to find the RT value in wai. The coefficient value is evaluated as same in trust service oriented scheduling. By implementing the improved min-min algorithm, the scheduling of resource allocation and the task performance are improved and provide less computation time.

(7)

(8)

First the service resources and tasks are considered from the resource and task set. Then the value of the task completion time within deadline is evaluated with the matrix. The function starts with unmapped tasks. The completion time is evaluated based on the execution time of resources selection for tasks and its finishing time. Based on the services the task completion is differing and finally the value is updated. In this algorithm the mapping of the tasks are selected only if the task is not assigned to any other tasks. It provides better performance in completion of tasks. It makes changes in the strategy to perform the long tasks.

Basically the long tasks follow the short tasks. By this improved algorithm the complication of tasks is reduced. It computes the time of resource for all tasks competition. The process of this algorithm will repeat until the resources are allocated to all the tasks. The process will update the time taken for mapping of tasks to resources and its completion. The time complexity of this algorithm for resource and tasks is O (T2R).

4.2. Evaluating Execution Time

A set of services are capable to complete the task execution process. The time taken to execute and for completion of tasks is evaluated by using max-min algorithm; it executes as an operator. The services are listed in descending order based on the time taken for execution and it is sorted. The time, cost, success rate, task details and the feedback values are listed.

(9)

The fitness of scheduling for iteration takes place with time constraints. To meet the individual time constraints the fitness function is defined.

(10)

4.3. Evaluating Execution Cost

Execution cost for scheduling tasks and resource allocation for each task is defined as follow:

(11)

where if cmax is equal to cx then T(cx) = 0 and if cmin is equal to cx then T(cx) = 1. The scheduling constraint and the priority take place the individual fitness function for cost estimation.

(12)

(13)

The member function of both time and cost indicate the performance of the services and intentions gratification. Positive feedback rate can be calculated as,

(14)

The final fitness function of scheduling the task execution time and cost is evaluated by using the formula as given below. Equation (10) and Equation (13) are combined to evaluate the fitness function FS(I)-Fitness function for scheduling.

(15)

By Equation (13), the iteration is minimized; otherwise the fitness will be within strategies constraints. The cost is evaluated based on the execution within constraints. According to the function the services are sorted. If a service is based on cost then the list is sorted in ascending order otherwise if a service is based on time then sorted in descending order.

5. Algorithm Model

TWFS and WFS require strategies to incur a balance for different necessities. The TMWS work is proposed to find a best solution and also concurrently to satisfy conditions within deadline. The best possible trust is defined to succeed the level of user satisfaction. Heuristically, scheduling the function for time and cost is planned and defined with best solution.

The utility function (η) is applied for scheduling; it selects the highest value for the execution of scheduling to provide best solution. η(i) represents the result as higher or lesser value; if η(i) = 1 then the value is higher and if η(i) = 0 then the value is lesser. This function is evaluated for each joining task. Figure 2 shows the execution flow of scheduling for each task.

(16)

Iteratively the independent tasks are scheduled by using Min-Min and Max-Min heuristics. Min-Min heuristic scheduling schedules the tasks to compute earlier completion time (ECT) with its available resources. It computes the early time to obtain the minimum estimated finishing time. The minimum value is chosen for scheduling the task at earlier time to complete it. It selects the task with its resources with minimum computation time. Based on the priority of tasks the scheduling is performed at earlier time by using Max-Min heuristic scheduling. The selection of resources for tasks is based on the value computed from completion time of tasks. The workflow of scheduling is based on the computation process.

To satisfy all the objectives of the workflow scheduling, the decision process of allocating the resources is made by using the heuristic process with genetic decision process. Genetic algorithm is implemented for decision making to satisfy overall scheduling with its available resources. The selection service of TMWS work is a maximum degree of fulfillment of workflow schedule. The selection decision and the performance of the scheduling are evaluated with the time, cost and the fitness function. Considering the DAG sample graph as shown in Figure 3 and the rating sample for services are formed as in Table 1.

The optimization of resource allocation for workflow consists of minimum cost and time constraint is achieved by using improved genetic algorithm. It starts with initial solution to generate the best solution using the genetic operators. It selects the solution based on the least effect of the scheduling. The complex objective function is appropriate to define the solution and it avoids the local optimum solution set up.

Figure 2. Flow of scheduling execution.

Figure 3. Sample DAG of the workflow application.

Table 1. Sample of the ratings of enterprises for cloud services.

6. Performance Analysis

A Strategy guiding principle and structure are developed to design a heuristic approach for providing better solution. Meta-heuristics provide an efficient process of scheduling the workflow of the system. This approach is implemented with Improved Genetic Algorithms, Min-Min and Max-Min heuristic model. The comparison of the algorithm used for resources allocation of the tasks is presented. From the combination of best solution the global solution is obtained to exploit a region for next flow of system.

In cloud environment the scheduling process depends on various factors to find a best scheduling algorithm. For the provisioning of resources, the algorithms must strict with the required strategies like time, cost, success rate, weight, trust value and security. The TMWS scheduling model is comparatively improved when compared to the existing algorithm.

The comparison of workflow scheduling algorithms is shown in Table 2. It specifies the metrics like time, cost, memory and bandwidth. According to the proposed model the algorithm provides better performance. In TMWS model, improved genetic model is providing better performance than the existing work.

The comparison of scheduling algorithm with different models is presented in the result graph. The different models such as TMWS, TWFS, Minimum Critical Path (MCP) and Greedy-Cost are compared to prove that the proposed model is better than the existing model. The TMWS model is a Meta Heuristic function model to provide minimum Time, Cost and Trust value to meet the user satisfaction within the constraint. Trust based workflow scheduling is implemented with the improved genetic algorithm.

The comparison strategies of task scheduling are execution time, execution cost and weight. The task scheduling has been performed before its deadline. Figure 4 shows that the time taken for the scheduling of tasks by the TMWS is lesser than the existing; also provide a better performance than the TWFS and Greedy-cost and take more time than the MCP for scheduling the tasks.

The cost estimation for scheduling the tasks is shown in Figure 5. The TMWS model, the trust value is compared with the existing model to prove that the performance is better and improved than the existing in scheduling the workflow in trust basis, as shown in Figure 6. Figure 7 shows that the execution time of the nodes scheduled by the TMWS model is improved. The execution time of the nodes in scheduling is shown in Figure 8.

Table 2. Algorithm comparison for proposed model.

Figure 4. Time taken for each tasks.

Figure 5. Cost taken for each tasks.

Figure 6. Comparison of trust value for each task.

Figure 7. Execution time taken for nodes.

Figure 8. Execution cost taken for nodes.

The TMWS model provides better cost performance than the TWFS and MCP. But compared to Greedy-cost the cost estimation is high in scheduling of task as well as in execution of the nodes.

In TMWS model estimation of time, cost and trust based scheduling are achieved simultaneously within deadline with better performance in scheduling the workflow in cloud environment. MCP has the highest cost between various algorithms but has less execution time. Inversely Greedy-cost has the longest execution time but has least cost.

7. Conclusion and Future Work

In cloud environment lack of trust has been evaluated in providing resources by providers to the organization. In this research work, we have discussed about the integration of the system in cloud. The TMWS model is proposed to provide integration service for Enterprise System in cloud environment. To meet various constraints of users in the selection process of resources in workflow application, the selection model of improved genetic algorithm with heuristic scheduling has been proposed. In TMWS model, the cloud service criteria such as execution time, cost, success rate and trust are considered simultaneously to yield a genuinely optimal solution. TMWS model algorithm has improved the efficiency and reliability of the operation in the cloud system and the results show that the TMWS approach is effective and feasible.

As future work, we think to extend the work for dynamic process of collaboration system to adapt the environment and to provide the services with satisfied user constraint. In cloud, evolution service along with collaboration system should be considered to support unlikelihood and untrustworthy environments.

Cite this paper: Rathanam, G. and Rajaram, A. (2016) Trust Based Meta-Heuristics Workflow Scheduling in Cloud Service Environment. Circuits and Systems, 7, 520-531. doi: 10.4236/cs.2016.74044.
References

[1]   He, W. and Xu, L.D. (2014) Integration of Distributed Enterprise Applications: A Survey. IEEE Transactions on Industrial Informatics, 10, 35-42.
http://dx.doi.org/10.1109/TII.2012.2189221

[2]   Liu, B., Cao, S.G. and He, W. (2011) Distributed Data Mining for E-Business. Information Technology and Management, 12, 67-79.
http://dx.doi.org/10.1007/s10799-011-0091-8

[3]   Rahman, M., Li, X.R. and Palit, H. (2011) Hybrid Heuristic for Scheduling Data Analytics Workflow Applications in Hybrid Cloud Environment. 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), Anchorage, 16-20 May 2011, 966-974.
http://dx.doi.org/10.1109/IPDPS.2011.243

[4]   Dikaiakos, M., Katsaros, D., Mehra, P., Pallis, G. and Vakali, A. (2009) Cloud Computing: Distributed Internet Computing for IT and Scientific Research. IEEE Internet Computing, 13, 10-13.
http://dx.doi.org/10.1109/MIC.2009.103

[5]   Li, S., Xu, L., Wang, X. and Wang, J. (2012) Integration of Hybrid Wireless Networks in Cloud Services Oriented Enterprise Information Systems. Enterprise Information Systems, 6, 165-187.
http://dx.doi.org/10.1080/17517575.2011.654266

[6]   Xu, L., Liu, H., Wang, S. and Wang, K. (2009) Modeling and Analysis Techniques for Cross-Organizational Workflow Systems. Systems Research and Behavioral Science, 26, 367-389.
http://dx.doi.org/10.1002/sres.978

[7]   Wu, S., Xu, L. and He, W. (2009) Industry-Oriented Enterprise Resource Planning. Enterprise Information Systems, 3, 409-424.
http://dx.doi.org/10.1080/17517570903100511

[8]   Leukel, J., Kim, S. and Schlegel, T. (2011) Supply Chain as a Service: A Cloud Perspective on Supply Chain Systems. IEEE Systems Journal, 5, 16-27.
http://dx.doi.org/10.1109/JSYST.2010.2100197

[9]   Yang, F.J., Shen, W., Tan, W. and Ghenniwa, H.H. (2010) A Framework for Service Enterprise Workflow Simulation Based on Multi-Agent Cooperation. 2010 IEEE International Conference on Systems Man and Cybernetics (SMC), Istanbul, 10-13 October 2010, 2587-2594.
http://dx.doi.org/10.1109/ICSMC.2010.5641910

[10]   Liu, W., Du, Y., Yan, C., Buyya, R., Yeo, C.S., Venugopal, S., Broberg, J. and Brandic, I. (2009) Cloud Computing and Emerging IT Platforms: Vision, Hype, and Reality for Delivering Computing as the 5th Utility. Future Generation Computer Systems, 25, 599-616.
http://dx.doi.org/10.1016/j.future.2008.12.001

[11]   Ranaldo, N. and Zimeo, E. (2009) Time and Cost-Driven Scheduling of Data Parallel Tasks in Grid Workflows. IEEE Systems Journal, 3, 104-120.
http://dx.doi.org/10.1109/JSYST.2008.2011299

[12]   Tan, W.A., Sun, Y., Li, L.X., Lu, G.Z. and Wang, T. (2014) A Trust Service-Oriented Scheduling Model for Workflow Applications in Cloud Computing. IEEE Systems Journal, 8, 868-878.
http://dx.doi.org/10.1109/JSYST.2013.2260072

[13]   Tan, W., Xu, W., Yang, F., Xu, L. and Jiang, C. (2012) A Framework for Service Enterprise Workflow Simulation with Multi-Agents Cooperation. Enterprise Information Systems, 7, 1-20.

[14]   Lopez, M.M., Heymann, E. and Senar, M.A. (2006) Analysis of Dynamic Heuristics for Workflow Scheduling on Grid Systems. The Fifth International Symposium on Parallel and Distributed Computing, Timisoara, 6-9 July 2006, 199-207.
http://dx.doi.org/10.1109/ispdc.2006.9

[15]   Sakellariou, R., Zhao, H., Tsiakkouri, E. and Dikaiakos, M.D. (2005) Scheduling Workflows with Budget Constraints. Proc. Workshop Integr. Res. Grid Comput., Pisa, 189-202.

[16]   Hwang, S., Lim, E., Lee, C. and Chen, C. (2008) Dynamic Web Service Selection for Reliable Web Service Composition. IEEE Transactions on Services Computing, 1, 104-116.
http://dx.doi.org/10.1109/TSC.2008.2

[17]   Jiang, Y., Liu, J., Tang, M. and Liu, X. (2011) An Effective Web Service Recommendation Method Based on Personalized Collaborative Filtering. 2011 IEEE International Conference on Web Services (ICWS), Washington DC, 4-9 July 2011, 211-218.
http://dx.doi.org/10.1109/ICWS.2011.38

[18]   Mandal, A., Kennedy, K., Koelbel, C., Marin, G., Mellor-Crummey, J., Liu, B. and Johnsson, L. (2005) Scheduling Strategies for Mapping Application Workflows onto the Grid. 14th IEEE International Symposium on High Performance Distributed Computing, Research Triangle Park, 24-27 July 2005, 125-134.
http://dx.doi.org/10.1109/HPDC.2005.1520947

[19]   Khajemohammadi, H., Fanian, A. and Gulliver, T.A. (2013) Fast Workflow Scheduling for Grid Computing Based on a Multi-Objective Genetic Algorithm. 2013 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM), Victoria, 27-29 August 2013, 96-101.
http://dx.doi.org/10.1109/PACRIM.2013.6625456

 
 
Top