الگوریتم های ترکیبی راه حل برای مشکل زمان بندی کار با حرکت مجریان

Heuristic algorithms for solving the task scheduling problem with moving executors to minimize the sum of completion times are considered. The corresponding combinatorial optimization problem is formulated. Three hybrid solution algorithms are introduced. As a basis an evolutionary algorithm is assumed that is combined with the procedure that uses simulated annealing metaheuristics. The results of simulation experiments are given in which the influence of parameters of the solution algorithms as well as of the number of tasks on the quality of scheduling and on the time of computation is investigated.

Problems of task scheduling with moving executors are a generalization of traditional task scheduling problems. It is assumed that executors of tasks move between places at a plane or in a space, where the tasks can be performed. These places called workstations are supplemented by a depot being a place, where executors begin and end their work. Modern discrete manufacturing systems are the main area of applications of the complex scheduling problem in the cases when the movement of plants being in production is impossible or too expensive and it is better to move executors. For example, it occurs when plants in production (e.g. big engine casings, railway carriage elements) are too big or too heavy to move among executors (machines). Another example may concern maintenance tasks on stationary machines or transport tasks performed by mobile robots or automated guided vehicles in flexible manufacturing systems. Automated service systems as well as computer systems, where the times of the movement of executors (agents) are not neglected, can be the prospective examples for the applications of the scheduling problem under consideration.

In the paper the complex task scheduling problem which consists in scheduling of independent, non-preemptive tasks on one moving executor to minimize the sum of completion time is presented. The movement of the executor being the subject performing the tasks leads to the new discrete optimization problem. Because of the strong computational complexity of this problem the determination of heuristic algorithms is crucial. The proposition of the algorithms based on the evolutionary approach is given. Three hybrid algorithms, in which in different ways the SA metaheuristics is applied, are presented and considered. The computer simulation experiments which have been conducted show significant improvement of the results in comparison with the component algorithms taken separately. When the SA and the EA are applied alternatively, the best results are obtained. The improvement up to 13% has been obtained in comparison with the individual EA but it causes a considerable increase of the time of computation. The experiments for small instances of the problem, when the optimal results can be the reference, confirm the usefulness of the algorithms under investigation. In further works the results will be compared with the approximate algorithm that is currently under development. Also some advanced versions of the SA may be used as their usefulness for the hybrid algorithms is worth evaluating. Moreover, other hybridization schemes of EA seem to be interesting and fruitful, too, e.g. the application of tabu search also seems to be a good choice.