The Research Of Task Scheduling And Allocating Strategy For Instance-intensive Business Workflows

Business and government agencies often need to handle a large volume of service requests as the fast growth of e-business. These requests are always small business processes and they need to be handled in a constrained period so called instance-intensive business workflows. The volumes of business data are bigger and bigger with the rapid development of commercialization, then how to ensure on-time completion for large volume instance-intensive business processes within a constrained time is a challenging QoS (Quality of Service) issue because any time delay may cause serious consequences such as user satisfaction, financial loss and/or penalty. The rapid development of cloud computing has brought great opportunities to handle business workflows, however, the lack of QoS management strategies is a serious impediment to its wide deployment due to the dynamic nature of cloud services. It is a key research issue for today’s software systems to utilize cloud computing resources to provide satisfactory QoS for large volume time-constrained processes. Considering these complex instance-intensive business workflows, how to ensure that all the business tasks can be completed in a constrain time at the initialization stage has a great influence to quality of service. Then how to effectively monitor that all tasks have been finished scheduling and improve efficiency and reliability for task allocation at the running stage is a very important criterion to business applications.The detail research contents are as follows:(1) The thesis puts forward several scheduling models include coarse-grained general business workflow scheduling model, fine-grained general business workflow scheduling model, resource pool general scheduling model and the theory of the shortest execution time scheduling model. In the real world, business processes are usually small workflow instances and each instance is limited to be executed in a fixed time period. The start and finish time usually have certain re-quirements to different instances and they all have sequential relations. So this thesis puts forward interval scheduling to deal with those features. Due to the existing temporal dependencies in busi- ness processes, the interval scheduling can be well utilized to allocate multiple tasks into different processors and provide basic fundamentals to parallel scheduling in business workflows.(2) The thesis utilizes Directed Acyclic Graph (DAG) model based on the interval scheduling by respectively considering the sequential limitation in different tasks. This thesis studies real-time scheduling for DAG tasks which have multiple serial and parallel activities with temporal dependency. So it extracts a valid main path for task scheduling that the task can be expanded into parallel mode based on our DAG model. Then this thesis puts forward a stretch scheduling strategy to meet the deadline of tasks and reduce the occupation of resources based on the completion time and deadline so that other tasks can be scheduled effectively. The strategy can ensure all tasks effectively scheduling and meeting whole sequence requirement limit by reducing the occupation of virtual machines.(3) This thesis puts forward a dynamic priority scheduling strategy (DPS) after entirely stretch the business processes which do not have temporal limitation in each task. It mainly uses the idea of Min-Min heuristic algorithm and greedy philosophy. DPS schedules all the business tasks by the mode of batch processes based on the using numbers of cloud processors. It forecasts and sorts the scheduling time for each batch of tasks before scheduling. DPS will assign different priority based on the execution time of tasks and keep the consistency state for all cloud processors. The time complexity of DPS is O(m2n) which is much better than Min-Min. In order to show the effectiveness of DPS, theoretical minimum execution time (METtheory) is used as a benchmark for evaluation based on our simulation. The results show that the ratios between METtheory and DPS are more than 98.5% by scheduling different orders of magnitude tasks from 1,000 to 1,000,000. Particularly, the ratio between METtheory and DPS is near 99.9% with 1,000,000 tasks, which means that our DPS can get the near-optimal results when scheduling large number of tasks.(4) To ensure on-time finishing a large number of real-time task scheduling, we need to moni-tor business workflow scheduling process to determine whether a task execution can meet temporal requirements. In this thesis, we propose a business workflow process monitoring strategy. It di-vides the scheduling process into several equal parts along the time-line to detect the time point of instruction in guaranteeing the normal operation of the workflow. However, due to the large amount data in business workflow, each event execution time is short and the scheduling system may have time redundancy. It does not need to monitor every testing point. Therefore, we put forward a kind of dynamic time testing point selection strategy in this article on the basis of the time-line testing points. This can keep the execution state before sequence detection of business workflow and judge the time redundancy scheduling process strategy when selecting a temporal checkpoint. Through the selection of dynamic testing points, we reduce the number of checking points overall, thereby reducing the cost of workflow monitoring process based on the temporal consistency.