We consider the following multi-mode task scheduling problem. Given are a set of non-preemptive and independent tasks, and a set of single unit dedicated renewable resources. At any time each resource can be used by a single task at most. Each task has to be executed without preemption in one out of its possible execution modes, where each mode identifies a subset of resources simultaneously required by the task for its execution. The aim of the problem is to find a mode assignment for each task, and a non-preemptive schedule of the tasks to be executed in the assigned modes, such that the total amount of resources requested by tasks in any time period does not exceed the resource availability, and the schedule length, i.e., the makespan, is minimized. From the complexity viewpoint this problem is NP-hard. Heuristic algorithms for scheduling tasks with multiple modes for the minimum schedule length criterion involve in general two distinct phases, task mode assignment and task scheduling. In this paper we propose a novel two-phase approach metaheuristic based on strategic oscillation and on a randomized choice of the neighborhood of the local search to avoid being trapped in local optima. The proposed approach simplifies that one appeared in a previous work of the authors in which an interval T-coloring graph model and a metaheuristic approach based on strategic oscillation were provided. The performance of the proposed solution approach is compared to that of known multi-mode scheduling heuristics.

Caramia, M., Giordani, S. (2009). A Fast Metaheuristic for Scheduling Independent Tasks with Multiple Modes.

A Fast Metaheuristic for Scheduling Independent Tasks with Multiple Modes

CARAMIA, MASSIMILIANO;GIORDANI, STEFANO
2009-07-07

Abstract

We consider the following multi-mode task scheduling problem. Given are a set of non-preemptive and independent tasks, and a set of single unit dedicated renewable resources. At any time each resource can be used by a single task at most. Each task has to be executed without preemption in one out of its possible execution modes, where each mode identifies a subset of resources simultaneously required by the task for its execution. The aim of the problem is to find a mode assignment for each task, and a non-preemptive schedule of the tasks to be executed in the assigned modes, such that the total amount of resources requested by tasks in any time period does not exceed the resource availability, and the schedule length, i.e., the makespan, is minimized. From the complexity viewpoint this problem is NP-hard. Heuristic algorithms for scheduling tasks with multiple modes for the minimum schedule length criterion involve in general two distinct phases, task mode assignment and task scheduling. In this paper we propose a novel two-phase approach metaheuristic based on strategic oscillation and on a randomized choice of the neighborhood of the local search to avoid being trapped in local optima. The proposed approach simplifies that one appeared in a previous work of the authors in which an interval T-coloring graph model and a metaheuristic approach based on strategic oscillation were provided. The performance of the proposed solution approach is compared to that of known multi-mode scheduling heuristics.
7-lug-2009
en
independent task scheduling
multi-mode
metaheuristic
Caramia, M., Giordani, S. (2009). A Fast Metaheuristic for Scheduling Independent Tasks with Multiple Modes.
Caramia, M; Giordani, S
Altro
File in questo prodotto:
File Dimensione Formato  
RR05.09_Caramia_Giordani.pdf

accesso aperto

Dimensione 364.09 kB
Formato Adobe PDF
364.09 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/913
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact