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.