Optimization models and algorithms for part routing and scheduling in a wafer fab

In the first part of our investigation, we consider the problem of moving production lots within the cleanroom of LFoundry, an important Italian manufacturer of microelectronic devices. The model adopted is a DIAL-A-RIDE PROBLEM (DARP). We propose a math-heuristic, specifically designed for use in a dynamic environment, with the objective of balancing vehicle workloads. This objective is achieved by minimizing, at each optimization cycle, the makespan, i.e., the largest completion time among the vehicles. A cluster-first route-second heuristic is devised for online use and compared to the actual practice through a computational experience based on real plant data. In the perspective of a comparison of the solutions obtained to the optimum or to lower bounds, and also to address such details as in-process inventory, we developed an original INVENTORY DARP and formulated it in terms of Mixed Integer Programming (MIP). This problem has not been considered yet in the vehicle routing literature. Due to its inherent complexity, our MIP formulation was just useful to find optima in small problem instances, being inapplicable to those derived from real size. Anyway, this piece of research gave us interesting indications for future studies. In the second part of the thesis, we present a mathematical model to deal with a problem that often arises in those manufacturing contexts where industrial parts are obtained by cutting sheets or bars of raw material. In such contexts, the production quality might be harmed by the occurrence of faults in the sheets. In our study, we focus on a ONE-DIMENSIONAL BIN PACKING PROBLEM (1-BPP) and consider the problem of finding limited trim-loss solutions which also minimize the expected loss of parts derived from small faulty areas. We first address the problem of computing the expected loss, then the more complex one of finding a BIN PACKING that is most robust against random faults. Two heuristics based on the solution of a suitable MULTIPROCESSOR SCHEDULING PROBLEM are designed and tested.