재방문이 있는 혼합흐름공정을 위한 이종목적 생산계획 및 일정계획

Abstract

This dissertation deals with production planning and scheduling problems of hybrid flow shops. The hybrid flow shop has serial stages where each stage consists of identical parallel machines. Products can be processed at any one of the parallel machines at a stage in the hybrid flow shop. Also a product may have reentrant operations which require revisits of some stages several times. This may cause the congestion of work in process (WIP) or equipment idleness. In the real world, a configuration of the reentrant hybrid flow shop may be found in electronics industry such as printed circuit board (PCB), semiconductor wafer fabrication, semiconductor assembly industry, and thin film transistor and liquid crystal display (TFT-LCD) manufacturing. In this dissertation, we consider bi-objective production planning and scheduling such that the productivity and the customer satisfaction are maximized in reentrant hybrid flow shop environments. First, we consider production planning problems for the reentrant hybrid flow shop to improve productivity and customer satisfaction. The objective of production planning is to determine the product mix for different products to be processed different layers at each time period such that the throughput is maximized for productivity and the delayed customer satisfaction is minimized for the customer satisfaction. The proposed problem is formalized by the linear programming model. In addition, we propose two heuristic algorithms based on preemptive goal programming trying to explicitly deal with the objective functions. In the customer first heuristic, we try to maximize the throughput based on the minimized delayed customer demand. In the system first heuristic, the minimization of the delayed customer demand is performed after the optimized throughput is given as a constraint. The proposed algorithms are compared with the existing methods presented in the literatures for simulated data. Second, we propose a Pareto genetic algorithm to solve the scheduling problem. The local-search based Pareto genetic algorithms with Minkowski distance-based crossover operator is proposed to approximate the Pareto optimal solutions for the minimization of makespan and total tardiness in a reentrant hybrid flow shop. The Pareto genetic algorithms are compared with existing multi-objective genetic algorithm, NSGA-II in terms of the convergence to best known solution, the diversity of solution and the dominance of solution. Computational experiments show that the proposed crossover operator and local search are effective and the proposed algorithm outperforms NSGA-II by statistical analysis. Third, we consider two-level hierarchical decisions on production planning and scheduling of the reentrant hybrid flow shop with the bi-objective function to improve productivity and customer satisfaction. We propose two two-level planning and scheduling methods that are the combination of proposed preemptive goal programming based production planning algorithms and Pareto genetic based scheduling algorithms. The objectives of upper-level planning are the maximization of throughput and the minimization of delayed customer demand. The objectives of lower-level scheduling are the minimization of makespan and the minimization total tardiness. The objectives of the proposed two-level planning and scheduling methods are the minimization of makespan and the minimization of delayed customer demand. We compare among proposed algorithms by statistical analysis. Finally, we apply the proposed two-level planning and scheduling methods to a real TFT-LCD manufacturing problem. The proposed two-level planning and scheduling methods are compared with a well-known commercial software based on real scheduling data provided by a TFT-LCD factory. Also, we compare with a single-level method that is the Pareto genetic algorithms which utilize lot sizes proposed the commercial software. The results show that the proposed two-level method outperforms the existing method and single-level method.| 본 논문은 혼합흐름공정의 생산계획 및 일정계획 문제를 다룬다. 혼합흐름공정은 병렬설비로 이루어진 다수의 단계를 포함하고 있다. 제품은 혼합흐름공정의 단계에서 병렬설비 중 하나에서 처리할 수 있다. 또한 제품은 어떤 단계를 여러 번 다시 방문하는 재방문 작업을 수행할 수 있다. 이 과정은 재공∙재고의 혼잡과 설비를 유휴의 원인이 된다. 현실세계에서, 재방문이 있는 혼합흐름공정의 형태는 PCB, 반도체 웨이퍼 제조, 반도체 조립산업, TFT-LCD 생산과 같은 전자산업에서 찾을 수 있다. 본 논문은 재방문이 혼합흐름공정 환경하에서 생산성과 고객만족을 극대화하는 이종목적 생산계획 및 일정계획을 다룬다. 첫째, 우리는 생산성과 고객만족을 향상시키기 위해 재방문이 있는 혼합흐름공정에서 생산계획 문제를 다룬다. 생산계획의 목적은 생산성을 위한 throughput을 최대화하고 고객 만족을 위한 delayed customer demand를 최소화하는 것으로 각 기간에 각각 다른 레이어들이 가공되어야 하는 다른 제품들에 대한 제품믹스를 결정하는 것이다. 제시된 문제는 선형계획 모형으로 공식화한다. 또한, 우리는 목적함수들을 직접적으로 반영하는 목표계획법기반의 2개의 휴리스틱 알고리즘을 제안한다. 고객우선 휴리스틱은 delayed customer demand를 최소화된 상황에서 throughput을 최대화를 진행한다. 시스템우선 휴리스틱은 throughput을 최적화 시킨 후에 delayed customer demand를 최소화를 진행한다. 제안된 알고리즘은 시뮬레이션 데이터에 대한 문헌에서 제시된 기존 알고리즘과 비교한다. 둘째, 우리는 일정계획 문제를 해결하기 위해서 파레토 유전자 알고리즘들을 제안한다. Minkowski 거리기반의 교차 연산자를 사용하는 로컬 탐색 기반의 파레토 유전자 알고리즘들은 재방문이 있는 혼합흐름공정에서 makespan과 tardiness의 최소화에 대한 근사 파레토 최적해를 제안한다. 파레토 유전자 알고리즘들은 현재 알려진 최상의 해로의 수렴과 해의 다양성 및 해의 지배성에 대한 측면들에서 기존의 다중목적 유전자 알고리즘인 NSGA-II와 비교한다. 실험은 제안된 교차 연산자와 지역탐색 방법이 효과적임을 보이며 제안된 알고리즘은 통계분석을 통하여 NSGA-II보다 좋은 성능을 보인다. 셋째, 우리는 생산성과 고객만족을 향상 시키기 위해 이종목적 함수를 가지는 혼합흐름공정에 대한 생산계획과 일정계획의 2수준 계층적 의사결정을 다룬다. 우리는 제안한 선점 목표계획법기반의 생산계획 알고리즘과 파레토 유전자기반의 일정계획 알고리즘의 조합인 2수준 생산계획과 일정계획 방법을 제안한다. 상위수준 생산계획의 이종목적 함수는 throughput의 최대화하고 delayed customer demand를 최소화하는 것이다, 하위수준 일정계획의 목적함수는 makespan을 최소화하고 총 tardiness을 최소화하는 것이다. 제안된 2수준 생산계획 및 일정계획 방법의 이종목적 함수는 makespan 및 delayed customer demand를 최소화하는 것이다. 우리는 통계분석을 통해 제안된 알고리즘 사이를 비교한다. 마지막으로, 우리는 제안한 2수준 생산계획 및 일정계획 방법을 실제 TFT-LCD 생산 문제에 적용한다. 제안한 2수준 생산계획 및 일정계획 방법은 TFT-LCD 공장에서 제공된 실시간 계획 데이터를 기반으로 상용 소프트웨어와 비교한다. 또한, 우리는 상용 소프트웨어의 제시한 로트 크기들을 적용한 파레토 유전자 알고리즘들인 단일수준 방법도 비교한다. 결과는 제시한 2수준 방법이 기존의 방법과 단일수준 방법을 능가하는 것을 보여준다.; This dissertation deals with production planning and scheduling problems of hybrid flow shops. The hybrid flow shop has serial stages where each stage consists of identical parallel machines. Products can be processed at any one of the parallel machines at a stage in the hybrid flow shop. Also a product may have reentrant operations which require revisits of some stages several times. This may cause the congestion of work in process (WIP) or equipment idleness. In the real world, a configuration of the reentrant hybrid flow shop may be found in electronics industry such as printed circuit board (PCB), semiconductor wafer fabrication, semiconductor assembly industry, and thin film transistor and liquid crystal display (TFT-LCD) manufacturing. In this dissertation, we consider bi-objective production planning and scheduling such that the productivity and the customer satisfaction are maximized in reentrant hybrid flow shop environments. First, we consider production planning problems for the reentrant hybrid flow shop to improve productivity and customer satisfaction. The objective of production planning is to determine the product mix for different products to be processed different layers at each time period such that the throughput is maximized for productivity and the delayed customer satisfaction is minimized for the customer satisfaction. The proposed problem is formalized by the linear programming model. In addition, we propose two heuristic algorithms based on preemptive goal programming trying to explicitly deal with the objective functions. In the customer first heuristic, we try to maximize the throughput based on the minimized delayed customer demand. In the system first heuristic, the minimization of the delayed customer demand is performed after the optimized throughput is given as a constraint. The proposed algorithms are compared with the existing methods presented in the literatures for simulated data. Second, we propose a Pareto genetic algorithm to solve the scheduling problem. The local-search based Pareto genetic algorithms with Minkowski distance-based crossover operator is proposed to approximate the Pareto optimal solutions for the minimization of makespan and total tardiness in a reentrant hybrid flow shop. The Pareto genetic algorithms are compared with existing multi-objective genetic algorithm, NSGA-II in terms of the convergence to best known solution, the diversity of solution and the dominance of solution. Computational experiments show that the proposed crossover operator and local search are effective and the proposed algorithm outperforms NSGA-II by statistical analysis. Third, we consider two-level hierarchical decisions on production planning and scheduling of the reentrant hybrid flow shop with the bi-objective function to improve productivity and customer satisfaction. We propose two two-level planning and scheduling methods that are the combination of proposed preemptive goal programming based production planning algorithms and Pareto genetic based scheduling algorithms. The objectives of upper-level planning are the maximization of throughput and the minimization of delayed customer demand. The objectives of lower-level scheduling are the minimization of makespan and the minimization total tardiness. The objectives of the proposed two-level planning and scheduling methods are the minimization of makespan and the minimization of delayed customer demand. We compare among proposed algorithms by statistical analysis. Finally, we apply the proposed two-level planning and scheduling methods to a real TFT-LCD manufacturing problem. The proposed two-level planning and scheduling methods are compared with a well-known commercial software based on real scheduling data provided by a TFT-LCD factory. Also, we compare with a single-level method that is the Pareto genetic algorithms which utilize lot sizes proposed the commercial software. The results show that the proposed two-level method outperforms the existing method and single-level method.