Rollout Algorithms for Job-Shop Scheduling

Abstract

The topic of this thesis are new approximation methods for job-shop scheduling that dispatch jobs based on statistics collected from multiple Monte Carlo rollouts. The methods use a look-ahead feature to evaluate all the jobs available for dispatching, by generating multiple feasible schedules. Previous work on rollout algorithms for combinatorial optimization problems has focused on sequentially consistent heuristics, that only search small areas of the solution space. The new algorithms widen the search space by basing the search on sequentially inconsistent algorithms. Four new algorithms are proposed: the fortified rollout algorithm, average rollout algorithm, hybrid rollout algorithm and quantile rollout algorithm. These methods differ in the way jobs are dispatched after completion of rollouts. The methods are tested on 600 job-shop problems of three different dimensions. All of the algorithms were able to generate schedules of higher quality than previous algorithms employing rollouts and the quantile rollout algorithm produced the best schedules overall, especially for larger problem instances.

Umfjöllunarefni þessarrar rigerðar eru nálgunaraðferðir fyrir verkniðurröðun. Aðferðirnar skoða næstu verk sem bíða niðurröðunar, mynda þaðan fjölda lausna með Monte Carlo útspilun (e. rollouts) og ákveða svo næsta verk til þess að raða. Rannsóknir á þessum aðferðum hafa hingað til einskorðast við röðunarreglur sem beina leit sinni að takmörkuðu svæði lausnarrúmsins. Aðferðirnar sem hér eru kynntar víkka leitarsvæði útspilanna með því að einblína á slembnar röðunarreglur.Fjórum nýjum reikniritum er lýst: styrktarreiknirit (e. fortified rollout algorithm), meðaltalsreiknirit (e. average rollout algorithm), tvinnreiknirit (e. hybrid rollout algorithm) og hlutfallsmarksreiknirit (e. quantile rollout algorithm) og liggur munur þeirra í því hvernig verkum er raðað eftir lok útspilanna. Aðferðirnar voru prófaðar á 600 mismunandi verkniðurröðunarverkefnum af þremur mismunandi stærðum. Allar nýju aðferðirnar fundu betri lausnir en önnur þekkt útspilunarreiknirit. Hlutfallsmarks-reikniritið fann bestu lausnirnar í heildina, sérstaklega fyrir stærri gerðir verkefna.