A memetic algorithm to minimize the total sum of earliness tardiness and sequence dependent setup costs for flow shop scheduling problems with job distinct due windows

Abstract

The research considers the flow shop scheduling problem under the Just-In-Time (JIT) philosophy. There are n jobs waiting to be processed through m operations of a flow shop production system. The objective is to determine the job schedule such that the total cost consisting of setup, earliness, and tardiness costs, is minimized. To represent the problem, the Integer Linear Programming (ILP) mathematical model is created. A Memetic Algorithm (MA) is developed to determine the proper solution. The evolutionary procedure, worked as the global search, is applied to seek for the good job sequences. In order to conduct the local search, an optimal timing algorithm is developed and inserted in the procedure to determine the best schedule of each job sequence. From the numerical experiment of 360 problems, the proposed MA can provide optimal solutions for 355 problems. It is obvious that the MA can provide the good solution in a reasonable amount of time.

Keywords

• flow shop scheduling
• earliness tardiness
• due window
• optimal timing algorithm
• Memetic Algorithm