The Application of Genetic Algorithms to Lot Streaming in Job-shop Scheduling Problem

摘要

A new approach using Genetic Algorithms (Gas) is proposed to determine Lot Streaming (LS) conditions in Job-shop Scheduling Problem (JSP). LS refers to a situation that a job (lot) can be split into a number of smaller jobs (sub-lots) so that successive operations of the same job can be overlapped. Consequently, the completion time of the whole job can be shortened such that the job can meet its due date. By applying the proposed approach called LS-GA, two sub-problems are solved simultaneously. The first problem is called LSP in which LS conditions are determined and the second problem is JSP after LS conditions are determined. Adopting Just-In-Time (JIT) philosophy, a number of test problems will be studied to investigate the optimum LS conditions such that all jobs can be finished close to their due dates. Computational results suggest that LS-GA works well with different objective measures and good solutions can be obtained with reasonable computational effort.