یک روش اکتشافی گلوگاه تغییر توزیع شده برای تولید کارگاهی کمپلکس

In this paper, we consider distributed versions of a modified shifting bottleneck heuristic for complex job shops. The considered job shop environment contains parallel batching machines, machines with sequence-dependent setup times and reentrant process flows. Semiconductor wafer fabrication facilities are typical examples for manufacturing systems with these characteristics. The used performance measure is total weighted tardiness (TWT). We suggest a two-layer hierarchical approach in order to decompose the overall scheduling problem. The upper (or top) layer works on an aggregated model. Based on appropriately aggregated routes it determines start dates and planned due dates for the jobs within each single work area, where a work area is defined as a set of parallel machine groups. The lower (or base) layer uses the start dates and planned due dates in order to apply shifting bottleneck heuristic type solution approaches for the jobs in each single work area. We conduct simulation experiments in a dynamic job shop environment in order to assess the performance of the heuristic. It turns out that the suggested approach outperforms a pure First In First Out (FIFO) dispatching scheme and provides a similar solution quality as the original modified shifting bottleneck heuristic.

The manufacturing of integrated circuits (IC) on silicon wafers is a production process of huge complexity (Schömig & Fowler, 2000; Uzsoy, Lee, & Martin-Vega, 1992). Up to 600 process steps on 50–120 di1fferent types of equipment are required to produce a chip of average complexity. A mix of different process types, i.e. batch processes and single wafer processes, sequence-dependent setup times, very expensive equipment and reentrant flows are typical for this type of manufacturing. Today, semiconductor manufacturing processes are additionally characterized by a wide and over time changing range of product types and the demand to achieve good delivery performance. Semiconductor wafer fabrication facilities (wafer fabs) are examples for complex job shops as introduced by Mason et al. (2002). A single product moves through the wafer fab in lots (jobs). Each lot consists of several (usually 24) wafers. The circuits are made up of layers. The recursive nature of the process flows is one of the main sources of difficulty in planning, scheduling and controlling wafer fabs. As indicated by Schömig and Fowler (2000), today it seems that better operational strategies are the main key in order to reduce costs and improve overall efficiency. New planning, scheduling and dispatching methods are required in order to reach the goal of better operational performance. The improved software and hardware capabilities have to be taken into account during the development of more sophisticated algorithms. It is now possible to solve large scale scheduling problems via decomposition methods. The power of distributed computation can be applied to solve the resulting subproblems of the decomposition process in a simultaneous manner. The shifting bottleneck heuristic may serve as the prominent example for job shop decomposition approaches. However, centralized implementations of the shifting bottleneck heuristic are still very time consuming from a runtime point of view even in the case of moderate scheduling horizons (Mönch & Rose, 2004). In the situation of a larger scheduling horizon, for example of 2 days, the number of nodes of the scheduling graph grows tremendously, hence the solution of the scheduling problem requires large computational efforts in terms of memory and computation time. On the other hand, considering a small scheduling horizon leads to the problem of proper internal due date setting that is very often difficult. Based on a proper physical decomposition of the manufacturing system into subsystems, called work areas, we use a rather simple job planning approach in order to assign internal ready times and internal due dates to each job with respect to the decomposition of the job shop into work areas. Based on the internal ready times and due dates, we apply a modified shifting bottleneck heuristic to each single work area in order to come up with detailed schedules for each single work area. The paper is organized as follows. We describe the problem and introduce notations in Section 2. We discuss related work in Section 3. A modified shifting bottleneck heuristic is very briefly discussed in Section 4. Then we describe distributed versions of the shifting bottleneck heuristic. In Section 5, we describe the simulation framework used for assessing the performance of the distributed shifting bottleneck heuristic. We continue with presenting the experimental design and the results of computational experiments in Section 5.

In this paper, we discuss several variants of a distributed shifting bottleneck heuristic for complex job shops. We describe the basic two-layer hierarchy and the suggested algorithms. We present results of computational experiments in a simulated wafer fab environment that clearly show that the suggested algorithms outperform dispatching rules and provide a similar solution quality as the original modified shifting bottleneck heuristic. In future research, we have to assess the performance of a distributed implementation of our algorithms. So far, only preliminary results of computational experiments are available that measure the speed up effect of the suggested distribution strategy. It seems that especially for Model B and Model C the running time of the algorithms is significantly decreased. Up to now, only the conceptually very simple ICA approach is used for determining the internal due dates and ready times. However, we believe that a further performance improvement of the distributed shifting bottleneck heuristic is possible by using a finite capacity production control algorithm. Such a production control algorithm based on the beam search approach is provided, for example, by Habenicht and Mönch (2002). Furthermore, it seems to be interesting to consider several rescheduling strategies in an environment with machine breakdowns.