RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación
Artículo científico (JournalArticle)
Solving the job shop scheduling problem with operators by depth-first heuristic search enhanced with global pruning rules
The job shop scheduling problem with an additional resource type has been recently proposed to model the situation
where each operation in a job shop has to be assisted by one of a limited set of human operators. We confront this problem with
the objective of minimizing the total flow time, which makes the problem more interesting from a practical point of view and
harder to solve than the version with makespan minimization. To solve this problem we propose an enhanced dept-first search
algorithm. This algorithm exploits a schedule generation schema termed OG&T, two admissible heuristics and some powerful
pruning rules. In order to diversify the search, we also consider a variant of this algorithm with restarts. We have conducted an
experimental study across several benchmarks. The results of this study show that the global pruning rules are really effective
and that the proposed algorithms are quite competent for solving this problem., We are grateful to the anonymous referees for their comments and suggestions, that made it possible to improve this paper. This research has been supported by the Spanish Government under projects MEC-FEDER TIN-20976-C02-01 and TIN-20976-C02-02 and by the Principality of Asturias under Grant FICYT-BP09105.