Task allocation problem solved by augmented simulated annealing

The augmented simulated annealing method is applied for the task allocation problem (a simplified analog of the well-known job-shop scheduling). The problem of task allocation is formulated graph theoretically, it is considered as a mapping of the task graph (nonoriented graph with evaluated vertices and edges by positive numbers) onto the machine graph (connected graph). Each mapping is evaluated by an objective function which reflects to some extent the task allocation problem. That is, loosely speaking, a cost of the given performance of tasks on machines. The augmented simulated annealing is a generalization of the standard simulated annealing, instead of the simple mapping a pool of mapping is optimized. An interaction between pool mappings is introduced, where two randomly selected mappings exchange a part of their entries. The method of augmented simulated annealing looks for an optimum mapping with minimum value of the objective function.