A Partial Critical Path Based Approach for Grid Workflow Scheduling | Open Access Journals

ISSN ONLINE(2319-8753)PRINT(2347-6710)

Yakışıklı erkek tatil için bir beldeye gidiyor burada kendisine türk Porno güzel bir seksi kadın ayarlıyor Onunla beraber otel odasına gidiyorlar Otel odasına rokettube giren kadın ilk önce erkekle sohbet ederek işi yavaş halletmeye çalışıyor sex hikayeleri Kocası fabrikatör olan sarışın Rus hatun şehirden biraz uzak olan bir türk porno kasabaya son derece lüks bir villa yaptırıp yerleşiyor Kocasını işe gönderip mobil porno istediği erkeği eve atan Rus hatun son olarak fotoğraf çekimi yapmak üzere türk porno evine gelen genç adamı bahçede azdırıyor Güzel hatun zengin bir iş adamının porno indir dostu olmayı kabul ediyor Adamın kendisine aldığı yazlık evde sikiş kalmaya başlayan hatun bir süre sonra kendi erkek arkadaşlarını bir bir çağırarak onlarla porno izle yapıyor Son olarak çağırdığı arkadaşını kapıda üzerinde beyaz gömleğin açık sikiş düğmelerinden fışkıran dik memeleri ile karşılayıp içeri girer girmez sikiş dudaklarına yapışarak sevişiyor Evin her köşesine yayılan inleme seslerinin eşliğinde yorgun düşerek orgazm oluyor

A Partial Critical Path Based Approach for Grid Workflow Scheduling

Anagha Sharaf1, Suguna.M2
  1. PG Scholar, Department of IT, S.N.S College of Technology, Coimbatore, Tamilnadu, India
  2. Associate Professor, Department of IT, S.N.S College of Technology, Coimbatore, Tamilnadu, India
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Science, Engineering and Technology


Grid Computing is a technique in which the idle systems in the Network and their CPU cycles can be efficiently used by uniting pools of servers, storage systems and networks into a single large virtual system for resource sharing dynamically. Utility grids are new service models in heterogenous distributed systems. Utility grids enable users to specify the quality requirements they need. The main challenge in grid computing is the efficient workflow scheduling. For scheduling workflows considering QoS specifications of user a metaheuristic algorithm is introduced. The algorithm is based on the concept of partial critical path. The algorithm includes two phases 1.deadline phase and 2.Planning phase. User submits deadline and other QoS specifications in deadline phase. The cheapest service is allotted to tasks inorder to satisfy QoS specifications and deadline in planning phase.


Utility grids, workflow scheduling, partial critical path


Grid computing is the technique of flexible and coordinated resource sharing. With grid computing users could access geographically distributed resources. Grids use a layer of middleware to communicate with and manipulate heterogeneous hardware and data sets. In some fields—astronomy, for example—hardware cannot reasonably be moved and is prohibitively expensive to replicate on other sites. In other instances, databases which are vital for some projects could not be replicated and transferred to multiple sites. Grid computing overcomes these obstacles. Grid computing enables the virtualization of distributed computing resources such as processing, network bandwidth, and storage capacity to create a single system image, granting users and applications seamless access to vast IT capabilities.
Utility grids are the emerging service provisioning model in heterogenous distributed systems. Utility grids make the distributed resources available in market for price.
The main difference between traditional grids and utility grid is the Quality of service. Utility grids enable the users to negotiate with service providers for the required Quality of service and also on the price.
\Workflow could be described as collection of tasks that can be processed on distributed resources in a well defined manner to achieve specific goal. It is a common model for describing wide range of applications in distributed systems. Workflows could be represented using Directed Acyclic Graph (DAG), where each computational task is represented by a node and dependency among tasks is represented using the edges.
A metaheuristic QoS based workflow scheduling algorithm called partial critical path algorithm is introduced. The performance of the algorithm in the parallel pipelined environment is enhanced in comparison with the heuristic approach. The problem of assigning longer sub deadlines for tasks in the pipeline is rectified in the metaheuristic approach.



In the PCP scheduling algorithm, the critical path and partial critical paths of the whole workflow is to be found. In order to find these, some idealized, notion of the start time of each workflow task are needed before scheduling of the tasks are done. This means that two notions of the start times of tasks are available, the earliest start time computed before scheduling the workflow, and the actual start time computed by the scheduling algorithm. For each unscheduled task ti, the Earliest Start Time EST (ti) is found as the earliest time ti can start its computation regardless of the actual service that will process the task which is determined during scheduling. Since grid is a heterogeneous environment and the computation time of tasks varies from service to service the EST cannot be found exactly.


This algorithm receives a scheduled node as input and tries to schedule all of its parents before the actual start time of the input node itself. On success, it returns the desired schedule, but on failure, it returns a task that causes this failure and a suggested start time for this task that hopefully makes its scheduling possible. The pseudocode of parent scheduling algorithm could be written as

2.1.3. The Path Scheduling Algorithm

It starts from the first task in the path and moves forward to the last task, at each step selecting an untried available service for that task. If the selected service creates an admissible (partial) schedule, then it moves forward to the next task, otherwise it selects another untried service for that task. If there is no available untried service for that task left, then it backtracks to the previous task on the path and selects another service for it. After selecting a service for the current task t, say service s, the algorithm computes the start time ST(t,s) and the actual cost C(t,s) of running task t on service s.The pseudocode for the path scheduling algorithm could be written as;


As the first step of modifying the existing PCP algorithm, its heuristic nature is changed to metaheuristic one. Initially, only time constraint was considered for optimizing the cost of workflow scheduling. But this project resulted in the PCP algorithm which considers different parameters like storage, speed, and time etc for optimizing the cost of workflow scheduling. As first step of scheduling, prescheduling parameters of the tasks entered are found out.
A user interface was created to enable the users and service providers to enter new tasks, offer new services etc. Users could specify the requirements of the task like storage, speed etc. The prescheduling parameters like MET, EST, LFT etc are calculated.
For instance, user have entered five tasks namely t0, t1, t2, t3, t4. The MET of the tasks are 6,20,8,10,15 respectively. The EST of the first task are found using the MET as:
1.EST(t0)=0+0+6 =6
Likewise EST of the other tasks could be calculated.
LFT(t0)=70 which is the deadline likewise the LFT of the other tasks could be calculated using the formula. The EST and LFT of the tasks could be tabulated as:


Users and service providers are allowed to enter new tasks and its specifications, calculate the prescheduling parameters, and offer new services by logging into the wfms. After logging in as user, new task and its requirements could be specified as:


Utility Grids enable users to obtain their desired QoS (such as deadline) by paying an appropriate price. In this paper, a new algorithm named PCP is proposed for workflow scheduling in utility Grids that minimizes the total execution cost while meeting a user-defined deadline. The PCP algorithm has two phases: deadline distribution and planning. In the deadline distribution phase, the overall deadline of the workflow is divided over the workflow’s tasks, for which are proposed three different policies, i.e., Optimized, Decrease Cost, and Fair. In the planning phase, the best service is selected for each task according to its subdeadline. The algorithm could be evaluated by simulating it with synthetic workflows that are based on real scientific workflows with different structures and different sizes.


1. D. Laforenza, “European Strategies Towards Next Generation Grids,” Proc. Fifth Int’l Symp. Parallel and Distributed Computing (ISPDC ’06), p. 11, 2006.

2. J. Broberg, S. Venugopal, and R. Buyya, “Market-oriented Grids and Utility Computing: The State-of-the-Art and Future Directions,” J. Grid Computing, vol. 6, no. 3, pp. 255-276, 2008.

3. J. Yu and R. Buyya, “Scheduling Scientific Workflow Applications with Deadline and Budget Constraints Using Genetic Algorithms,” Scientific Programming, vol. 14, nos. 3/4, pp. 217- 230, 2006.

4. E. Deelman et al., “Pegasus: A Framework for Mapping ComplexScientific Workflows Onto Distributed Systems,” Science Programming, vol. 13, pp. 219-237, 2005.

5. M. Wieczorek, R. Prodan, and T. Fahringer, “Scheduling ofScientificWorkflows in the Askalon Grid Environment,” SIGMODRecord, vol. 34, pp. 56-62, 2005.

6. F. Berman et al., “New Grid Scheduling and ReschedulingMethods in the Grads Project,” Int’l J. Parallel Programming, vol. 33, pp. 209- 229, 2005.

7. J. Yu and R. Buyya, “A Taxonomy of Workflow ManagementSystems for Grid Computing,” J. Grid Computing, vol. 3, pp. 171-200, 2005.

8. M.R. Garey and D.S. Johnson, Computers and Intractability: A Guideto the Theory of NP-Completeness. W.H. Freeman, Jan. 1979.

9. Y.K. Kwok and I. Ahmad, “Static Scheduling Algorithms forAllocating Directed Task Graphs to Multiprocessors,” ACMComputing Surveys, vol. 31, no. 4, pp. 406-471, 1999.

10. H. Topcuoglu, S. Hariri, and M. Wu, “Performance-Effective andLow-Complexity Task Scheduling for Heterogeneous Computing,” IEEE Trans. Parallel and Distributed Systems, vol. 13, no. 3, pp. 260- 274, Mar. 2002.

11.Saeid Abrishami,Mahmoud Naghibzadeh and Dick H.J.Epema,”Cost Driven Scheduling of Grid Workflows using Partial critical paths”, IEEE transactions on parallel and distributed systems, vol. 23, no. 8, August 2012.

12. Reen-Cheng Wang, Su-Ling Wu, and Ruay-Shiung Chang,” A Novel Data Grid Coherence Protocol Using Pipeline-based Aggressive Copy Method”