دانلود رایگان مقاله برنامه ریزی تطبیقی بر روی ماشین غیر مرتبط با برنامه نویسی ژنتیک

Abstract

This paper investigates the use of genetic programming in automatized synthesis of heuristics for the parallel unrelated machines environment with arbitrary performance criteria. The proposed scheduling heuristic consists of a manually defined meta-algorithm which uses a priority function evolved separately with genetic programming. In this paper, several different genetic programming methods for evolving priority functions, like dimensionally aware genetic programming, genetic programming with iterative dispatching rules and gene expression programming, have been tried out and described. The performance of the suggested approach is compared to existing scheduling heuristics and it is shown that it mostly outperforms them. The described approach could prove useful when used for optimizing scheduling criteria for which no adequate scheduling heuristic exists.

7. Conclusion

This paper showshow genetic programming canbeused to build scheduling algorithms for the parallel unrelated machines scheduling environment with arbitrary scheduling criteria. The proposed heuristic is composed of two parts: a meta-algorithm and a priority function. The meta-algorithm we propose is defined manually, while the priority function is evolved using GP. This allows the users to specify an arbitrary criterion, and evolve the appropriate priority function for it. The experiments have shown that the proposed algorithm achieved results which were in most cases better than the results achieved by the existing scheduling heuristics. The GP was still unable tofindsolutionsbetter thanthose foundby the search-based methods. However, the goal of this approach is not to provide optimal or near optimal solutions, but to find solutions with acceptable quality in a small amount of time. Additionally, several different GP approaches like dimensionally aware GP, GEP and GP with iterative dispatching rules were tried out. GP with iterative dispatching rules achieved the best results when compared to any of the other GP approaches, but is applicable only in off-line scheduling. Dimensionally aware GP and GEP achieved results which were mostly comparable to the standard GP, but offer some benefits which could make them more appropriate for certain situations.