Associate Professor Tsung-Che Chiang

Department of Computer Science and Information Engineering
National Taiwan Normal University

Tel: +886-2-77346692    Fax: +886-2-29322378    Email

Tsung-Che Chiang, Hsueh-Chien Cheng, and Li-Chen Fu, A memetic algorithm for minimizing total weighted tardiness on parallel batch machines with incompatible job families and dynamic job arrival, Computers & Operations Research, vol. 37, no. 12, pp. 2257 - 2269, 2010.

Full text: ScienceDirect ; Unedited version

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 decisions – batch 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.

Benchmark algorithm : L. Mönch, H. Balasubramanian, J. W. Fowler, and M. E. Pfund, "Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times," Computers & Operations Research, vol. 32, no. 11, pp. 2731 - 2750, 2005.

Benchmark problem instances: Download