Comparing Schedule Generation Schemes in Memetic Algorithms for the Job Shop Scheduling Problem with Sequence Dependent Setup Times

摘要

The Job Shop Scheduling Problem with Sequence Dependent Setup Times (SDJSS) is an extension of the Job Shop Scheduling Problem (JSS) that has interested to researchers during the last years. In this paper we confront the SDJSS problem by means of a memetic algorithm. We study two schedule generation schemas that are extensions of the well known G&T algorithm for the JSS. We report results from an experimental study showing that the proposed approaches produce similar results and that both of them are more efficient than other genetic algorithm proposed in the literature.