Ant Colony Algorithm for Single Processor Scheduling with Minimization of Peak Resource Usage

We consider the problem of constructing a single processor task schedule withminimization of peak resource usage. An example of the resource is the main memory of the targetcomputer. Task set to be scheduled is represented as a directed acyclic graph every node of whichis marked with the amount of resource used by the corresponding task. The resource allocated toa task is released on completion of the last (according to the schedule) immediate successor of thistask in the graph. Correctness constraint on the schedule is the partial order specified by the taskgraph. Task duration values are not considered. The formal statement of the problem is provided.To solve the problem, we propose an ant colony algorithm modified so that the pheromone matrixreflects the desirability of pairwise order in the schedule for every pair of tasks, not only for pairs ofadjacent tasks. During the schedule construction, for every task the algorithm chooses its positionin the schedule, in contrast to existing ant colony scheduling algorithms that construct schedule inincreasing order of positions (left-to-right) choosing a task for every next position. Experimentalevaluation of the algorithm was conducted on two sets of task graphs. The first set containsgraphs generated in such a way that the estimation for the optimum value of the goal function isknown a priori. Graphs from the second set are “layered,” and their structure corresponds to thestructure of multistage data processing applications. In both sets, the graphs are generatedrandomly with respect to specified generation parameters and constraints on the graph structure.The experiments indicate high precision and stability of the proposed ant colony algorithm.