Open Science Research Excellence

Marco Antonio Cruz Chavez

Publications

1

Publications

1
15077
The Problem of Using the Calculation of the Critical Path to Solver Instances of the Job Shop Scheduling Problem
Abstract:

A procedure commonly used in Job Shop Scheduling Problem (JSSP) to evaluate the neighborhoods functions that use the non-deterministic algorithms is the calculation of the critical path in a digraph. This paper presents an experimental study of the cost of computation that exists when the calculation of the critical path in the solution for instances in which a JSSP of large size is involved. The results indicate that if the critical path is use in order to generate neighborhoods in the meta-heuristics that are used in JSSP, an elevated cost of computation exists in spite of the fact that the calculation of the critical path in any digraph is of polynomial complexity.

Keywords:
Job Shop, CPM, critical path, neighborhood, meta-heuristic.