Research Article
Pruning Search Spaces of RATA Model for the Job-Shop Scheduling
347 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
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.
Copyright © 2013–2024 ICST
