Optimization Online


A two-step optimization approach for job shop scheduling problem using a genetic algorithm

Jorge Magalhaes-Mendes (jjm***at***isep.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
Entry Accepted: 01/16/2013
Entry Last Modified: 10/18/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society