Scientific Research and Essays

  • Abbreviation: Sci. Res. Essays
  • Language: English
  • ISSN: 1992-2248
  • DOI: 10.5897/SRE
  • Start Year: 2006
  • Published Articles: 2768

Full Length Research Paper

Lot streaming based job-shop scheduling problem using hybrid genetic algorithm

Serdar Birogul1*, Cetin Elmas 2 and Tuncay Yigit 3
  1Research and Development Department, Caretta Software, Istanbul, Turkey. 2Department of Electrical, Technical Education Faculty, Gazi University, Ankara, Turkey. 3Department of Computer Engineering, Engineering Faculty, Suleyman Demirel University, Isparta, Turkey.
Email: [email protected], [email protected]

  •  Accepted: 20 October 2010
  •  Published: 31 July 2011

Abstract

 

Job shop scheduling problems (JSSP’s) are computationally complex problems. Lot streaming (LS) is the process of splitting a job into sublots to reduce its makespan on a sequence of machines. A lot can be split into a number of smaller lots in JSSP. However, planning decisions become more complex when lot streaming is allowed. Thus, the solution can be minimized both the idle time and total working time. In modern manufacturing environment, a factor that effects the scheduling is the size of lot streaming. In this paper, it is examined how the lot streaming affects both the Gantt scheme and the genetic algorithm, and how to adapt the Hybrid Genetic Algorithms (HGA) to JSSP. HGA has a new repair operator, together with crossover and mutation operators. Experiments are conducted to show the effectiveness of the proposed repair algorithm.

 

Key words: Job-shop scheduling problem, genetic algorithms, lot streaming.