A two-step optimization approach for job shop scheduling problem using a genetic algorithm
Jorge Magalhaes-Mendes (jjmisep.ipp.pt)
Abstract: 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.
Keywords: Scheduling; Discrete Optimization; Genetic Algorithm; Job Shop; heuristics.
Category 1: Applications -- OR and Management Sciences
Category 2: Applications -- OR and Management Sciences (Scheduling )
Citation: Working Paper 06.2013, Instituto Superior de Engenharia do Porto, Portugal
Entry Submitted: 01/16/2013
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|