SCHEDULING FOR A SINGLE SEMICONDUCTOR BATCH-PROCESSING MACHINE TO MINIMIZE TOTAL WEIGHTED TARDINESS

ABSTRACT

This paper considers the scheduling problem of a single semiconductor batch-processing machine with job release times, non-identical job sizes, distinct due dates, and weights to minimize the total weighted tardiness. A batch-processing machine can process several jobs simultaneously as a batch, and the processing time of a batch is equal to the longest processing time among all jobs in the batch. According to the literature review of Mathirajan and Sivakumar and the studies of Perez et al., the problem dealt with in this paper has not been studied so far. Therefore, we proposed a mathematical modeling approach and two kinds of hybrid heuristics, including a rule-based algorithm and a genetic algorithm based (GA-based) algorithm in which a dynamic programming (DP) algorithm is integrated to obtain an optimal batching solution for a given job sequence. The experimental results indicated that job sequence is an important factor for the problem. Particularly, the GA-based algorithm significantly outperformed the rule-based algorithm in terms of the quality of solutions for small-job problems. Likewise, the solutions were obviously considerably improved compared with the mathematical modeling approach for large-job problems.

Keywords:

• total weighted tardiness
• dynamic programming
• batch-processing machine scheduling
• genetic algorithm