Combining global pruning rules with depth-first search for the job shop scheduling problem with operators
Publication date:
Abstract:
We propose an enhanced depth- rst heuristic search algorithm to face the job shop scheduling problem with operators. This problem extends the classical job shop scheduling problem by considering a limited number of human operators that assist the processing of the operations. We considered total ow time minimization as objective function which makes the problem harder to solve and more interesting from a practical point of view than minimizing the makespan. The proposed method exploits a schedule generation scheme termed OG&T, two admissible heuristics and some powerful global pruning rules that require recording expanded states. We have conducted an experimental study across several benchmarks to evaluate our algorithm. The results show that the global pruning method is really e ective and that the proposed approach is quite competent for solving this problem
We propose an enhanced depth- rst heuristic search algorithm to face the job shop scheduling problem with operators. This problem extends the classical job shop scheduling problem by considering a limited number of human operators that assist the processing of the operations. We considered total ow time minimization as objective function which makes the problem harder to solve and more interesting from a practical point of view than minimizing the makespan. The proposed method exploits a schedule generation scheme termed OG&T, two admissible heuristics and some powerful global pruning rules that require recording expanded states. We have conducted an experimental study across several benchmarks to evaluate our algorithm. The results show that the global pruning method is really e ective and that the proposed approach is quite competent for solving this problem
Patrocinado por:
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
Collections
- Informática [813]
- Ponencias, Discursos y Conferencias [4117]
Files in this item
