Microsoft Word - 48 MT_ZAHEDI-INTEGER RELAXATION ON BINARY QUADRATIC PROGRAMMING-Ok.doc Integer Relaxation on… (Zahedi) 1083 INTEGER RELAXATION ON BINARY QUADRATIC PROGRAMMING FOR BATCHING AND SEQUENCING IN SINGLE FORMULATION TO MINIMIZE TOTAL ACTUAL FLOW TIMES CRITERIA Zahedi Mathematics & Statistics Department, School of Computer Science, Binus University Jl. K.H. Syahdan No. 9, Palmerah, Jakarta Barat 11480 zahedizahedi@binus.ac.id ABSTRACT This paper examines batch scheduling problem that has batching and sequencing in single formulation for multiple-item case. The first step is to develop a model for single item single resource discussed in Zahedi (2008). The model determined batch sizes and their schedule simultaneously in single item case. This paper develops the model and algorithm for multiple-item case. The model functions to minimize total actual flow times. An algorithm for the model is developed using a relaxation of the binary constraints. The binary values for the decision variables are obtained from steps provided in algorithm. A numerical experience showing characteristics of this problem is presented. Keywords: actual flow time, batching, sequencing, simultaneous formulation, optimal solution ABSTRAK Makalah ini membahas masalah penjadwalan batch dengan batching dan sequencing dalam formulasi tunggal untuk beberapa item kasus. Langkah pertama adalah mengembangkan model sumber daya tunggal satu item yang dibahas dalam Zahedi (2008). Model ini ditentukan ukuran batch dan jadwal mereka secara bersamaan dalam kasus item tunggal. Makalah ini mengembangkan model dan algoritma untuk multiple-item kasus. Model ini berfungsi meminimalkan total waktu aliran yang sebenarnya. Sebuah algoritma untuk model ini dikembangkan menggunakan relaksasi kendala biner. Nilai biner untuk variabel keputusan diperoleh dari langkah yang diberikan dalam algoritma. Sebuah pengalaman numerik disajikan yang menunjukkan karakteristik dari masalah ini. Kata kunci: waktu aliran sebenarnya, batching, sequencing, formulasi simultan, solusi optimal 1084 ComTech Vol.2 No. 2 Desember 2011: 1083-1088 INTRODUCTION This article develops backward scheduling problem and minimizes total actual flow times criteria from Halim et al (1998). He proposed a shop time criterion called actual flow time defined as the time that the part spends in the shop from its due date. The parts to be processed arrive at the production line at the right time in the right quantities, and that completed parts are delivered at their due dates. This means that the actual flow time can be implemented for production systems under Jus- in-time (JIT) environment. In solving the problem Halim et al (1998), Lagrangian relaxation is used, in the case determining number of parts in batches and scheduling of batches in two ways. Zahedi (2004, 2007, and 2008) did research for backward scheduling on job and block level in the same criterion, i.e., minimize total actual flow times. Zahedi (2008) developed model and algorithm to solve binary quadratic programming model from batch scheduling that determines number of parts in batches and scheduling in single formulation, in single item single resource case. This article examines batch scheduling problem that has batching and sequencing in single formulation for multiple-item case. Problem Formulation Let K different items be processed in a single stage operation. Each item requires one machine or resource to complete the operation. The items, with nk standing for the numbers of parts of item k (k = 1, 2,…, K) respectively, are demanded at common due date d. The processing time and setup time for an item may be diffrent from one to another item. For each item, the processing time, the setup time, and the quantity demanded are assumed to be known and deterministic. The parts to process are not required to be available for processing at time zero but may arrive at the production line at the right times in the right quantities. The completed parts are delivered at their due date. There are two issues considered here, i.e., creating the model formulation and creating an algorithm to solve the formulation. Let’s define the following constants and variables: d = the common due date i, j = the indices for batch numbers. i, j = 1, 2,…, Nk k, m = the indices for ítems. k, m = 1, 2,…, K Nk = the number of batches for item k n = the total number of parts nk = the number of parts of item k demanded tk = the processing time for item k sk = the setup time for item k/ B(ki) = the starting time of processing batch i of item k Q(ki) = the number of parts of item k in batch i Xki = 1, if batch i of item k processed on resource is not vacuous, 0, otherwise Ykmij = 1, if batch i of item k precedes batch j of item m, = 0, otherwise Fa = total actual flow times all of parts Fia = total actual flow times on ith step in algorithm. The formulation of multiple ítems single resource (MISR) to minimize the total actual flow times can be expressed as follows. Problem MISR Minimize Fa = ∑Kk=1∑Nki=1(∑km=1 ∑ij=1(sm Xmj+ tm Q(mj) )- sk) Q(ki) Integer Relaxation on… (Zahedi) 1085 + ∑(k,i | k>i) ( ∑k-1m=1 ∑Nmj=/+1 (smXmj + tm Q(mj))) Q(ki) (1) subject to ∑Kk=1∑ Nk i=1 Q(ki) = n (2) ∑Nki=1 Q(ki) = nk , ∀ k (3) Q(ki) ≤ Xki nk , ∀ i,k (4) B(ki) + ∑km=1 ∑ij=1(sm Xmj+ tm Q(mj))- sk + ∑(k,i | k>i) ( ∑k-1m=1 ∑Nmj=i+1 (smXmj + tm Q(mj))) = d , ∀ k,i (5 B(KNK(opt)) ≥ 0 (6) B(ki) + tk Q(ki) ≤ B(mj) + m ( Ykmij ) , ∀ i,j,k,m, except fo i=j=k=m (7) Ykmij + Ymkji = 1 , ∀ i,j,k,m, except for i=j=k=m (8) Xki , Ykmij = 0, 1 , ∀ i,j,k,m, except for i=j=k=m (9) N, Nk ≥ 0 and integer , ∀ k (10) Q(ki) ≥ 0 , ∀ k,i (11) Function (1) is the objective of the model i.e. minimize total actual flow times all of the parts. Constraints (2) and (3) accomplish material balance in the shop and the items/respectively. Constraint (4) means that if the size of batch i of item k is positive, the setup time for item k in constraint (5) will be incurred. Constraint (5) ensures that all batches on schedule will be finished at the due date. Constraint (6) shows that the processing of batch K must be started at or after time zero. Constraint (7) ensures that if batch i of item k is to precede batch j of item m then starting time of batch j of item m must come later after the completion time of batch i of item k, where constant M must sufficiently be large enough. Constraint (8) shows that given two batches, one must precede the other. Xki and Ykmij are binary variables as shown by constraint (9). Constraint (10) shows values of total number of parts and number of all items must be integer. Number of parts in every batches must be non negative. METHOD Problem MISR can be viewed as a mix quadratic programming model. There are a lot of softwares such as LINGO that can be used to solve the problem. However, in order to solve Problem MISR using LINGO, it is required to create a relaxation for binary constraint, i.e., Constraint (9). It can developed some steps referring to using LINGO for the modified Problem MISR in a proposed algorithm to solve the original problem MISR. The proposed algorithm is then provided with steps to obtain integer values for the decision variables that must be integer. The remaining steps in the algorithm are based on the previous algorithm that have developed in Zahedi (2008) to solve the single item single resource (SISR) batch scheduling problem. The following algorithm is proposed to solve Problem MISR. Algorithm Step 1: Set all parts of each item as one batch. This leads to having K batches. Step2: Sequence the K batches in order of non-decreasing the ratio of (tknk + sk)/ nk , ∀ k, or (t1n1 + s1)/ Q1 ≤ (t2n2 + s2)/ n2 ≤ . . . ≤ (tKnK + sK)/ nK Step 3: Generate a backward schedule of the batches on resource, based on the resulting sequence, considering the feasibility of the schedule. Determine Tmin constituting the time interval from the starting time, BK, until the common due date. 1086 ComTech Vol.2 No. 2 Desember 2011: 1083-1088 Step 4: Problem MISR is considered feasible if and only if Tmin ≤ d, and go to step 5. Otherwise, the problem is not feasible, and stop. Step 5: Compute Nk(maks) for each item using the following equation Nk(maks) = ⎣1/2 + √ 1/4 + 2nktk /sk ⎦ where ⎣N⎦ denotes the maximum integer less than or equal to N. Step 6: Substitute all values of K and Nk where Nk = Nk(maks), nk, tk, sk and d to modify Problem MISR. Step 7: Set X11= X21= ... =XK1= 1, and set Xki= 0 otherwise. Also, set Ykmij = 1 if k < m or k=m and i < j, ∀ i,j,k,m, and set Ykmij = 0, otherwise. Compute F1a, constituting the initial total actual flow time, for this setting. Step 8: Set k = K. Step 9: Set i = 2, then set Xkj = 1, for j = 1, ..., i. Step 10: Solve the problem. Step 11: Observe whether B(ki) ≥ 0 ?, If B(ki) ≥ 0, write Fia. Observe whether Fia < Fi-1a . If Fia < Fi-1a , set i = i + 1 and go to step 9. Otherwise, set i-1 = Nk(opt) and go to step 12. Step 12: Set k = K-1. If k > 0, go to step 8. If k = 0, set Fia as the optimal solution and recompute all decision variables. RESULTS AND DISCUSSION To clarify how the proposed algorithm works, the following example is given. Consider problem with parts of 3 items. The quantities demanded of the respective items at the common due date, d = 200, are 40, 100, and 80. The processing times are 0.6, 0.8 and 0.5 respectively. The setup times for respective items are 2.4, 2.0, and 4.0. The computational steps to solve the problem are the followings. Step 1 ~ Step 4: These steps give the resulting sequences: Item 3, Item 1, and Item 2. The time interval from the starting time, B3, of batch processed first until the common due date, Tmin = 150.4 ≤ d=200. Step 5: The numbers of batches for items 1, 2, and 3 respectively are 5, 5, and 9. Step 6 ~ Step 7 subsitute all values of the parameters to the formulation of modified Problem MISR and set the condition as shown in step 7 of the proposed algorithm result F1a = 18592.36. Step 8 ~ Step 12: These steps give the optimal solution shown in Table 1 with Fa = 17966.44. Table 1. The Optimal Solution of Example Position Qki Bki Item 1 44 178 3 2 36 156 3 3 40 128 1 Integer Relaxation on… (Zahedi) 1087 4 21.11 108.71 2 5 18.61 91.82 2 6 16.11 76.93 2 7 13.61 64.04 2 8 11.11 53.16 2 9 8.61 44.27 2 10 6.11 37.38 2 11 3.61 32.49 2 12 1.11 29.60 2 On other side, to observe model behavior and the solution, some groups of cases are created as available in Table 2. Table 2 Optimal Solution Some Groups of Cases Group No Data Fa N(t) BNopt Item-1 n t s Item-2 n t s Item-3 n t s I 1 2 3 4 5 40 0.6 2.4 40 0.6 2.4 40 0.6 2.4 40 0.6 2.4 40 0.6 2.4 100 0.8 2.0 80 0.8 2.0 60 0.8 2.0 40 0.8 2.0 20 0.8 2.0 80 0.5 4.0 80 0.5 4.0 80 0.5 4.0 80 0.5 4.0 80 0.5 4.0 17966.44 12 14716.60 12 11781.31 11 9212.50 10 7021.10 8 29.6 45.2 63.2 81.2 101.2 II 6 7 1 40 0.6 2.4 40 0.6 2.4 40 0.6 2.4 100 0.8 2.0 100 0.8 2.0 100 0.8 2.0 80 0.5 2.0 80 0.5 3.0 80 0.5 4.0 17332.44 12 17649.94 12 17966.44 12 33.6 31.6 29.6 III 8 9 1 40 0.6 2.4 40 0.6 2.4 40 0.6 2.4 100 0.4 2.0 100 0.6 2.0 100 0.8 2.0 80 0.5 4.0 80 0.5 4.0 80 0.5 4.0 13568.67 9 17150.33 8 17966.44 12 74.8 56.8 29.6 CONCLUSION The foregoing has presented a model and algorithm to solve binary quadratic programming model from batch scheduling that determines number of parts in batches and scheduling in single formulation for multiple-item cases. Problem MISR appears to be an NP-hard problem, and can be viewed as a mixed quadratic programming for which the proposed algorithm takes advantages of the so-called LINGO software. However, a relaxation of binary constraints is needed to make the formulation of Problem MISR solvable using the LINGO software. In view of the Results and Discussion, the conclusions are the proposed algorithm can solve problem MISR effectively. The last item scheduled (first in process) has more batches since batching of the last item can increase total actual flow time. The resulting solution are optimal, since LINGO gives the optimal solution and the steps provided in proposed algorithm for obtaining the best binary value search from all alternative binary values. The research underway is to extend problem MISR to cover the issue in actual problems such as multiple due dates and multiple process stages. REFERENCES Halim, A. H., Toha, I. S., Zahedi. (1998). Simultaneous Resource Scheduling to Minimize Total Actual Flow Times. Proceeding of Pacific Congress of Manufacturing and Management. Victoria, Australia. 1088 ComTech Vol.2 No. 2 Desember 2011: 1083-1088 Zahedi. (2007). The Solution for Binary Quadratic Programming to Multiple Resources Scheduling Problem. Jurnal MatStat, 5 (1), September 2007. Jakarta: Binus University. Zahedi. (2008). Integer Relaxation for Binary Quadratic Model in Batching and Scheduling with Minimize Total Actual Flow Times. Proceeding of National Conference in Mathematics, November 2008. Palembang, Indonesia. Zahedi. (2008). Optimal Block Measurement Optimization to Minimize the Total Actual Flow Time. Jurnal MatStat, 6 (1), January 2008. Jakarta: Binus University.