A memetic algorithm for minimizing total weighted tardiness on parallel batch machines with incompatible job families and dynamic job arrival
Journal
Computers and Operations Research
Journal Volume
37
Journal Issue
12
Pages
2257-2269
Date Issued
2010
Author(s)
Abstract
This paper addresses a scheduling problem motivated by scheduling of diffusion operations in the wafer fabrication facility. In the target problem, jobs arrive at the batch machines at different time instants, and only jobs belonging to the same family can be processed together. Parallel batch machine scheduling typically consists of three types of decisionsbatch forming, machine assignment, and batch sequencing. We propose a memetic algorithm with a new genome encoding scheme to search for the optimal or near-optimal batch formation and batch sequence simultaneously. Machine assignment is resolved in the proposed decoding scheme. Crossover and mutation operators suitable for the proposed encoding scheme are also devised. Through the experiment with 4860 problem instances of various characteristics including the number of machines, the number of jobs, and so on, the proposed algorithm demonstrates its advantages over a recently proposed benchmark algorithm in terms of both solution quality and computational efficiency. © 2010 Elsevier Ltd. All rights reserved.
SDGs
Type
journal article