Scientific article
OA Policy
English

Graph colouring approaches for a satellite range scheduling problem

Published in

Journal of scheduling, vol. 11, no. 4, p. 263-277

Collection

  • Open Access - Licence nationale Springer

Publication date

2008

Abstract

A goal of this paper is to efficiently adapt the best ingredients of the graph colouring techniques to an NPhard satellite range scheduling problem, called MuRRSP. We propose two new heuristics for the MuRRSP, where as many jobs as possible have to be scheduled on several resources, while respecting time and capacity constraints. In the permutation solution space, which is widely used by other researchers, a solution is represented by a permutation of the jobs, and a schedule builder is needed to generate and evaluate a feasible schedule from the permutation. On the contrary, our heuristics are based on the solution space which contains all the feasible schedules. Based on the similarities between the graph colouring problem and the MuRRSP, we show that the latter solution space has significant advantages. A tabu search and an adaptive memory algorithms are designed to tackle the MuRRSP. These heuristics are derived from efficient graph colouring methods. Numerical experiments, performed on large, realistic, and challenging instances, showed that our heuristics are very competitive, robust, and outperform algorithms based on the permutation solution space.

Keywords

  • Oversubscribed satellite scheduling
  • Graph colouring
  • Heuristics

UNIGE affiliation entities

Citation (ISO format)

ZUFFEREY, Nicolas, AMSTUTZ, Patrick, GIACCARI, Philippe. Graph colouring approaches for a satellite range scheduling problem. In: Journal of scheduling, 2008, vol. 11, n° 4, p. 263–277. doi: 10.1007/s10951-008-0066-8

Main files (1)

Article (Published version)

Identifiers

Journal ISSN

1094-6136
752views
1008downloads

Technical informations

Creation

24/02/2010 15:01:00

First validation

24/02/2010 15:01:00

Update

14/03/2023 15:24:20

Status update

14/03/2023 15:24:20

Last indexation

29/10/2024 13:01:55
All rights reserved by Archive ouverte UNIGE and the University of Geneva
OpenAIRE Indexed & Validated