Production Planning in Automated Manufacturing

During the last two decades, the impact of automation on manufacturing has sharply increased. Nowadays, computers can play a role in every aspect of the production process, ranging from the design of a new product to the inspection of its quality. In some types of industry automated manufacturing has a long history, for instance in chemical or oil-refining industries. However, in the batch-manufacturing industries, like the metalworking industry or the electronics industry, the concept of automated manufacturing was introduced only in the 1970’s, causing a profound effect on manufacturing and the way it is organized So-called flexible manufacturing systems (FMSs) emerged as a critical component in the development towards the “factory of the future”. Our focus will be on this type of industry. On the one hand, automated manufacturing has a wide variety of potential benefits to offer to batch-manufacturing industries. One of the most important advantages is the increased ability to respond to changes in demand. This is important in view of today’s fast changing demand and short product cycles. Other possible advantages include shorter lead times, lower inventories and higher machine utilization. On the other hand, it is not an easy task to make an efficient use of the newly offered possibilities. In particular, planning the use of a system consisting of a number of connected, complicated machines using limited resources can constitute a formidable challenge.

The electronics industry relies heavily on numerically controlled machines for the placement of electronic components on the surface of printed circuit boards (PCB). These placement (or mounting, or pick-and-place) machines automatically insert components into PCB’s, in a sequence determined by the input program. The most recent among them are characterized by high levels of accuracy and speed, but their throughput rates still appear to be extremely sensitive to the quality of the instructions. On the other hand, the effective programming of the machines becomes steadily more difficult in view of the increasing sophistication of the available technology. The development of optimization procedures allowing the efficient operation of such placement machines therefore provides an exciting challenge for the operations research community, as witnessed by, e.g., the recent papers by Ahmadi, Grotzinger and Johnson (1988), Ball and Magazine (1988), and Leipälä and Nevalainen (1989).

Consider the following classical formulation of the (axial) three-dimensional assignment problem (3DA) (see e.g. Balas and Saltzman (1989)). Given is a complete tripartite graph K _{n,n, n} = (I∪J∪K,(I × J) ∪ (I × K) ∪ (J × K)), where I, J, K are disjoint sets of size n, and a cost c _ijk for each triangle (i, j, k) ∈ I × J × K. The problem 3DA is to find a subset A of n triangles, A⊆ I × J × K, such that every element of I ∪ J ∪ K occurs in exactly one triangle of A, and the total cost c(A) = ∑_(i,j,k)∈A c _ijk is minimized. Some recent references to this problem are Balas and Saltzman (1989), Frieze (1974), Frieze and Yadegar (1981), Hansen and Kaufman (1973).

The following problem is studied in this chapter. Given are n jobs, which have to be processed on a single machine within the timespan [0, T]. In our formulation, we assume T to be an integer, and the timespan is discretized into T time periods (or periods) of length one, viz. [0,1], [1, 2],..., [T − 1, T]. Thus, period t refers to the time slot [t − 1, t], t = 1,...,T. The machine can handle at most one job at a time. The processing time, or length, of each job equals p, p ∈ ℕ. The processing cost of each job is an arbitrary function of its start-time: we denote by c _jt the cost of starting job j in period t. The problem is to schedule all jobs so as to minimize the sum of the processing costs. We refer to this problem as problem SEL (Scheduling jobs of Equal Length).

In this chapter we identify some basic models for production planning in FMSs. In doing so, we set the stage for Chapters 6–9 where some of these models are more thoroughly investigated.

An FMS consists of a number of numerically controlled machines, linked by automated material handling devices, that perform the operations required to manufacture parts. The tools required by these operations are stored in a limited capacity tool magazine attached to each machine. An automated tool interchanging device enables the machine to interchange tools very quickly (in seconds). This fast tool interchanging capability avoids costly setups while producing with the tools available in the magazine, and is an essential feature of FMSs. When it becomes necessary to add tools to the tool magazine to allow new operations, the machine sometimes has to be shutdown while the tools are interchanged, after which the machine may resume production. The latter type of setup is time-consuming (it may take up to two hours). The performance of an FMS may therefore be considerably boosted by reducing the occurrences of these setups.

In Chapter 6 the job grouping problem for flexible manufacturing systems has been studied. This chapter concentrates on extensions of the previous model. First, the extension where tools may require several slots in the tool magazine is discussed. Next, we consider the case where several identical machines are necessary for production. In both cases, the procedures used in Chapter 6 are extended to derive strong lower and upper bounds on the optimal value of the problem and results of computational experiments are presented. In Section 7.4 we discuss the possibility to incorporate due dates in the model. Section 7.5 summarizes and concludes the chapter.

In Chapters 6 and 7, lower and upper bounding procedures were proposed for the job grouping problem. It appeared that, in many cases, sequential heuristic procedures were not sufficient to provide an optimal solution. A column generation approach was also developed to compute a strong lower bound, based on the linear relaxation of the set covering formulation of the job grouping problem. In the course of this procedure, it was sometimes possible to derive improved upper bounds. Notice, however, that solving the job grouping problem may be done faster if a better upper bound is known from the start. For instance, execution of the column generation procedure can be avoided if simple lower bounds like LB _SW and LB _MSW (see Chapters 6 and 7) are optimal and an optimal upper bound is also available. Alternatively, improved solutions provide additional columns to be included in the set covering formulation, which may speed up the column generation procedure.

A central problem of tool management for flexible machines is to decide how to sequence the parts to be produced, and what tools to allocate to the machine, in order to minimize the number of tool setups. The problem becomes especially crucial when the time needed to change a tool is significant with respect to the processing times of the parts, or when many small batches of different parts must be processed in succession. These phenomena have been observed in the metal-working industry by Hirabayashi, Suzuki and Tsuchiya (1984), Finke and Kusiak (1987), Bard (1988), Tang and Denardo (1988a), Bard and Feo (1989), etc. Blazewicz, Finke, Haupt and Schmidt (1988) describe for instance an NC-forging machine equipped with two tool magazines, each of which can handle eight tools. The tools are very heavy, and exchanging them requires a sizeable fraction of the actual forging time. Another situation where minimizing the number of tool setups may be important is described by Förster and Hirt (1989, p. 109). These authors mention that, when the tool transportation system is used by several machines, there is a distinct possibility that this system becomes overloaded. Then, minimizing the number of tool setups can be viewed as a way to reduce the strain on the tool transportation system. Bard (1988) mentions yet another occurrence of the same problem in the electronics industry. Suppose several types of printed circuit boards (PCBs) are produced by an automated placement machine (or a line of such machines).