[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]

(Related publications: [PUBLink] [PUBLink])

The experiments in Section [Randomization] showed that the ARC's heuristic is not very powerful. It would therefore seem advisable to consider other heuristics. For example, tasks should obviously be packed quite tightly on a machine. The following ARC-H2 heuristic supports this feature. ARC-H2 is very similar ARC-H1, but it makes the selection of the second interval in a different way: for the new position of the task, only two shifts are possible, the task either beginning at the beginning of the task's predecessor interval or ending at the end of the task's successor interval. The interval with less tasks is chosen.

The impact of the new ARC-H2 heuristic is impressive. The best results are obtained using a probability of about 90% for the new heuristic to be chosen, and 10% for the old ARC-H1 heuristic (see following figure). Choosing the new heuristic more often causes a deterioration in the results.

The figure below shows the impact of randomization, indicating the first interval's selection of the ARC-H2 heuristic by the letter s (always with a probability of 90% for the ARC-H2 heuristic to be chosen). The addition of domain knowledge by the new heuristic strongly reduced the effect of randomization compared to that in Section [Randomization].

For questions, comments or suggestions, please contact us.

Last update:
May 19, 2001 by Alexander Nareyek