A Meta-RaPS algorithm for spatial scheduling with release times

Abstract

Spatial scheduling involves jobs that require processing space as well as time. Space is a limited resource, and solutions require assigning a location to each job within the available processing space in addition to a start time. We consider problems where each job has a release time and multiple processing areas are used in parallel. We develop an algorithm for minimising total tardiness based on Meta–heuristic for Randomised Priority Search (Meta–RaPS), a meta–heuristic that has been very effective on many scheduling and combinatorial optimisation problems. Our algorithm performs effectively on a large variety of benchmark problems.