Pruning Search Spaces of RATA Model for the Job-Shop Scheduling

Farid Arfi; Jean-Michel Ilié; Djamel-Eddine Saidouni

Quality, Reliability, Security and Robustness in Heterogeneous Networks. 9th International Conference, QShine 2013, Greader Noida, India, January 11-12, 2013, Revised Selected Papers

Research Article

Pruning Search Spaces of RATA Model for the Job-Shop Scheduling

Download

331 downloads

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1007/978-3-642-37949-9_34,
    author={Farid Arfi and Jean-Michel Ili\^{e} and Djamel-Eddine Saidouni},
    title={Pruning Search Spaces of RATA Model for the Job-Shop Scheduling},
    proceedings={Quality, Reliability, Security and Robustness in Heterogeneous Networks. 9th International Conference, QShine 2013, Greader Noida, India, January 11-12, 2013, Revised Selected Papers},
    proceedings_a={QSHINE},
    year={2013},
    month={7},
    keywords={Scheduling reachability analysis timed model job-shop},
    doi={10.1007/978-3-642-37949-9_34}
}

Farid Arfi
Jean-Michel Ilié
Djamel-Eddine Saidouni
Year: 2013
Pruning Search Spaces of RATA Model for the Job-Shop Scheduling
QSHINE
Springer
DOI: 10.1007/978-3-642-37949-9_34

Farid Arfi¹^,*, Jean-Michel Ilié²^,*, Djamel-Eddine Saidouni¹^,*

1: University of Mentouri, MISC Laboratory
2: Paris 6 University, LIP6 Laboratory

*Contact email: arfi_f@hotmail.com, jean-michel.ilie@lip6.fr, saidouni@misc-umc.org

Abstract

In this paper, we propose a pruning method in order to reduce the search space for the job-shop scheduling problem with makespan minimization. In RATA model each trace corresponds to a feasible schedule, so we apply this method to the reachability algorithm of RATA model that explores the space of all possible schedules. We conducted an experimental study over a set of benchmarks. The results show that the proposed method is able to reduce both the space and the time in searching for optimal schedules.

Keywords: Scheduling reachability analysis timed model job-shop

Published: 2013-07-09

: http://dx.doi.org/10.1007/978-3-642-37949-9_34