(PDF) Order Consolidation for Batch Processing

Journal of Combinatorial Optimization, 9, 121–138, 2005 c 2005 Springer Science + Business Media, Inc. Manufactured in The Netherlands. Order Consolidation for Batch Processing HARK-CHIN HWANG Department of Industrial Engineering, Chosun University, 375 Seosuk-Dong, Dong-Gu, Gwangju 501-759, Republic of Korea SOO Y. CHANG∗

Department of Industrial Engineering, Division of Electrical and Computer Engineering, Pohang University of Science and Technology, Hyoja Dong San 31, Pohang, 790-784, Kyungbuk, Republic of Korea Received March 3, 2003; Revised January 12, 2004; Accepted April 9, 2004 Abstract. We consider the batch processing of orders where either whole or part of a single order or a specific pair of different orders may be grouped in a batch with a fixed capacity. The problem can be modelled by a graph G = (V, E), where each node v ∈ V corresponds to an order, its weight w(v) corresponds to the amount of ordered quantity and a pair of orders, say u and v may be grouped in a batch if there exists the edge (u, v) ∈ E. The objective is to maximize the number of batches filled up to its capacity λ. In this paper, we prove that the problem is NP-hard and, moreover, that no PTAS exists unless P = NP. Then, an optimal algorithm is developed with running time O(|V | log |V |) for the special case when G is a tree. Keywords: batch processing, three dimensional matching, tree 1. Introduction In industries like the steel or chemical industries, the production is done mostly in batch mode where each batch yields fixed amount of products that are identical or very similar in nature. In such production environment, grouping orders to form batches can be quite cumbersome unless the ordered quantities are given in exact integer multiples of the batch size. Especially, when customer orders are given in large variety, consolidating similar orders to form as many batches as possible becomes a task crucial for ensuring the batch production efficiency. In this paper, we consider the case where single or a specific pair of orders may be grouped in a batch. A real world example for this particular case would be the continuous casting operation in steel mills where steel grade and slab specifications in a batch must be close to each other (Chang et al., 2000; Tang et al., 2001). The continuous caster converts a batch of molten steel into solid steel slabs which are the most important work-in-process inventory items in steel mills. As a way to better control the slab inventory, slabs are often manufactured in limited variety of physical dimensions, namely, in a few standardized sizes. Hence, customer orders demanding different final steel products are often fulfilled by processing slabs with the same standardized size. In effect, slabs designated to more than ∗ Corresponding author. 122 HWANG AND CHANG one customer orders may be produced from the same batch of molten steel at the continuous caster. We generalize this situation and model our problem by the use of an undirected graph G = (V, E), where V is a finite set of nodes and E is a set of edges. Each node v ∈ V is defined for each individual order and assigned the weight w(v) of the corresponding ordered quantity. The edge e = (u, v) ∈ E is defined whenever the pair of orders corresponding to the node u and v are allowed to be grouped to form a batch. Two types of batches are allowed to be formed. The batch consisting of the whole or portion of the weight of a single node is called a homogeneous batch. The batch consisting of the whole or portions of the weights of a pair of nodes connected by an edge is called a heterogeneous batch. Our objective is to maximize the total number of batches that can be formed under the constraint that each batch is completely filled up to the batch size λ. In the literature, there have been extensive researches into batching or grouping of or- ders with the purpose of maximizing efficiency. Some of the works deal with scheduling of batches as well as batcing of orders with regular objective functions like minimizing makespan, total (weighted) completion time, or maximum lateness, etc. In these works, batching occurs when machines require setups if they are to process jobs that have differ- ing characteristics (Potts and Kovalyov, 2000). Also, batching is needed when a batching machine is capable of processing several jobs simultaneously (Potts and Kovalyov, 2000) as in ‘burn-in’ operations for circuits in semiconductor industry (Lee et al., 1992). In the burn-in model, Uzsoy (1995) also deal with bacthing machine problem for the multiple incompatible job families where only homogeneous batches (consisting of jobs from the same family) are allowed to be constructed. Other works have focused on batching without scheduling in the name of job grouping. Crama and Oerllemans (1994) study a flexible manufacturing system in which jobs are needed to be grouped considering their tool types used in a machine. To minimize the number of setups between batch operations, they try to find a solution with minimal number of job groups. Also, Knuutila and Nevalainen (2002) considers job grouping problem in the automated assembly of electronic components on printed circuit boards. The problem concerned in this paper is about bacthing like job grouping problems rather than batching with scheduling. However, note that the objective function in our problem is to maximize the number of feasible batches, which is different from that of the job grouping problem, i.e., minimization of the number of setups. Though the setup time from switching operations in continuous casting is not small, the objective of maximizing batching instances is considered more significant under the situation that batching itself is limited for the purpose of producing standardized products. Chang et al. (2000) first deal with the problem of this type in which the objective is to make batches as many as possible satisfying the various batching constraints specific to steel industry. An integer programming model is established and an efficient heuristic based on column generation approach is proposed. In fact, our model is a generalization of that in Chang et al. (2000) using graph theoretic approach, where constraints on batching are represented by edges between nodes. Note that when λ = 2, and w(v) = 1 for each v ∈ V , our problem is equivalent to the maximum cardinality matching problem, for which optimal algorithms are known as in Micali and Vazirani (1980) and Papadimitriou and Steiglitz (1988). However, as shown ORDER CONSOLIDATION FOR BATCH PROCESSING 123 in Section 3, finding an optimum solution to our problem is very hard in general since the NP-complete problem known as the three-dimensional matching can be reduced to a special case of our problem. The best result in solving hard optimization problems theoretically would be a polynomial time approximation scheme. An (1 − )-approximation algorithm, 0 < < 1, for maximization problems is any polynomial time algorithm that produces solutions with objective function value at least (1 − ) times optimum. Then, a polynomial time approximation scheme (PTAS) is a family of (1 − )-approximation algorithms for any value of 0 < < 1. Unfortunately, it will be shown that no PTAS exists for our problem unless P = N P. Hence, our problem is not only hard but also nonapproximable, in general. Therefore, in this paper, we develop an optimal algorithm for a special class of our problem where the graph G is a tree. In the next section, we develop a formal mathematical model of our problem. In Section 3, we prove that the three-dimensional matching problem can be reduced to our problem and also that our problem belongs to Max SNP-hard class, for which no PTAS exists unless P = N P. Then, based on the analysis presented in Sections 4 and 5, we develop an optimal algorithm in Section 6. Then, the conclusion follows. 2. Problem definition A heterogeneous batch for an edge e = (u, v) is denoted by a two-dimensional vector xe = (xe (u), xe (v)) where xe (u) and xe (v) are the portions of w(u) and w(v), respectively, which together satisfy xe (u) + xe (v) = λ. The following lemma shows that it is enough to consider only the solutions with no more than one heterogeneous batch on each edge. Lemma 1. Given two heterogeneous batches for e = (u, v) ∈ E, we can make either two homogeneous batches or one homogeneous and one heterogeneous batch. Proof: Suppose that we are given two heterogeneous batches x̄e and x̂e for an edge e = (u, v) ∈ E and assume x̄e (u) + x̂e (u) ≥ x̄e (v) + x̂e (v), without loss of generality. If x̄e (u) + x̂e (u) = λ, x̄e (v) + x̂e (v) = λ must hold and, hence, we can construct two homogeneous batches, one from x̄e (u) and x̂e (u) and the other from x̄e (v) and x̂e (v). If x̄e (u) + x̂e (u) > λ, we can make one homogeneous batch from x̄e (u) and x̂e (u) and one heterogeneous batch xe by setting; xe (u) = x̄e (u) + x̂e (u) − λ, xe (v) = x̄e (v) + x̂e (v). Due to this lemma, we may use the binary variable ye to represent the heterogenous batch for each edge e = (u, v) defined as ye = 1, if and only if xe (u) > 0, xe (v) > 0, and xe (u) + xe (v) = λ, while ye = 0, if and only if xe (u) = 0 and xe (v) = 0. To represent the homogeneous batches defined for each node v, we use the integer variable yv . The set E(v) is defined for each node v to denote the set of every edge having the node v as one of the connected nodes. Then the mathematical model for our problem, that we call IP1, can be 124 HWANG AND CHANG written as the following. Maximize yv + ye v∈V e∈E Subject to λye − xe (u) − xe (v) = 0 for e = (u, v) ∈ E (1) λyv + xe (v) ≤ w(v) for v ∈ V (2) e∈E(v) xe (v) ≥ 0 for v ∈ V and e ∈ E(v) (3) yv ≥ 0 integer for v ∈ V (4) ye ∈ {0, 1} for e ∈ E (5) 3. Hardness and nonapproximability We first see the hardness of our problem IP1 by showing that the well known NP-complete problem, the three-dimensional matching, can be reduced to a special case of our problem. Furthermore, based on the same reduction, we also prove that IP1 is Max SNP-hard, which shows nonexistence of PTAS in case that P = NP. The reduction from the three-dimensional matching to IP1 is quite similar to the Theorem 3.7 in Garey and Johnson (1979). Three-dimensional matching (3DM) Instance: Disjoint sets A = {a1 , . . . , an }, B = {b1 , . . . , bn }, C = {c1 , . . . , cn } and a family F = {T1 , . . . , Tm } of triples with |Ti ∩ A| = |Ti ∩ B| = |Ti ∩ C| = 1 for i = 1, . . . , m. A matching is a subset F ⊆ F such that no two triples of F agree in any coordinate. Question: Does F contain a matching with cardinality n, that is, a subfamily F for which |F | = n and ∪Ti ∈F Ti = A ∪ B ∪ C? Theorem 2. 3DM can be reduced to our problem IP1 in polynomial time. Proof: Given an instance of 3DM, we construct an instance of our problem with the batch size λ = 3. We define one node for each element in the set A, B and C. Then for each triple Ti = {a j , bk , cl }, we construct a set E i of seven edges and five nodes as shown in figure 1, where the weight of each node is the number in the circle. Then, define V and E of G as; m V = (A ∪ B ∪ C) ∪ {vi j : 1 ≤ j ≤ 5}, i=1 m E= Ei . i=1 ORDER CONSOLIDATION FOR BATCH PROCESSING 125 Figure 1. The graph for triple Ti = {a j , bk , cl }. Note that the total sum of weights of V is w(v) = |A ∪ B ∪ C| + 9|F| = 3(n + 3m). v∈V Suppose F is a matching. Then, for each Ti ∈ F , construct batches by setting yei1 =1 (xei1 (a j ) = 1, xei1 (vi1 ) = 2), yei3 =1 (xei3 (bk ) = 1, xei3 (vi3 ) = 2), yei5 =1 (xei5 (cl ) = 1, xei5 (vi5 ) = 2), yei7 =1 (xei7 (vi2 ) = 1, xei7 (vi4 ) = 2), / F construct batches by setting and for each Ti ∈ yei2 = 1 (xei2 (vi1 ) = 2, xei2 (vi4 ) = 1), yei4 = 1 (xei4 (vi3 ) = 2, xei4 (vi2 ) = 1), yei6 = 1 (xei6 (vi5 ) = 2, xei6 (vi4 ) = 1). Conversely, suppose that y is any solution with n + 3m batches, that is, e∈E ye = n + 3m. Then, the matching F can be constructed by collecting Ti ∈ F for each yei7 = 1. Now, we consider the question on the existence of PTAS for our problem IP1. To this end, we need to define the concept of L-reduction introduced by Papadimitriou and Yannakakis (1991). Definition 3. Let and be two optimization problems. For each instance of I (I ) of ( ) we let S(I ) (S (I )) be the set of feasible solutions and z(x) (z (x )) be the value of 126 HWANG AND CHANG objective function for the solution x ∈ S(I ) (x ∈ S (I )), respectively. An L-reduction from to is a pair of polynomial time computable functions f and g with the following two conditions: • The function f maps from instances I of to instances I of such that OPT(I ) ≤ α · OPT(I ), for some positive constant α. • The function g is a mapping from feasible solutions of S (I ) to feasible solutions of S(I ) such that for every x ∈ S (I ) |OPT(I ) − z(g(x ))| ≤ β · |OPT(I ) − z (x )|, for some positive constant β. Papadimitriou and Yannakakis (1991) also define a class of optimization problems called Max SNP, and show that this class is closed under L-reduction. The hardest problems in this class are called Max SNP-complete (with respect to L-reduction) and a problem at least as hard as a Max SNP-complete is called Max SNP-hard. For the Max SNP-hard problems, it has been proven that no PTAS exits unless P = NP by Arora et al. (1992). Hence, when one wants to prove the nonapproximability of an optimization problem, it suffices to provide an L-reduction from a Max SNP-Complete problem to the optimization problem. We start with the Maximum Bounded Three-Dimensional Matching, which is an opti- mization version of 3DM and proven to be Max SNP-complete by Kann (1991). Maximum bounded three-dimensional matching (Max-3DM-3) Instance: Disjoint sets A = {a1 , . . . , an }, B = {b1 , . . . , bn }, C = {c1 , . . . , cn } and a family F = {T1 , . . . , Tm } of triples with |Ti ∩ A| = |Ti ∩ B| = |Ti ∩ C| = 1 for i = 1, . . . , m, where any element of A, B and C occurs in at most three triples in F. Goal: Find a matching F from F with largest cardinality. Then, we can prove the next theorem in almost similar fashion of the Corollary 5 by Kann (1991). Theorem 4. The problem IP1 is Max SNP-hard and thus does not has a PTAS, unless P = NP. Proof: We map an instance I of Max-3DM-3 to an instance G of our problem IP1 as described in the reduction of Theorem 2. Note that |F| ≤ 3 · OPT(I ). Then, ORDER CONSOLIDATION FOR BATCH PROCESSING 127 we have OPT(G) = 4 · OPT(I ) + 3(|F| − OPT(I )) ≤ OPT(I ) + 9 · OPT(I ) = 10 · OPT(I ). Hence, the first condition of L-reduction is satisfied. Next, we consider the second condition of L-reduction. Let y be a feasible solution of G. In correspondence with y, the solution t of I is obtained by selecting Ti for which yei1 = yei3 = yei5 = yei7 = 1. Thus, for the number of batches for y, z (y), and the number of matchings for t, z(t), we have z (y) ≤ 4z(t) + 3(|F| − z(t)). Then, we obtain that OPT(G) − z (y) ≥ 4 · OPT(I ) + 3(|F| − OPT(I )) − [4 · z(t) + 3(|F| − z(t))] = OPT(I ) − z(t). In other words, there exists a constant β such that |OPT(I ) − z(t)| ≤ β · |OPT(G) − z (y)|. It follows that Max-3DM-3 L-reduces to IP1. As suggested by Theorem 2, it is quite unlikely for us to be able to come up with an optimal algorithm for our problem. Moreover, by Theorem 4, the problem is nonapproximable in general in the sense that no PTAS exists unless P = N P. Hence, in the following sections, we will develop an optimal algorithm for the special cases of our problem when G is a tree. Before moving on to the next section, we introduce another concept which is quite impor- tant for the analysis of the proposed algorithm. Note that there may be several alternative optimal solutions for each problem instance G. Among these optimal solutions, the one using least amount of w(u) is called u-oriented optimal solution to G, which can formally be characterized by the following model, that we call IP2: Maximize w(u) − λyu − xe (u) (6) e∈E(u) Subject to yv + ye = OPT(G) (7) v∈V e∈E (1), (2), (3), (4), and (5) 4. Properties of u-oriented optimal solutions When a graph G = (V, E) is a tree it can be arranged about a node r ∈ V , called root as illustrated in (figure 2(a)). Then, there is a unique path from each node to r . A node is said to be in level if the distance that is measured by the number of edges on the path from the node to the root is . Hence, the root node is the only node in level 0. The depth of G is said to be d if the largest level about the root node is d, in which case G is said to have its depth d about the root node r . 128 HWANG AND CHANG Figure 2. (a) Levels in a tree and (b) Rooted and leaf trees for node u. We say that the level of a node is higher than the level of other node if its level number is smaller. For the sake of notational convenience, we assume that the pair of nodes in each edge, say, (u, v) is ordered so that the level of u is always one level higher than v. With this in mind, we let D(u) be the set of edges such that (u, v) ∈ E. For every node u except the root node, the node π(u) is defined to be the node such that (π(u), u) ∈ E. Let yv∗ , ye∗ , xe∗ : v ∈ V, e ∈ E be an optimal solution to G and ϕ ∗ (u) be the amount remained unused at each node u, after grouping all homogeneous and heterogeneous batches according to the optimum solution. Namely, ϕ ∗ (u) = w(u) − λyu∗ − xe∗ (u) − x(π ∗ (u),u) (u). e∈D(u) Then, clearly we have, ϕ ∗ (u) < λ. (8) With respect to an arbitrary node u of a tree G, we define two subtrees that we call u-rooted tree, Ḡ(u) = (V̄ (u), Ē(u)) and u-leaf tree, G(u) = (V (u), E(u)). The set V̄ (u) includes u and all the other nodes which have their paths to the root node pass through u and the set Ē(u) includes all the edges defined among the nodes in Ḡ(u). Then the set V (u) includes u and all the nodes that are not included in V̄ (u) and the set E(u) includes all the edges that are not included in Ē(u) (See figure 2(b)). The u-oriented optimal solution to Ḡ(u) plays an important role in designing an optimal algorithm. In fact, by the property of the u-oriented optimal solution to Ḡ(u), we can recursively decompose the tree G into simple subtrees so that we can construct the optimum solution incrementally. Suppose that ȳv , ȳe , x̄e : v ∈ V̄ (u), e ∈ Ē(u) is the u-oriented optimal solution of Ḡ(u) and let ϕ̄(u) be the amount remained unused from w(u), after grouping all homogeneous and heterogeneous batches according to the u-oriented optimal solution. Namely, we let, ϕ̄(u) = w(u) − λ ȳu − x̄e (u). e∈D(u) ORDER CONSOLIDATION FOR BATCH PROCESSING 129 Then, obviously we have, ϕ̄(u) < λ. (9) Then, we introduce four new nodes ū, u, µ̄ and µ which are used in replace of the node u to define graphs that are useful for our analysis. The weights of the ū and u are set based on the u-oriented optimal solution of Ḡ(u), whereas the weights for µ̄ and µ are set based on the optimal solution of G. Namely, we let w(u) = ϕ̄(u), w(ū) = w(u) − w(u), w(µ) = ϕ ∗ (u) + x(π(u),u) ∗ (u), w(µ̄) = w(u) − w(µ). With the nodes ū and u, we define G(ū) = (V (ū), E(ū)) and G(u) = (V (u), E(u)) by replacing the node u in Ḡ(u) and G(u), respectively. Likewise, with the nodes µ̄ and µ, we define G(µ̄) = (V (µ̄), E(µ̄)) and G(µ) = (V (µ), E(µ)) by replacing the node u in Ḡ(u) and G(u), respectively. Then it is clear that we can construct a feasible solution to G by combining the feasible solutions to G(ū) and G(u). Likewise, the same is true for the pair G(µ̄), and G(µ). Hence, we have OPT(G(ū)) + OPT(G(u)) ≤ OPT(G) and (10) OPT(G(µ̄)) + OPT (G(µ)) ≤ OPT(G). (11) Recall that the tree G(ū) is constructed based on the u-oriented optimal solution of Ḡ(u). Hence, we have OPT(G(ū)) = OPT(Ḡ(u)). (12) Also, note that G(µ̄) is the same as Ḡ(u) except for the node µ̄ with w(µ̄) ≤ w(u), which implies OPT(Ḡ(u)) ≥ OPT(G(µ̄)). Hence, from (12), we have OPT(G(ū)) ≥ OPT(G(µ̄)). (13) Now, we make feasible solutions to G(µ̄) and G(µ) from the optimal solution yv∗ , ye∗ , xe∗ : v ∈ G, e ∈ E of G. If we let, yµ̄ = yu∗ yv = yv∗ , for v ∈ V (µ̄), v = µ̄ y(µ̄,v) = ∗ y(u,v) for (µ̄, v) ∈ D(µ̄) ye = ∗ ye for e ∈ E(µ̄), e ∈ / D(µ̄) x(µ̄,v) (µ̄) = ∗ x(u,v) (u) and x(µ̄,v) (v) = x(u,v) ∗ (v), for (µ̄, v) ∈ D(µ̄), xe = ∗ xe , for e ∈ / D(µ̄) but e ∈ E(µ̄), 130 HWANG AND CHANG yv , ye , xe : v ∈ V (µ̄), e ∈ E(µ̄) is a feasible solution to G(µ̄). Then, by construction, we see that yv∗ + ye∗ = yv + ye . (14) v∈V̄ (u) e∈ Ē(u) v∈V (µ̄) e∈E(µ̄) The feasible solution to G(µ) is constructed similarly as below. If u is happened to be the root node, we know that V (µ) = {µ} and E(µ) = ∅. Then, we simply set yµ = 0 which is the only variable to be set. However, if u is not the root node, we let π (µ) = π (u) = π and set yµ = 0 yv = yv∗ , for v ∈ V (µ), v = µ ∗ y(π,µ) = y(π,u) ye = ye∗ , for e ∈ E(µ), e = (π, µ) ∗ ∗ x(π,µ) (µ) = x(π,u) (u) and x(π,µ) (π ) = x(π,u) (π ), for (π, µ) xe = xe∗ , for e = (π, µ) but e ∈ E(µ), yv , ye , xe : v ∈ V (µ), e ∈ E(µ) is a feasible solution to G(µ). Then, by construction, OPT(G) = yv∗ + ye∗ v∈V e∈E = yv + ye + yv + ye v∈V (µ̄) e∈E(µ̄) v∈V (µ) e∈E(µ) ≤ OPT(G(µ̄)) + OPT(G(µ)) (15) must hold. Hence, this together with (11) implies that OPT(G(µ̄)) + OPT(G(µ)) = OPT(G). (16) We now show that yv , ye , xe and yv , ye , xe constructed above are, in fact, optimum solutions to G(µ̄) and G(µ), respectively. Lemma 5. yv , ye , xe : v ∈ V (µ̄), e ∈ E(µ̄) is an optimum solution to G(µ̄), or equivalently, OPT(G(µ̄)) = yv + ye . v∈V (µ̄) e∈E(µ̄) ORDER CONSOLIDATION FOR BATCH PROCESSING 131 Proof: Suppose that the lemma is false and thus OPT(G(µ̄)) > v∈V (µ̄) yv + e∈E(µ̄) ye . Then, from (15) and (16), we have OPT(G(µ)) < yv + ye , v∈V (µ) e∈E(µ) which contradicts the fact that yv , ye , xe : v ∈ V (µ), e ∈ E(µ) is a feasible solution to G(µ). By (16), this lemma implies that yv , ye , xe : v ∈ V (µ), e ∈ E(µ) is an optimum solution to G(µ). We further note the following lemma. Lemma 6. If OPT(G(ū)) = OPT(G(µ̄)), w(u) = ϕ̄(u) ≥ ϕ ∗ (u) + x(π ∗ (u),u) (u) = w(µ). Proof: Note that the solution yv , ye , xe : v ∈ V̄ (u), e ∈ Ē(u) is not only an optimum solution to G(µ̄) by Lemma 5 but also a feasible solution to Ḡ(u). However, if OPT(G(ū)) = OPT(G(µ̄)), yv , ye , xe : v ∈ V̄ (u), e ∈ Ē(u) is also an optimum solution to Ḡ(u), since OPT(G(ū)) = OPT(Ḡ(u)) by (12). Hence, the lemma follows from the fact that ϕ̄(u) is set according to the u-oriented optimal solution to Ḡ(u). The next lemma lays a basis for constructing a divide-and-concur approach for finding an optimum solution. Lemma 7. Given a tree G = (V ,E), for any u ∈ V , except the root node of G, OPT(G(ū)) + OPT(G(u)) = OPT(G). Proof: Based on (13), we develop the proof by considering two cases. Case 1. OPT(G(ū)) = OPT(G(µ̄)). In this case, by Lemma 6, we have, w(u) = ϕ̄(u) ≥ ϕ ∗ (u) + x(π ∗ (u),u) (u) = w(µ). This means that OPT(G(u)) ≥ OPT(G(µ)). Hence, by (16), OPT(G(ū)) + OPT(G(u)) ≥ OPT(G(µ̄)) + OPT(G(µ)) = OPT(G). Then, from this and (10), the lemma follows. 132 HWANG AND CHANG Case 2. OPT(G(ū)) > OPT(G(µ̄)). We first note that OPT(G(ū)) > OPT(G(µ̄)) implies, w(ū) > w(µ̄)and hence, w(u) < w(µ) and OPT(G(u)) ≤ OPT(G(µ)). But, in fact, a strict inequality OPT(G(u)) < OPT(G(µ)) must hold, since if OPT(G(u)) = OPT(G(µ)), OPT(G(ū)) + OPT(G(u)) > OPT(G(µ̄)) + OPT(G(µ)) = OPT(G), which is a clear contradiction to (10). When u is not the root node, the π(u) = π (u) = π (µ) is well defined and recall that w(µ) = ϕ ∗ (u) + x(π(u),u) ∗ (u). ∗ If w(u) ≥ x(π(u),u) (u), yv , ye , xe : v ∈ V (µ), e ∈ E(µ) constructed from yv∗ , ye∗ , xe∗ : v ∈ V, e ∈ E is also feasible to G(u) and, hence, OPT(G(u)) ≥ OPT(G(µ)) which leads to a contradiction to the inequality OPT(G(u)) < OPT(G(µ)). Hence, ∗ w(u) < x(π(u),u) (u), Then, we construct a feasible solution to G(u), say, yv , ye , xe by copying the solution yv , ye , xe except setting, y(π (µ),µ) = x(π (µ),µ) (µ) = x(π (µ),µ) (π (µ)) = 0. Then the solution yv , ye , xe has exactly one less batch than OPT(G(µ)). Hence, OPT(G(u)) ≥ OPT(G(µ)) − 1. Since, OPT(G(ū)) > OPT(G(µ̄)) implies OPT(G(ū)) ≥ OPT(G(µ̄)) + 1, OPT(G(ū)) + OPT(G(u)) ≥ OPT(G(µ̄)) + OPT(G(µ)) = OPT(G). Thus, from this together with (10), the lemma follows. When the node u is the root of the tree G, we do not decompose further. Instead, we execute the procedure discussed in the following section. ORDER CONSOLIDATION FOR BATCH PROCESSING 133 5. A procedure for finding u-oriented solutions for stars In this section, we consider the way to get a u-oriented optimal solution for simple trees called stars. A tree G = (V, E) with a root node u is called a star if its depth is at most one and w(v) < λ for every v = u. If G = (V, E) is a star with a root node u, clearly D(u) = E and we can make at most one heterogeneous batch on each edge, since each w(v) < λ. Now, we consider the problem IP2 for the u-oriented optimal solution to the star G. Note that the constraint (7) is reduced to yu + ye = OPT(G). (17) e∈D(u) We note that the objective function of IP2 in (6) can be rewritten as w(u) − λyu − xe (u) e:u∈e = w(u) − λyu − xe (u) e∈D(u) = w(u) − λOPT(G) + λ ye − xe (u) by (17) e∈D(u) e∈D(u) = w(u) − λOPT(G) + (λye − xe (u)) e∈D(u) = w(u) − λOPT(G) + xe (v). e∈D(u) Hence, (6) is equivalent to, Maximize xe (v). (18) e∈D(u) For notational ease, let V = {u, v1 , . . . , vk } and assume, without loss of generality, that w(v1 ) ≥ · · · ≥ w(vk ) > 0 holds. k Then, first consider the case when w(u) + i=1 w(vi ) ≥ λk. In this case, we construct a solution ȳv , ȳe , x̄e : v ∈ V, e ∈ D(u) by setting, ȳe = 1, x̄e (vi ) = w(vi ), x̄e (u) = λ − w(vi ), (19) for each e = (u, vi ), i = 1, . . . , k, and w(u) − e∈D(u) x̄e (u) ȳu = . (20) λ 134 HWANG AND CHANG Then, ȳv , ȳe , x̄e : v ∈ V, e ∈ D(u) is a u-oriented optimum solution since, k w(u) + w(vi ) w(u) − e∈D(u) x̄e (u) + kλ OPT(G) ≤ i=1 = λ λ w(u) − e∈D(u) x̄e (u) = + k = ȳu + ȳe , λ e∈D(u) and e∈D(u) x̄e (v) = (u,vi )∈D(u) w(vi ). k Next, we consider the case when w(u) + i=1 w(vi ) < λk. In this case, we let j be the index satisfying, j λ( j − 1) ≤ w(u) + w(vi ) < λj. (21) i=1 Then, we construct a solution ȳv , ȳe , x̄e : v ∈ V, e ∈ D(u) by setting, ȳe = 1, x̄e (vi ) = w(vi ), x̄e (u) = λ − w(vi ), (22) for each e = (u, vi ), i = 1, . . . , j − 1, and ȳu = 0. (23) The next lemma shows that, ȳv , ȳe , x̄e : v ∈ V, e ∈ D(u) is a u-oriented optimal solution. Lemma 8. For a star G = (V, E), with root node u, V = {u, v1 , . . . , vk } and w(v1 ) ≥ k . . . ≥ w(vk ), if w(u) + i=1 w(vi ) < λk, the solution ȳv , ȳe , x̄e defined in (22) and (23) is a u-oriented optimal solution. Proof: We first establish the fact that ȳ is an optimal solution and then show that it is also u-oriented solution. To this end, we assume that ȳv , ȳe , x̄e is not optimal and there exists another feasible solution ŷ = ŷu , ŷe , x̂e : u ∈ V, e ∈ D(u) with ŷu + ŷe ≥ j > ȳe = j − 1. (24) e∈D(u) e∈D(u) Let r = e∈D(u) ŷe , and ŷei = 1, ei ∈ D(u), for i = 1, . . . , r . Then, (24) can be written as ŷu + r ≥ j. (25) For each ei ∈ D(u), i = 1, . . . , r , we define node vei such that ei = (u, vei ). Then, we assume, without loss of generality, that the edges are arranged in the order satisfying ORDER CONSOLIDATION FOR BATCH PROCESSING 135 x̂e1 (ve1 ) ≥ · · · ≥ x̂er (ver ). Recalling that the nodes are also arranged so that w(v1 ) ≥ . . . ≥ w(vk ), we must have w(vi ) ≥ x̂ei (vei ) for = 1, . . . , k. (26) i=1 i=1 r r clearly w(u) ≥λrŷu + i=1 x̂ei (u) must hold. Hence, with this and the fact that But i=1 x̂ ei (u) = λr − i=1 x̂ ei (vei ) together with (25), we have, r w(u) + x̂ei (vei ) ≥ λ( ŷu + r ) ≥ λj. i=1 j j This implies that ri=1 x̂ei (vei ) > i=1 w(vi ), since w(u) + i=1 w(vi ) < λj by (21). Hence, we can see that r > j due to (26), which means x̂e j (u) > 0. Let’s further look at the term x̂e j (u) and note that, by (21), we have j−1 w(u) + w(vi ) − λ( j − 1) < λ − w(v j ). (27) i=1 Hence, we have j−1 x̂e j (u) ≤ w(u) − λ ŷu − x̂ei (u) i=1 j−1 = w(u) − λ ŷu − λ − x̂ei vei i=1 j−1 = w(u) − λ ŷu − λ( j − 1) + x̂ei vei i=1 j−1 ≤ w(u) − λ( j − 1) + x̂ei vei i=1 j−1 ≤ w(u) − λ( j − 1) + w(vi ) by (26) i=1 < λ − w(v j ) by (27). Thus, x̂e j (u) < λ − w(v j ). Also, since x̂e j (ve j ) ≤ w(v j ), we have x̂e j (u) + x̂e j (ve j ) < λ. This is a contradiction. Hence, ȳv , ȳe , x̄e must be an optimal solution. To show that ȳv , ȳe , x̄e is a u-oriented optimal solution, we suppose that not ȳv , ȳe , x̄e but ŷu , ŷe , x̂e is the u-oriented optimal solution and let ŷei = 1 for i = 1, . . . , r . Recalling 136 HWANG AND CHANG Figure 3. The procedure StarGroup. the objevtive function of (18), we get r j−1 x̂ei (vei ) = x̂e (v) > x̄e (v) = w(vi ), i=1 e∈D(u) e∈D(u) i=1 which implies that r > j − 1, since each x̂ei (vei ) ≤ w(vi ) for i = 1, . . . , j − 1. This is a contradiction to the optimality of ȳv , ȳe , x̄e . Hence, the lemma follows. By incorporating the construction scheme suggested in (19), (20), (22) and (23), we can develop an optimal algorithm, that we call StarGroup, for finding a u-oriented optimum solutions for stars as shown in figure 3. It is worthwhile, at this point, to note that if the star is given as a single node u, the algorithm would skip the while-loop, construct homogeneous batches if possible and then update w(u) to be strictly less than λ. 6. An optimal algorithm for orders on trees In Lemma 7, we have shown that any optimal solution for a tree G can be obtained by decomposing it into two subtrees, G(ū) and G(u), and finding their optimal solutions. Note that the subtrees are constructed based on the u-oriented optimal solution to Ḡ(u). We also have shown that the u-oriented optimal solution for a star can be obtained by the procedure StarGroup in the previous section. The proposed optimum algorithm that we call TreeGroup is presented in figure 4. The algorithm proceeds as explained below. When is the depth of G, let L(i) be the set of nodes in level i for i = 0, . . . , . Then every node in the set L() is a leaf node, i.e. a node, u ∈ V such that D(u) is empty. With ORDER CONSOLIDATION FOR BATCH PROCESSING 137 Figure 4. Algorithm TreeGroup. respect to a leaf node u, the u-rooted tree Ḡ(u), is obviously a star with zero depth. If the procedure StarGroup is executed on the u-rooted tree Ḡ(u) of a leaf node u, the algorithm should yield w(u) λ homogeneous batches and update ϕ̄(u) = w(u) − λ w(u) λ . Having executed the procedure StarGroup on each and every node in L(), we can easily verify that the u-rooted tree Ḡ(u) of every node u in the set L( − 1) is again a star. Hence, we deploy the procedure StarGroup on Ḡ(u) for every node u in the set L( − 1). Continuing in this manner, we construct an optimum solution. Note that the procedure StarGroup takes O(|D(u)| log |D(u)|) steps for each star Ḡ(u), due to the sorting of the nodes in the star in non-decreasing order of their weights. Hence, the overall time complexity of TreeGroup is O(|V | log |V |). Hence, we have the following theorem. Theorem 9. The algorithm TreeGroup generates an optimal solution to the problem I P1 when G is a tree and its computational complexity is bounded by O(|V | log |V |). 7. Conclusion We introduced a batch scheduling problem characterized by a graph G and show that it is not only NP-hard problem but also Max SNP-hard problem, for which no PTAS exists unless P = N P. Then, we develop an optimal algorithm for a special class of the problem when the graph G is a tree. Optimal algorithms for other cases when G is a special graph other than a tree are under active investigation. Acknowledgment This study was supported in part by research funds from Chosun University, 2004. References S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, “Proof verification and hardness of approximation problems,” in Proceedings of the 33rd IEEE Symposium on the Foundations of Computer Science, 1992, pp 14– 23. 138 HWANG AND CHANG S.Y. Chang, M.R. Chang, and Y.S. Hong, “A lot grouping algorithm for a continuous slab caster in an integrated steel mill,” Production Planning & Control, vol. 11, pp. 363–368, 2000. Y. Crama and A.G. Oerlemans, “A column generation approach to job grouping for flexible manufacturing systems,” European Journal of Operational Research, vol. 78, pp. 58–80, 1994. M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman: San Francisco, CA, 1979. V. Kann,“Maximum bounded 3-dimensional matching is MAX SNP-complete,” Information Processing Letters, vol. 38, pp. 27–35, 1991. T. Knuutila and O. Nevalainen, “A reduction technique for weighted grouping problems,” European Journal of Operational Research, vol. 140, pp. 590–605, 2002. C.-Y. Lee, R. Uzsoy, and L.A. Martin-Vega, “Efficient algorithms for scheduling semiconductor burn-in opera- tions,” Operations Research, vol. 40, pp. 764–775, 1992. √ S. Micali and V.V. Vazirani, “An O( |V | · |E|) algorithm for finding maximum matching in general graphs,” in Proc. Twenty-first Annual Symposium on the Foundations of Computer Science, 1980, pp. 17–27. C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization, Dover Publications: Mineola, NY, 1988. C.H. Papadimitriou and M. Yannakakis,“Optimization, approximation and complexity classes,” Journal of Com- puter and System Sciences, vol. 43, pp. 425–440, 1991. C.N. Potts and M.Y. Kovalyov, “Scheduling with batching: A review,” European Journal of Operational Research, vol. 120, pp. 228–249, 2000. L. Tang, J. Liu, A. Ring, and Z. Yang, “A review of planning and scheduling systems and methods for integrated steel production,” European Journal of Operational Research, vol. 133, pp. 1–20, 2001. R. Uzsoy, “Scheduling batch processing machines with incompatible job families,” Int. J. Prod. Res., vol. 33, pp. 2685–2708, 1995.