Re-entrant permutation flow shop problems occur in practical applications such as wafer manufacturing, paint shops, mold and die processes and textile industry. A re-entrant material flow means that the production jobs need to visit at least one working station multiple times. A comprehensive review gives an overview of the literature on re-entrant scheduling. The influence of missing operations received just little attention so far and splitting the jobs into sublots was not examined in re-entrant permutation flow shops before. The computational complexity of makespan minimization in re-entrant permutation flow shop problems requires heuristic solution approaches for large problem sizes. The problem provides promising structural properties for the application of a variable neighborhood search because of the repeated processing of jobs on several machines. Furthermore the different characteristics of lot streaming and their impact on the makespan of a schedule are examined in this thesis and the heuristic solution methods are adjusted to manage the problem’s extension.

In semiconductor manufacturing, wafers are grouped into lots and sent to a separate facility for assembly and test (AT) before being shipped to the customer. Up to a dozen operations are required during AT. The facility in which these operations are performed is a reentrant flow shop consisting of several dozen to several hundred machines and up to a thousand specialized tools. Each lot follows a specific route through the facility, perhaps returning to the same machine multiple times. Each step in the route is referred to as a "pass." Lots in work in process (WIP) that have more than a single step remaining in their route are referred to as multi-pass lots. The multi-pass scheduling problem is to determine machine setups, lot assignments and lot sequences to achieve optimal output, as measured by four objectives related to key device shortages, throughput, machine utilization, and makespan, prioritized in this order. The two primary goals of this research are to develop a new formulation for the multipass problem and to design a variety of solution algorithms that can be used for both planning and real-time control. To begin, the basic AT model considering only single-pass scheduling and the previously developed greedy randomized adaptive search procedure (GRASP) along with its extensions are introduced. Then two alternative schemes are proposed to solve the multipass scheduling problem. In the final phase of this research, an efficient procedure is presented for prioritizing machine changeovers in an AT facility on a periodic basis that provides real-time support. In daily planning, target machine-tooling combinations are derived based on work in process, due dates, and backlogs. As machines finish their current lots, they need to be reconfigured to match their targets. The proposed algorithm is designed to run in real time. / text