Title: A Meta-RaPS algorithm for spatial scheduling with release times

Authors: Christopher Garcia; Ghaith Rabadi

Addresses: College of Business, University of Mary Washington, 1301 College Avenue, Fredericksburg, VA 22401, USA. ' Department of Engineering Management and Systems Engineering, Old Dominion University, 241 Kaufman Hall, Norfolk, VA 23529, USA

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.

Keywords: spatial scheduling; release times; Meta-RaPS; metaheuristics; randomised priority search; total tardiness.

DOI: 10.1504/IJPS.2011.044555

International Journal of Planning and Scheduling, 2011 Vol.1 No.1/2, pp.19 - 31

Received: 01 Jun 2011
Accepted: 06 Sep 2011
Published online: 31 Dec 2011 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article