Level Based Research On Workflow Scheduling Algorithm

With the rapidly development of computer network, the widely used of some newtechnologies and concepts, such as intelligent computing, SOA (Service Oriented Architecture)and so on, has promoted the realization of computer supported and cooperative work. Workflow,which is regard as an abstract model in computers’ cooperative work, plays a more important rolein pipeline production of enterprises, office automation, researching and so on, and it can alsoincrease the robotization and flexibility of business process. Thus, workflow scheduling isbecoming a critical technique of workflow management. With the services of workflow from freeto paid, it should select the optimized service according to the value of the Quality of Service(QoS), like time, cost and reliable, to satisfy users’ requirements. The paper mainly discuss theworkflow scheduling algorithm of cost minimize under time constraint based on leveling, andproposes a novel heuristics algorithm, a workflow scheduling simulation platform has also beendeveloped. The novel contributions are as below:To solve the problem of cost minimization under deadline constraint based workflowscheduling, which is described by DAG (Directed Acyclic Graph), the DBL (Deadline BottomLevel) hasn’t considered the concurrence during the real executing process that cause much moreshatter time, then a novel heuristics algorithm of CLWS (Concurrent Level Workflow Scheduling)is proposed. It makes its best efforts to distribute tasks that can execute concurrence into the samelevel. Then, CLWS distributes the total redundancy time into every level based on their concurrentdegree. And it adopts the algorithm of MDP (Markov Decision Process) to optimize tasks, whichhave dependence with each other in the same level. The experiments show that CLWS can make abetter improvement compared with DBL, DTL (Deadline Top Level).While considering the complex executing environment, some abrupt service unavailable mayhappen without expected, causing the QoS of workflow tasks cannot be estimated preciously,from this sense, the given workflow may not execute as plan. This paper proposes a workflowrescheduling algorithm to solve the problem of service delay based on CLWS. Every level (exceptthe first and last level) has been distributed the sub time float, if some task executes overtime andit has affect its successor(s), the sub time float can be distributed to this task and its concurrenttask(s). What if the sub time float can’t afford the delay time, the children level of this task’scorresponding level should adjust its time interval like before until all the remain time float is usedup. The experiments show that this algorithm can optimize the cost minimization under thedeadline constraint. To compare the optimize performance among workflow scheduling algorithms, a workflowscheduling simulation platform has also been developed. This platform can produce workflowautomatic, select algorithm optionally to execute, and give the comparison chart as the result.