Earliest Starting and Finishing time Duplication-based algorithm
Mahsa Hosseinzadeh, Hadi Shahriar Shahhoseini · International Symposium on Performance Evaluation of Computer and Telecommunication Systems · 2009
Optimal task scheduling of a direct acyclic graph (DAG) onto distributed environments is a NP-hard problem. In this paper, we propose a new scheduling algorithm called Earliest Starting and Finishing time Duplication based (ESFD). ESFD has three phases: priority processing, task scheduling and task duplication. ESFD considers all parameters related to the task and its immediate predecessors to assigning a task. After each schedule ESFD will be updated its first phase, so ESFD is a dynamic algorithm. Experimental results on random graphs and real application graphs show that the NSL and speedups generated by the ESFD are better than those generated by the well-known HCPT, HEFT and LHCNF algorithms.