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
271 downloads
  • @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 Arfi1,*, Jean-Michel Ilié2,*, Djamel-Eddine Saidouni1,*
  • 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.