A memetic algorithm for minimizing total weighted tardiness on parallel batch machines with incompatible job families and dynamic job arrival

Tsung-Che Chiang, Hsueh Chien Cheng, Li Chen Fu

Research output: Contribution to journalArticle

46 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)2257-2269
Number of pages13
JournalComputers and Operations Research
Issue number12
Publication statusPublished - 2010 Dec 1



  • Batch processing machine
  • Memetic algorithm
  • Scheduling
  • Total weighted tardiness

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this