engleski

Comparison of schedule generation schemes for designing dispatching rules with genetic programming in the unrelated machines environment

Automatically designing new dispatching rules (DRs) by genetic programming has become an increasingly researched topic. Such an approach enables that DRs can be designed efficiently for various scheduling problems. Furthermore, most automatically designed DRs outperform existing manually designed DRs. Most research focused solely on designing priority functions that were used to determine the order in which jobs should be scheduled. However, in some scheduling environments, besides only determining the order of the jobs, one has to additionally determine the allocation of jobs to machines. For that purpose, a schedule generation scheme (SGS), which constructs the schedule, has to be applied. Until now the influence of different choices in the design of the SGS has not been extensively researched, which could lead to the application of an SGS that would obtain inferior results. The main goal of this paper is to perform an analysis of different SGS variants. For that purpose, three SGS variants are tested, two of which are proposed in this paper. They are tested in several variations which differ in details like whether they insert idle times in the schedule, or if they select the job with the highest or lowest priority values. The obtained results demonstrate that the automatically designed DRs with the tested SGS variants perform better than manually designed DRs, but also that there is a significant difference in the performance between the different SGS types and variants. The best DRs are analysed and show that the main reason why they performed well was due to the more sophisticated decisions they made when selecting the appropriate machine for a job. The results suggest that it is best to apply SGS variants which use the evolved priority functions to choose both the next job and the appropriate machine for that job.

Genetic programming ; Dispatching rules ; Schedule generation scheme ; Unrelated machines environment ; Hyper-heuristics ; Scheduling

nije evidentirano