Browsing by Author "Chen, Chen-Fu"

Now showing 1 - 8 of 8

A comparison of two chromosome representation schemes used in solving a family-based scheduling problem
(2013-06-01)
Chen, Chen-Fu
;
Wu, Muh-Cherng
;
Li, Yi-Hsun
;
Tai, Pang-Hao
;
Chiou, Chie-Wun
Meta-heuristic algorithms have been widely used in solving scheduling problems; previous studies focused on enhancing existing algorithmic mechanisms. This study advocates a new perspective developing new chromosome (solution) representation schemes may improve the performance of existing meta-heuristic algorithms. In the context of a scheduling problem, known as permutation manufacturing-cell flow shop (PMFS), we compare the effectiveness of two chromosome representation schemes (S-old and S-new) while they are embedded in a meta-heuristic algorithm to solve the PMFS scheduling problem. Two existing meta-heuristic algorithms, genetic algorithm (GA) and ant colony optimization (ACO), are tested. Denote a tested meta-heuristic algorithm by X_Y, where X represents an algorithmic mechanism and Y represents a chromosome representation. Experiment results indicate that GA_S-new outperforms GA_S-old, and ACO_S-new also outperforms ACO_S-old. These findings reveal the importance of developing new chromosome representations in the application of meta-heuristic algorithms. (C) 2012 Elsevier Ltd. All rights reserved.
A genetic algorithm embedded with a concise chromosome representation for distributed and flexible job-shop scheduling problems
(2018-01-01)
Lu, Po-Hsiang
;
Wu, Muh-Cherng
;
Tan, Hao
;
Peng, Yong-Han
;
Chen, Chen-Fu
This paper proposes a genetic algorithm for solving distributed and flexible job-shop scheduling (DFJS) problems. A DFJS problem involves three scheduling decisions: (1) job-to-cell assignment, (2) operation-sequencing, and (3) operation-to-machine assignment. Therefore, solving a DFJS problem is essentially a 3-dimensional solution space search problem; each dimension represents a type of decision. The algorithm is developed by proposing a new and concise chromosome representation , which models a 3-dimensional scheduling solution by a 1-dimensional scheme (i.e., a sequence of all jobs to be scheduled). That is, the chromosome space is 1-dimensional (1D) and the solution space is 3-dimensional (3D). In , we develop a 1D-to-3D decoding method to convert a 1D chromosome into a 3D solution. In addition, given a 3D solution, we use a refinement method to improve the scheduling performance and subsequently use a 3D-to-1D encoding method to convert the refined 3D solution into a 1D chromosome. The 1D-to-3D decoding method is designed to obtain a "good" 3D solution which tends to be load-balanced. In contrast, the refinement and 3D-to-1D encoding methods of a 3D solution provides a novel way (rather than by genetic operators) to generate new chromosomes, which are herein called shadow chromosomes. Numerical experiments indicate that outperforms the IGA developed by De Giovanni and Pezzella (Eur J Oper Res 200:395-408, 2010), which is the up-to-date best-performing genetic algorithm in solving DFJS problems.
An analysis of the ceiling height requirement for a large-scale semiconductor fab
(2010)
Wu, Muh-Cherng
;
Shih, Chang-Fu
;
Chen, Chen-Fu
;
工業工程與管理學系
;
Department of Industrial Engineering and Management
This paper proposes the proposition that the fab ceiling height may become a bottleneck for throughput in a large-scale semiconductor fab. To justify the proposition, we propose a systematic approach for the design of the fab ceiling height. In this approach, we develop a queuing network model to evaluate the cycle time performance of a fab design under a target throughput. This queuing network model is adapted from Connor et al. [1996. A queueing network model for semiconductor manufacturing. IEEE Transactions on Semiconductor Manufacturing, 9 (3), 412-427] by additionally treating the transportation facilities as finite-capacity resources. Numerical experiments were carried out. The results indicate that a large-scale fab with an inappropriate ceiling height may limit the installation of transportation capacity, which, in turn, limits the utilisation of tool capacity, and thus lowers the fab throughput that can be achieved.
An efficient approach to cross-fab route planning for wafer manufacturing
(2009-10-01)
Wu, Muh-Cherng
;
Shih, Chang-Fu
;
Chen, Chen-Fu
;
工業工程與管理學系
;
Department of Industrial Engineering and Management
This paper proposes an efficient approach to solve a cross-fab route planning problem for semiconductor wafer manufacturing. A semiconductor company usually adopts a dual-fab strategy. Two fab sites are built neighbor to each other to facilitate capacity-sharing. A product thus may be produced by a cross-fab route; that is, some operations of a product are manufactured in one fab and the other operations in the other fab. This leads to a cross-fab routing planning problem, which involves two decisions-determining the cut-off point of the cross-fab route and the route ratio for each product-in order to maximize the throughput subject a cycle time constraint. A prior study has proposed a method to solve the cross-fab route planning problem; yet it is computationally extensive in solving large scale cases. To alleviate this deficiency, we proposed three enhanced methods. Experiment results show that the best enhanced method could significantly reduce the computational efforts from about 13 h to 0.5 h, while obtaining a satisfactory solution. (C) 2009 Elsevier Ltd. All rights reserved.
Dispatching for make-to-order wafer fabs with machine-dedication and mask set-up characteristics
(2008)
Wu, Muh-Cherng
;
Chiou, Shau-Jie
;
Chen, Chen-Fu
;
工業工程與管理學系
;
Department of Industrial Engineering and Management
This paper develops a dispatching algorithm to improve on-time delivery for a make-to-order semiconductor wafer fab with two special characteristics: mask set-up and machine dedication. A new algorithm is proposed for dispatching series workstations. Simulation experiments show that the algorithm outperforms the previous methods both in on-time delivery rate, cycle time, and only slightly less than the best benchmark in throughput. The experiments are carried out in 10 test scenarios, which are created by the combination of two product-mix ratios and five mask set-up times.
Effect of solution representations on Tabu search in scheduling applications
(2013-12-01)
Chen, Chen-Fu
;
Wu, Muh-Cherng
;
Lin, Keng-Han
;
工業工程與管理學系
;
Department of Industrial Engineering and Management
This research investigates the application of meta-heuristic algorithms to a scheduling problem called permutation manufacturing-cell flow shop (PMFS) from two perspectives. First, we examine the effect of using different solution representations (S-new and S-old) while applying Tabu-search algorithm. Experimental results reveal that Tabu_S-new outperforms Tabu_S-old. The rationale why Tabu_S-new is superior is further examined by characterizing the intermediate outcomes of the evolutionary processes in these two algorithms. We find that the superiority of Snew is due to its relatively higher degree of freedom in modeling Tabu neighborhood. Second, we propose a new algorithm GA_Tabu_S-new, which empirically outperforms the state-of-the-art meta-heuristic algorithms in solving the PMFS problem. This research highlights the importance of solution representation in the application of meta-heuristic algorithm, and establishes a significant milestone in solving the PMFS problem. (C) 2013 Elsevier Ltd. All rights reserved.
Effects of different chromosome representations in developing genetic algorithms to solve DFJS scheduling problems
(2017-04)
Wu, Muh-Cherng
;
Lin, Chi-Shiuan
;
Lin, Chia-Hui
;
Chen, Chen-Fu
;
工業工程與管理學系
This paper attempts to compare the effect of using different chromosome representations while developing a genetic algorithm to solve a scheduling problem called DFJS (distributed flexible job shop scheduling) problem. The DFJS problem is strongly NP-hard; most recent prior studies develop various genetic algorithms (GAs) to solve the problems. These prior GAs are similar in the algorithmic flows, but are different in proposing different chromosome representations. Extending from this line, this research proposes a new chromosome representation (called Sop) and develops a genetic algorithm (called GA_OP) to solve the DFJS problem. Experiment results indicate that GA_OP outperforms all prior genetic algorithms. This research advocates the importance of developing appropriate chromosome representations while applying genetic algorithms (or other meta-heuristic algorithms) to solve a space search problem, in particular when the solution space is high-dimensional. (C) 2016 Elsevier Ltd. All rights reserved.
Route planning for two wafer fabs with capacity-sharing mechanisms
(2009)
Wu, Muh-Cherng
;
Chen, Chen-Fu
;
Shih, Chang-Fu
;
工業工程與管理學系
;
Department of Industrial Engineering and Management
This paper formulates and solves a route planning problem for semiconductor manufacturing. In order to quickly respond to rising demand, a semiconductor company usually adopts a dual-fab strategy to expand capacity. That is, two fab sites are built as neighbours and can easily share capacity. Through the capacity-sharing design, a product may be produced by a cross-fab route. That is, some operations of a product are carried out in one fab and the other operations in the other fab. This leads to a routing planning problem, which involves two decisions-determining the cut-off point of the cross-fab route and the route ratio for each product-in order to maximise the throughput subject to a cycle time constraint. An LP-GA method is proposed to solve the route planning problem. We first use the LP module to make the cut-off point decisions, and proceed to use the GA module for making the decision on the route ratio. Experimental results show that the LP-GA method significantly outperforms other methods.