### Paper Menu >>

### Journal Menu >>

J. Software Engineering & Applications, 2010, 3: 91-97 doi:10.4236/jsea.2010.31011 Published Online January 2010 (http://www.SciRP.org/journal/jsea) Copyright © 2010 SciRes JSEA Makespan Algorithms and Heuristic for Internet-Based Collaborative Manufacturing Process Using Bottleneck Approach Salleh Ahmad BAREDUAN, Sulaiman HASAN Faculty of Mechanical and Manufacturing Engineering, University Tun Hussein Onn Malaysia, Batu Pahat, Johor, Malaysia. Email: saleh@uthm.edu.my Received August 20th, 2009; revised September 15th, 2009; accepted November 12th, 2009. ABSTRACT This paper presents makespan algorithms and scheduling heuristic for an Internet-based collaborative design and manufacturing process using bottleneck approach. The collaborative manufacturing process resembles a permutation re-entrant flow shop environment with four machines executing the process routing of M1,M2,M3,M4,M3,M4 in which the combination of the last three processes of M4,M3,M4 has high tendency of exhibiting dominant machine character- istic. It was shown that using bottleneck-based analysis, effective makespan algorithms and constructive heuristic can be developed to solve for near-optimal scheduling sequence. At strong machine dominance level and medium to large job numbers, this heuristic shows better makespan performance compared to the NEH. Keywords: Heuristic, Re-Entrant Flow Shop, Bottleneck, Scheduling, Dominant Machine 1. Introduction Flow shop manufacturing is a very common production system in many manufacturing facilities, assembly lines and industrial processes. In this environment, the opera- tions of all jobs must follow the same order following the same route along the machines assumed to be set up in series [1]. It is known that finding an optimal solution for a flow shop scheduling problem is a difficult task [2] and even a basic problem involving three machines is already NP-hard [1]. Therefore, many researchers have concen- trated their efforts on finding near optimal solutions within acceptable computation time using heuristics. Most heuristics are developed by the researchers after gaining familiarity and in-depth understanding of the system’s characteristic or behaviour. One of the important subclass of flow shop which is quite prominent in industries is re-entrant flow shop. The special feature of a re-entrant flow shop compared to ordinary flow shop is that the job routing may return one or more times to any facility. A group of researchers de- veloped a cyclic scheduling method that takes advantage of the flow character of the re-entrant process [3]. This work illustrated a re-entrant flow shop model of a semi- conductor wafer manufacturing process and developed a heuristic algorithm to minimize average throughput time using cyclic scheduling method at specified production rate. The branch and bound technique was utilized in [4,5] while the decomposition technique in solving maximum lateness problem for re-entrant flow shop with sequence dependent setup times was suggested in [6]. Mixed inte- ger heuristic algorithms was later on elaborated in [7] for minimizing the makespan of a permutation flow shop scheduling problem. Significant works on re-entrant hy- brid flow shop can be found in [8] while hybrid algo- rithms which combine a few well known techniques was reported in [9–11]. In scheduling literature, there are a number of studies conducted using the bottleneck approach in solving shop scheduling problem. This includes shifting bottleneck heuristic [12] and bottleneck minimal idleness heuristic [13,14].Other related studies are the dispatching rule heuristic for proportionate flow shop [15] and flow shops with deteriorating jobs on no-idle dominant machine [16]. However, not much progress is reported on bottleneck approach in solving re-entrant flow shop problem. Among the few researches are [6] who developed a spe- cific version of shifting bottleneck heuristic to solve the re-entrant flow shop sequence problem. In this paper we explored and investigated an Inter- net-based collaborative design and manufacturing proc- ess scheduling which resembles a four machine permuta- Makespan Algorithms and Heuristic for Internet-Based Collaborative Manufacturing Process Using Bottleneck Approach 92 tion re-entrant flow shop. The study develops a makes- pan minimization heuristic using bottleneck approach known as Bottleneck Adjacent Matching 2 (BAM2) heu- ristic. This procedure is specifically intended for the cy- ber manufacturing centre (CMC) at Universiti Tun Hus- sein Onn Malaysia (UTHM) that allows the university to share the sophisticated and advanced machinery and software available at the university with the small and medium enterprises (SMEs) using Internet technology [17]. The remainder of the paper is organised as follows: In the next section, the CMC operations are described and followed by discussions on alternative makespan computation using bottleneck approach. The later sec- tions explain the proposed heuristic. The two final sec- tions evaluate the heuristic performance, summarize the findings and present some future heuristic development. 2. Cyber Manufacturing Centre UTHM has recently developed a web-based system that allows the university to share the sophisticated and ad- vanced machinery and software available at the univer- sity with the SMEs using Internet technology [17]. The heart of the system is the cyber manufacturing centre (CMC) which consists of an advanced computer numeri- cal control (CNC) machining centre fully equipped with cyber manufacturing system software that includes com- puter aided design and computer aided manufacturing (CAD/CAM) system, scheduling system, tool manage- ment system and machine monitoring system. The Petri net (PN) model that describes a typical de- sign and manufacturing activities at the CMC is shown in Figure 1. The places denoted by P22, P23, P24 and P25 in Figure 1 are the resources utilized at the CMC. These resources are the CAD system, CAM system, CNC post- processor and CNC machine centre respectively. At the CMC, all jobs must go through all processes following the sequence represented in the PN model. This flow pattern is very much similar with flow shop manufactur- ing [1]. However, it can be noticed from the PN model that there are a few processes that share common re- sources. The process of generating CNC program for prototyping (T3) and the process of generating CNC program for customer (T5) are executed on the same CNC postprocessor (P24). Similarly, the processes of prototype machining (T4) and parts machining (T6) are executed on the same CNC machine centre. Thus, this process flow is considered as a re-entrant flow shop as described in [3]. It can also be noticed that both shared resources (P24 and P25) must completely finish the processing of a particular job at T5 and T6 before start- ing to process any new job at T3 and T4. In other words, this problem can be also identified as four machine per- mutation re-entrant flow shop with the processing route of M1,M2,M3,M4,M3,M4. One important characteristic observed at the CMC is that the processing time at the CNC machine centre or the M4 is always the longest. This means the M4 always shows dominant machine characteristic. Due to the re-entrant nature of the CMC process, the M4 dominant characteristic is identified as M4 + M3 + M4 or also recognized as P4 + P5 + P6 espe- cially when the processing time is used in the discussion. It was also found out from the CMC operations data that the number of jobs at the CMC is ranged from minimum of 6 to maximum of 20. 3. Alternative Makespan Computation Using Bottleneck Approach Referring to Figure 1, the permutation scheduling algo- rithm for the CMC can be written as the followings and is identified as Algorithm 1 [18]: Algorithm 1 Let i = Transition number, process number or work cen- tre number (i=1,2,3,…6) j = Job number (j=1,2,3,…n) Start (i,j) = start time of the jth job at ith work centre. Stop (i,j) = stop time of the jth job at ith work centre. P(i,j) = processing time of the jth job at ith work centre. For i=1,2,5,6 and j=1,2,3,…n Start (i,j) = Max [Stop (i,j-1), Stop (i-1,j)] except Start (1,1) = initial starting time Figure 1. Petri net model of CMC activities P1P2 P3 P4 P5 P6 P7 P22 P23 P24 P25 T1 15 T2 3 T3 2 T4 8 T5 2 T6 16 CAD design, virtual CAM simulation Generate CNC p rogra m for prototype Generate CNC Parts machining Prototype machining p rogra m for customer meeting, design review CAD system (M1) CNC postprocessor (M3) CAM system (M2) CNC machine (M4) Copyright © 2010 SciRes JSEA Makespan Algorithms and Heuristic for Internet-Based Collaborative Manufacturing Process Using Bottleneck Approach 93 Resource Time M1 P11 P12 P13 P14 M2 P21 VP21 P22 VP22 P23 VP23 P24 M3 P 31 P 51 P32 P52 P33 P53 P34 P54 M4 P 41 P 61 P42 P62 P43 P63 P44 P64 Figure 2. Example schedule focusing on M4 Stop (i,j) = Start (i,j) + P (i,j) For i =3,4 and j=1,2,3,…n Start (i,j) = Max [Stop (i,j-1), Stop (i-1,j), Stop (i+2,j-1)] Stop (i,j) = Start (i,j) + P(i,j) The makespan for the CMC is computed using Algo- rithm 1 by determining the completion time of the last task belongs to the last job or Stop (6,n). The example schedule for the CMC can also be observed by focusing on the M4 as the dominant machine and this is shown in Figure 2. The makespan for the example in Figure 2 is computed as the following: Cmax=+ 1) 36 114 (,1)(, ) n iji PiPi j 2 4( n j PBCFj )( ) 6 2 1 1 1 where P4BCF = P4 Bottleneck Correction Factor 2 4( n j PBCFj = (Gap between P61 and P42) + (Gap between P62 and P43) + (Gap between P63 and P44) = Max[0, P32-P61, (VP21+P22+P32) - (P21+P31+P41+ P51+P61)] + Max[0, P33-P62, (VP21+VP22+P23+P33) - (P21+ P31+P41+P51+P61) - (P42+P52+P62)] + Max[0, P34-P63, (VP21+VP22+VP23+P24+P34) - (P21+P31+P41+P51+P61) - (P42+P52+P62+ P43+P53+P63)] The generalised equation for P4BCF is described as follows: For j=2, P4BCF(j) = Max (2) 3 2 0,(3, )(6,1),(, )(2,1)(.1) ii PjPjPi jVPjPi For j=3,4..n, P4BCF(j) = Max (3) 1 366 21 242 0,(3,)(6,1),( ,)(2,)(.1)( ,) jj ik iik PjPjPi jVPkPiPik where, VP = Virtual processing For j = 1, VP(2,1) = Max [P(2,1), P(1,2)] For j = 2,3…n-1, VP(2,j)= 11 12 (2, )(2,),(1,)(2,) jjj kkk M axVP kPjPkVP k (4) Virtual processing (VP) time is an imaginary process- ing time that assumes the starting time of any work process (WP) must begin immediately after the comple- tion of the previous imaginary WP at the same work cen- tre (WC). For the example in Figure 2, consider a job X starting on WC 2 (P22) and at the same time a job Y starts at WC 1 (P13). If the completion time of job X on WC 2 is earlier than the completion time of job Y at WC 1, under the imaginary concept, the VP of job X at WC 2 is extended from its actual processing time to match the completion time of job Y at WC 1. This means the VP of job X at WC 2 (or VP22) is equivalent to the processing time of job Y at WC 1 since the process at WC 2 for job Y can only be started immediately after the completion of Job Y at WC 1 regardless of the earlier completion time of job X at WC 2. The accuracy of Equation (1) was tested with a total of 10,000 simulations conducted using random data of be- tween 1 to 80 hours for each of P( 1, j ), P( 2, j ), P( 3, j ), P( 4, j ), P( 5, j ) and P( 6, j) with six job sequence for each simulations. The simulations were coded in VBA for Microsoft Excel. Each set of random data obtained was also tested with a total of 720 different sequences that resembles the sequence arrangement of ABCDEF, ABCDFE, ABCEDF etc. The makespan from (1) were compared with makespan from Algorithm 1. The result of the simulation shows that 100% of the makespan val- ues for both methods are the same. This indicates the accuracy of (1) in computing the makespan of the 6 job CMC operations scheduling. Equation (1) was also tested for computing the makespan for 10-job and 20-job CMC scheduling. All results indicate that (1) produces accurate makespan result. 4. Bottleneck Adjacent Matching 2 (BAM2) Heuristic The Bottleneck Adjacent Matching 2 (BAM2) heuristic, which is thoroughly illustrated in this section, exploits the bottleneck limiting characteristics of the CMC proc- ess scheduling. The BAM2 heuristic will generate a Copyright © 2010 SciRes JSEA Makespan Algorithms and Heuristic for Internet-Based Collaborative Manufacturing Process Using Bottleneck Approach 94 schedule which selects a job based on the best matching index to the previous job bottleneck processing time, which is the P4 + P5 + P6 (or P456) of the previous job. Ultimately, this minimizes the discontinuity time be- tween the bottleneck machines and thus produces near-optimal schedule arrangement. The procedures to implement the BAM2 heuristic to the CMC scheduling are as the followings: Step 1: Select the job with the smallest value of P(1,j) + P(2,j) + P(3,j) as the first job. If more than one job are having the same smallest value of P(1,j) + P(2,j) + P(3,j), select the first job found to have the smallest P(1,j) + P(2,j) + P(3,j) value. This step is in accordance with (1), which indicated that minimum makespan can be achieved by assigning small- est P(1,j) + P(2,j) + P(3,j) as first job. Step 2: Compute the BAM2 index for the potential second job selection by testing each of the remaining jobs as the second job. The BAM2 indexes are derived from the P4BCF algorithm as in (2) and (3) and are computed as the followings: For j =2, BAM2 index= Max (5) 3 2 (3, )(6,1),(,)(2,1)(.1) i PjPjPi jVPjPi 6 2i 1j ) For j = 3,4,..n, BAM2 index= Max 1 366 21 242 (3,)(6,1),( ,)(2,)(.1)( ,) j ik iik PjPjPi jVPkPiPik (6) where j = remaining jobs to be selected one after the other j-1 = the immediate preceding job that has been assigned The value of VP is computed using (4). Step 3: Select the job that has zero BAM2 index. If no zero BAM2 index is available, select the job that has the larg- est negative BAM2 index (negative BAM1 index closest to zero). If no negative BAM2 index is available, select the job with the smallest positive BAM2 index. Assign this job for the current job scheduling. If more than one job have the same best index value, select the first job found to have the best index value from the jobs list. Step 4: Compute the BAM2 index for job scheduling assign- ment number 3, 4….n-1 one after the other using algo- rithm at Step 2 and select the best job allocation using Step 3. Assign the last remaining job as the last job. Step 5: Compute the makespan of the completed job schedul- ing sequence using (1). Step 6: For the first completed schedule only, use the bottle- neck scheduling performance 2 (BSP2) index to evaluate the schedule performance. This index is computed as the followings: BSP2 index = + (7) 3 1 (,1) i Pi 2 4( n j PBCFj Excluding the first job in the completed schedule, identify other jobs which have the value of less than the BSP2 index. Assign these jobs one after the other as the first job and repeat Step 2 to Step 5. 3 1 (, ) i Pi j Step 7: From the completed schedule arrangement list, select the schedule that produces the minimum makespan as the BAM2 heuristic solution. 5. BAM2 Heuristic Performance Evaluation This section discusses the BAM2 heuristic performance evaluation under a few selected operating conditions. Since the P456 dominance level is the major characteris- tic being considered in developing the BAM2 heuristic, it is appropriate to test the performance of this heuristic under various groups of dominance level values. The dominance level is measured by observing how many times the value of P2+P3+P4+P5+P6 of any job greater than P1+P2+P3 of other jobs. Similar to [13], the domi- nance level groups are divided into levels of weak P456 dominance, medium P456 dominance and strong P456 dominance. The determination of the group dominance level ranges is solely depended on the value of the maximum possible P456 dominance level divided by 3. For the experimentation that uses 6 job analysis, the maximum possible P456 dominance level equals to (n-1)n = (6-1)6 = 30. The P456 dominance level range values are summarised in Table 1. The performance evaluation was simulated using groups of 6 jobs waiting to be scheduled at the CMC. The selection of 6 jobs enables fast enumeration of all possible job sequences that can be used to compare with the BAM2 heuristic result. The processing time for each process was randomly generated using uniform distribu- tion pattern on the realistic data ranges as in Table 2. During each simulation, data on P1 dominance level, minimum makespan from BAM2 heuristic and optimum makespan from complete enumeration were recorded. The ratio between BAM2 heuristic makespan and the optimum makespan from enumeration was then com- puted for performance measurement. A total of 3000 simulations were conducted using the randomly gener- ated data and the results are tabulated in Table 3. The average makespan ratio in Table 3 represents the average ratio of the makespan from BAM2 heuristic to the optimum makespan from complete enumeration. The optimum result column registers the percentage of oc- Copyright © 2010 SciRes JSEA Makespan Algorithms and Heuristic for Internet-Based Collaborative Manufacturing Process Using Bottleneck Approach 95 currences in which the makespan from BAM2 heuristic equals the optimum makespan from complete enumera- tion. The general results indicate that the BAM2 heuristic produces overall makespan solutions that are 1.7% above the optimum. This is shown by the overall average makespan ratio of 1.017. However, the result also sug- gested that the BAM2 heuristic is very effective in solv- ing the scheduling problems within the strong P456 dominance level range. This is indicated by the average makespan ratio of 0.1% above the optimum at the strong P456 dominance level range. Moreover, it was also noted that at this dominance range, 89.47% of the solution generated by the heuristic are the optimum solutions. The percentage of optimum results decreases at the medium P456 dominance (42.26%) and the weak P456 domi- nance (47.37%). For comparison purposes, a similar test was also con- ducted using the NEH heuristic, which is the best known heuristic for flow-shop scheduling [13,19] in predicting the job sequence that produces optimum makespan for the CMC. The result of this test is illustrated in Table 4. Table 1. P456 dominance level groups P456 Dominance Descrip- tions Ranges of P456 Dominance Level (P456DL) Weak 0456 (1/3)(1PDLnn) Medium (1/3)( 1)456(2/3)( 1)nnPDLnn Strong (2 / 3)(1)456(1)nnPDL nn Table 2. Process time data range (hours) P(1,j) P(2,j) P(3,j) P(4,j) P(5,j)P(6,j) Minimum 8 4 4 8 4 8 Maximum 150 16 16 60 16 60 Table 3. BAM2 heuristic performance for 6 job problems P456 Dominance Level Average Makespan Ratio Optimum result (%) Strong 1.001 89.47 Medium 1.020 42.26 Weak 1.017 47.37 Overall 1.017 51.17 Table 4. NEH heuristic performance for 6 job problems P456 Dominance Level Average Makespan Ratio Optimum result (%) Strong 1.0004 93.32 Medium 1.0001 98.04 Weak 1.00001 99.70 Overall 1.0002 97.63 Comparing Tables 4 and 3, it can be clearly seen that NEH heuristic produces good results and is superior to BAM2 heuristic in solving the CMC 6 job re-entrant flow shop problem. This indicates that for larger prob- lems, where complete enumeration is not practical, NEH heuristic is an appropriate tool that can be used to meas- ure the BAM2 performance. In analysing the six job problems, the makespan results from the BAM2 heuristic were also compared with the NEH heuristic. The result of this comparison is illustrated in Table 5. From the makespan performance comparison between BAM2 and NEH in solving the CMC scheduling for 6 job problems (Table 5), it can be seen that BAM2 pro- duces best result at strong P456 dominance level. Here, 84.82% of BAM2 results are the same with NEH, 5.47% of BAM2 results are better than NEH while 9.72% of BAM2 results are worse than NEH. Since this study con- siders NEH as the best and appropriate tool for BAM2 performance verification, it can be highlighted that at strong P456 dominance level, BAM2 produces 84.82% + 5.47% or 90.29% accurate result. This dominance level also produces average BAM2 makespan performance of 0.1% above the NEH makespan. Observations at Table 5 also suggest that BAM2 is less accurate in solving the CMC scheduling problem at both medium and weak P456 dominance level. The BAM2 performance evaluation was also simu- lated using groups of 10 jobs waiting to be scheduled at the CMC. Similar with the 6 job test, the processing time for each process for the 10 job problems was randomly generated using uniform distribution pattern on the real- istic data ranges as in Table 2. A total of 3000 simula- tions of 10 job problems using the randomly generated data were conducted. The simulation result analysis is presented in Table 6. From Table 6, it can be seen that for 10 job problems, BAM2 also produces best result at strong P456 domi- nance level. Here 90.83% of BAM2 results are the same with NEH, 6.59% of BAM2 results are better than NEH while 2.58% of BAM2 results are worse than NEH. Overall, at the strong P456 dominance level BAM2 pro- duces 90.83% + 6.59% or 97.42% accurate results that equal to or better than the NEH makespan results. This dominance level also produces average BAM2 makespan performance of 0.02% below the NEH makespan. Ob- servations at Table 6 also suggest that BAM2 is less ef- fective in solving the CMC 10 job scheduling problems at both medium and weak P456 dominance level. A new simulation was also conducted to evaluate the capability of the BAM2 heuristic in estimating near op- timal job sequences for CMC 20 job problems. A total of 1500 simulations of 20 job problems using the randomly generated data that fulfilled the typical processing time ranges at Table 2 were conducted. The simulation result analysis is presented in Table 7. Copyright © 2010 SciRes JSEA Makespan Algorithms and Heuristic for Internet-Based Collaborative Manufacturing Process Using Bottleneck Approach 96 Table 5. BAM2 vs NEH makespan performance for 6 job problems P456 Domi- nance Level Average BAM2/NEH Ratio BAM2 < NEH (%) BAM2 = NEH (%) BAM2 > NEH (%) Strong 1.001 5.47 84.82 9.72 Medium 1.020 0.81 41.88 57.31 Weak 1.017 0 47.52 52.48 Overall 1.016 1.4 50.2 48.4 Table 6. BAM2 vs NEH makespan performance for 10 job problems P456 Domi- nance Level Average BAM2/NEH Ratio BAM2 < NEH (%) BAM2 = NEH (%) BAM2 > NEH (%) Strong 0.9998 6.59 90.83 2.58 Medium 1.011 7.50 40.44 52.06 Weak 1.015 4.36 21.51 74.13 Overall 1.010 7.03 44.13 48.83 Table 7. BAM2 vs NEH makespan performance for 20 job problems P456 Domi- nance Level Average BAM2/NEH Ratio BAM2 < NEH (%) BAM2 = NEH (%) BAM2 > NEH (%) Strong 0.9999 1.02 98.98 0 Medium 1.004 6.96 54.50 38.54 Weak 1.010 0.77 6.15 93.08 Overall 1.005 3.27 49.33 47.4 From Table 7, it can be seen that at strong P456 domi- nance level, BAM2 heuristic produces 98.98% makespan results equal to NEH, 1.02% results better than NEH while none of BAM2 results is worse than NEH. Overall, at the strong P456 dominance level BAM2 produces 100% results that are equal or better than NEH makespan results. This dominance level also produces average BAM2 makespan performance of 0.01% less than the NEH makespan. 6. Conclusions In this paper, we explore and investigate the potential development of a bottleneck-based makespan algorithms and heuristic to minimize the makespan of an Inter- net-based collaborative design and manufacturing proc- ess that resembles a four machine permutation re-entrant flow shop with the process routing of M1,M2,M3,M4,M3,M4. It was shown that using bottleneck-based analysis, effec- tive makespan algorithms and a constructive heuristic known as the BAM2 heuristic can be developed to solve for near-optimal scheduling sequence. The simulation results indicated that especially at strong P456 domi- nance level, the BAM2 heuristic is capable to produce near optimal results for all the problem sizes studied. At strong P456 dominance level, this heuristic generates results which are very much compatible to the NEH. To some extent, in the specific 10 and 20 job problems simulation conducted during the study, the BAM2 shows better makespan performance compared to the NEH within the strong P456 dominance level. The bottleneck approach presented in this paper is not only valid for the CMC alone, but can also be utilised to develop specific heuristics for other re-entrant flow shop operation sys- tems that shows significant bottleneck characteristics. With the successful development of the BAM2 heuristic, the next phase of this research is to further utilize the bottleneck approach in developing heuristic for optimiz- ing the CMC scheduling for the medium and weak P456 dominance level. 7. Acknowledgments This work was partially supported by the Fundamental Research Grant Scheme, Ministry of Higher Education, Malaysia (Cycle 1 2007 Vot 0368). REFERENCES [1] M. Pinedo, “Scheduling: theory, algorithms, and sys- tems,” 2nd Edtion, Upper Saddle River, Prentice-Hall, N.J., 2002. [2] Z. Lian, X. Gu, and B. Jiao, “A novel particle swarm optimization algorithm for permutation flow-shop sched- uling to minimize makespan,” Chaos, Solitons and Frac- tals, Vol. 35, No. 5, pp. 851–861, 2008. [3] S. C. Graves, H. C. Meal, D. Stefek, and A. H. Zeghmi, “Scheduling of re-entrant flow shops,” Journal of Opera- tions Management, Vol. 3, No. 4, pp. 197–207, 1983. [4] J. S. Chen, “A branch and bound procedure for the reen- trant permutation flow-shop scheduling problem,” Inter- national Journal of Advanced Manufacturing Technology, Vol. 29, pp. 1186–1193, 2006. [5] S. W. Choi, and Y. D. Kim, “Minimizing makespan on a two-machine reentrant flowshop,” Journal of The Opera- tional Research Society, Vol. 58, pp. 972–981, 2007. [6] E. Demirkol, R. Uzsoy, “Decomposition methods for reentrant flow shops with sequence dependent setup times,” Journal of Scheduling, Vol. 3, pp. 115–177, 2000. [7] J. C. Pan, and J. S. Chen, “Minimizing makespan in re-entrant permutation flow-shops,” Journal of Operation Research Society, Vol. 54, pp. 642–653, 2003. [8] S. W. Choi, Y. D. Kim, and G. C. Lee, “Minimizing total tardiness of orders with reentrant lots in a hybrid flow- shop,” International Journal of Production Research, Vol. 43, pp. 2049–2067, 2005. [9] S. W. Choi, and Y. D. Kim, “Minimizing makespan on an m-machine re-entrant flowshop,” Computers & Opera- tions Research, Vol. 35, No. 5, pp. 1684–1696, 2008. Copyright © 2010 SciRes JSEA Copyright © 2010 SciRes JSEA 97 [10] J. S. Chen, J. C. H. Pan, and C. K. Wu, “Hybrid tabu search for re-entrant permutation flow-shop scheduling problem. Expert Systems with Applications,” Vol. 34, No. 3, pp. 1924–1930, 2008. [11] J. S. Chen, J. C. H. Pan, and C. M.Lin, “Hybrid genetic algorithm for the re-entrant flow-shop scheduling prob- lem. Expert Systems with Applications,” Vol. 34, pp. 570–577, 2008. [12] S. Mukherjee, and A. K. Chatterjee, “Applying machine based decomposition in 2-machine flow shops,” European Journal of Operational Research, Vol. 169, pp. 723–741, 2006. [13] A. A. Kalir , and S. C. Sarin, “A near optimal heuristic for the sequencing problem in multiple-batch flow-shops with small equal sublots,” Omega, Vol. 29, pp. 577–584, 2001. [14] J. B. Wang, F. Shan, B. Jiang, and L. Y. Wang, “Permu- tation flow shop scheduling with dominant machines to minimize discounted total weighted completion time,” Applied Mathematics and Computation, Vol. 182, No. 1, pp. 947–957, 2006. [15] B. C. Choi, S. H. Yoon, and S. J. Chung, “Minimizing maximum completion time in a proportionate flow shop with one machine of different speed,” European Journal of Operational Research, Vol. 176, No. 2, pp. 964–976, 2007. [16] M. B. Cheng, S. J. Sun, and L. M. He, “Flow shop sched- uling problems with deteriorating jobs on no-idle domi- nant machines,” European Journal of Operational Re- search, Vol. 183, pp. 115–124, 2007. [17] S. A. Bareduan, S. H. Hasan, N. H. Rafai, and M. F. Shaari, “Cyber manufacturing system for small and me- dium enterprises: a conceptual framework,” Transactions of North American Manufacturing Research Institution for Society of Manufacturing Engineers, Vol. 34, pp. 365–372, 2006. [18] S. A. Bareduan, S. H. Hasan, and S. Ariffin, “Finite scheduling of collaborative design and manufacturing ac- tivity: a Petri net approach,” Journal of Manufacturing Technology Management, Vol. 19, No. 2, pp. 274–288, 2008. [19] P. J. Kalczynski, and J. Kamburowski, “On the NEH heuristic for minimizing the makespan in permutation flow shops,” Omega, Vol. 35, pp. 53–60, 2007. |