PRUNING SEARCH SPACE BY DOMINANCE RULES IN BEST FIRST SEARCH FOR THE JOB SHOP SCHEDULING PROBLEM

María R. Sierra, Ramiro Varela

2008

Abstract

Best-first graph search is a classic problem solving paradigm capable of obtaining exact solutions to optimization problems. As it usually requires a large amount of memory to store the effective search space, in practice it is only suitable for small instances. In this paper, we propose a pruning method, based on dominance relations among states, for reducing the search space. We apply this method to an A∗ algorithm that explores the space of active schedules for the Job Shop Scheduling Problem with makespan minimization. The A∗ algorithm is guided by a consistent heuristic and it is combined with a greedy algorithm to obtain upper bounds during the search process. We conducted an experimental study over a conventional benchmark. The results show that the proposed method is able to reduce both the space and the time in searching for optimal schedules so as it is able to solve instances with 20 jobs and 5 machines or 9 jobs and 9 machines. Also, the A∗ is exploited with heuristic weighting to obtain sub-optimal solutions for larger instances.

Paper Citation

in Harvard Style

R. Sierra M. and Varela R. (2008). PRUNING SEARCH SPACE BY DOMINANCE RULES IN BEST FIRST SEARCH FOR THE JOB SHOP SCHEDULING PROBLEM . In Proceedings of the Third International Conference on Software and Data Technologies - Volume 1: ICSOFT, ISBN 978-989-8111-51-7, pages 273-280. DOI: 10.5220/0001896102730280

in Bibtex Style

@conference{icsoft08,
author={María R. Sierra and Ramiro Varela},
title={PRUNING SEARCH SPACE BY DOMINANCE RULES IN BEST FIRST SEARCH FOR THE JOB SHOP SCHEDULING PROBLEM},
booktitle={Proceedings of the Third International Conference on Software and Data Technologies - Volume 1: ICSOFT,},
year={2008},
pages={273-280},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001896102730280},
isbn={978-989-8111-51-7},
}

in EndNote Style

TY - CONF
JO - Proceedings of the Third International Conference on Software and Data Technologies - Volume 1: ICSOFT,
TI - PRUNING SEARCH SPACE BY DOMINANCE RULES IN BEST FIRST SEARCH FOR THE JOB SHOP SCHEDULING PROBLEM
SN - 978-989-8111-51-7
AU - R. Sierra M.
AU - Varela R.
PY - 2008
SP - 273
EP - 280
DO - 10.5220/0001896102730280