This paper presents a two-step optimization approach to solve the complex scheduling problem in a job shop environment. This problem is also known as the Job Shop Scheduling Problem (JSSP). The JSSP is a difficult problem in combinatorial optimization for which extensive investigation has been devoted to the development of efficient algorithms. The proposed approach is based on a genetic algorithm. Genetic algorithms are an optimization methodology based on a direct analogy to Darwinian natural selection and mutations in biological reproduction. The chromosome representation of the problem is based on random keys. The schedules are constructed using a schedule generation scheme in which the priorities and delay times of the operations are defined by the genetic algorithm and obtaining parameterized active schedules. After a schedule is obtained a local search heuristic using Monte Carlo method is applied to improve the solution. The approach is tested on a set of standard instances taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed approach.
Working Paper 06.2013, Instituto Superior de Engenharia do Porto, Portugal