A single-machine, single-wafer-processing, multiple-lots-per-carrier scheduling oroblem to minimize the sum of lot comoletion times

摘要

A high volume/high mix wafer fabrication facility processes customer orders (or lots) that are smaller in size. Because of their small sizes, a number of these lots are transported together in a carrier from one machine to another for processing. This is in contrast to transporting them individually, which would lead to an excessive number of mostly empty carriers, thereby resulting in a situation that would be prone to congestion and delays. At a machine, the wafers contained in a carrier are processed one-at-atime. The problem that we address in this paper is to configure a given set of identical carriers of known capacity with a given number of lots of various sizes for processing at a machine so that the sum of the completion times of the lots at the machine is minimized. The processing time of a carrier is the sum of the processing times of the wafers in it, and the completion time of each lot in a carrier is the same being equal to the completion time of the carrier. To develop an effective solution methodology, first, we consider carriers of an unlimited capacity. We develop some structural properties for this version of the problem that readily lead to its solution for the case of same-sized lots, and also, that help in devising an effective procedure for its solution when the lots are of different sizes. Then, we consider identical carriers of finite and known capacity and show that the problem is readily solvable if the lots are of the same size. For different-sized lots, we present a branch-and-bound-based method that exploits the structural properties that we develop. For the testbed of data used, the results of our experimental investigation reveal the efficacy of our branch-and-bound method over the direct solution by CPLEX 12.2 of two different mixed integer programming formulations of the problem. The proposed branch-and-bound method has the tendency of solving a problem at the root node itself, while CPLEX 12.2 cannot solve large-sized instances due to excessive memory requirements.