The Research On Budget-Constrained Workflow Scheduling Algorithm In Grid Computing

As a new computing mode, grid has become a cyber-infrastructure for the next-generation of the e-Science. Many scholars and researchers have been attracted by its great potential and have been sparing no effort to study it, which gives birth to a lot of achievements. The grid workflow, as an important primary service of the grid environment, contributes much to the improvement of the automation and efficiency of the grid applications.The grid workflow scheduling is one of the core components of the grid workflow management systems, which provides significant supports to the high-performance computing of the grid. The grid workflow scheduler maps the activities (or computing tasks) onto proper computing resources in the grid environment and coordinates the execution of the activities to achieve the best goal.The scheduling of the grid workflow has been proved to be NP-hard, but it really attracts a great number of people. Thanks to the contribution from the researchers, the grid workflow scheduling problem has been developed a lot. Plenty of algorithms have been proposed, including huristics and metahuristics scheduling algorightms. Examples of the former are Min-Min, Max-Min, HEFT, List Scheduling and cluster based scheduling, while that of the latter are genetic algorighm, silumated annealing algorithm, ant colony optimization, and so on.When utilizing grid resources to execute the activities, the workflow scheduler needs to pay for the cost, which is proportional to executing time period. In most cases, the budget for the cost is limited, thus forming what we call budget-constrained grid workflow. The algorithms mentioned above are all performance-driven and not fit for the scheduling of the budget-constrained grid workflow.We propose in this paper an algorithm based on the Ant Colony Optimization to solve the problem above. In the application of the Ant Colony Optimization to the problem, we creatively put forward two new concepts, the luxury money and luxury rate; also, a whole new formula for computing the distance between two nodes is displayed. When computing the distance between two nodes, our algorithm takes such factors as the limitation of the budget, the finish time of the precedence, the communication time and the execution time of the activity into consideration and improves the quality and efficiency of the solutions.