576 0

Full metadata record

DC FieldValueLanguage
dc.contributor.advisor이동호-
dc.contributor.author최현선-
dc.date.accessioned2020-04-03T17:15:54Z-
dc.date.available2020-04-03T17:15:54Z-
dc.date.issued2009-02-
dc.identifier.urihttps://repository.hanyang.ac.kr/handle/20.500.11754/145579-
dc.identifier.urihttp://hanyang.dcollection.net/common/orgView/200000410715en_US
dc.description.abstract본 논문은 혼합흐름공정에서의 일정계획문제를 다루고 있다. 혼합흐름공정이란 각 작업이 동일한 공정순서를 거쳐 완성되는 형태의 전통적인 흐름공정에서 작업장마다 생산용량을 증가시키기 위해 복수의 병렬기계가 존재하는 형태의 생산시스템을 의미한다. 이러한 혼합흐름공정은 전자 및 반도체 가공 공정, 인쇄회로기판 등 첨단 산업에서뿐만 아니라 화학, 철강, 식품 등 전통적인 산업에서 많이 발견되는 형태이다. 혼합흐름공정은 작업의 흐름에 따라 단방향 흐름과 재방문의 형태로 구분된다. 먼저 단방향 흐름에서 각 작업은 첫 번째 작업장에서 출발하여 마지막 작업장을 거쳐 작업이 완료된다. 이와는 반대로 재방문에서의 각 작업 흐름은 각 작업장에 대하여 다수회의 방문을 통해 작업이 수행된다. 본 논문은 단방향 및 재방문을 고려한 혼합흐름공정에서의 일정계획 문제에 관한 연구를 수행하였다. 첫 번째로, 두 개의 작업장으로 구성된 단방향 혼합흐름공정에서 납기지연 작업 수를 최소화하는 일정계획 문제를 다루었었다. 각 작업들은 연속적인 두 작업장을 통하여 작업이 완료되며 각 작업장에는 동일 병렬기계들이 존재한다. 이 장에서 고려하고 있는 문제에의 경우 각 기계에 작업을 할당하는 문제와 더불어 각 기계에 할당된 작업의 순서를 동시에 결정하여야 한다. 본 장에서는 최적해를 구하기 위해 분지 한계 방법(branch and bound algorithm)을 개발하였고 해의 탐색 영역을 줄이기 위한 방법으로 해의 우월성질(dominance property), 하한(lower bound) 및 상한(upper bound)을 개발하였으며 이를 제안하는 분지한계 방법에 이용하였다. 추가적으로 대규모 문제에 대해서는 2단계로 구성된 다양한 발견적 기법을 제안하였다. 분지한계 방법과 발견적 기법의 성능 평가를 위해 임의로 생성한 문제에 대하여 실험을 수행하였다. 두 번째로, 두 개의 작업장으로 구성된 혼합흐름공정에서 작업의 재방문을 고려한 문제에 대하여 연구하였다. 이 문제에서는 주어진 납기에 대하여 최대 연장가능 허용치의 범위 내에서 총 작업완료 시간을 최소화 하는 문제를 다루고 있다. 이 문제의 해를 구하기 위해 두 가지 해법을 제안하고 있다. 첫 번째로 반순열일정계획해(semi-permutation schedule)에 대해 최적해을 찾기 위하여 분지한계 알고리듬을 제한하였다. 두 번째로 비순열일정계획해(non-permutation schedule)에 대하여 발견적 기법의 알고리듬을 제안하였다. 실험 결과 발견적 기법의 알고리듬 성능은 분지한계 방법에서의 최적해와 큰 차가 없었다. 세 번째로 고려한 문제는 첫 번째 문제를 확장한 것으로 다수개의 작업장으로 구성된 혼합흐름공정에서 일정계획 문제를 다루고 있으며 납기지연 작업의 수를 최소화 하는 것을 목적으로 하는 문제를 연구하였다. 이 장에서 고려하고 있는 문제의 경우 문제의 복잡도로 인해 tabu search 알고리듬과 simulated annealing 알고리듬을 제안하였다. 이 연구에서는 국지최적으로 수렴하는 납기지연 작업 수 최소화라는 목적함수의 특성을 고려하여 세가지 대체 목적함수를 이용한 이웃해 생성방법을 제안하였으며 실험결과 대체 목적함수를 사용하는 것이 우수한 결과값을 보이는 것으로 나타났다. 또한, 두 개의 작업장으로 구성된 소규모 문제에 대한 실험결과 제안한 탐색기법이 분지한계 방법에 비해 적절한 계산시간 내에 대부분의 문제에 대하여 최적해를 찾을 수 있었다. 마지막으로 두 번째 문제를 확장한 문제를 고려하였는데 이 문제에서는 다수개의 작업장으로 구성된 혼합흐름공정에서 작업의 재방문을 고려한 문제에 대하여 연구하였다. 이 연구에서는 기존의 이론적인 연구와 차별화 하기 위하여 시뮬레이션 기반의 실시간 일정계획 수립에 관한 방법을 제안하였다. 제안하는 방법은 의사결정나무(decision tree) 알고리듬을 이용하여 현재 시스템의 상황하에서 여러 우선순위 규칙들 중 적절한 규칙을 선택하는 방법이다. 일반적으로 실시간 일정계획 수립을 위한 문제에서 시뮬레이션을 통한 작업의 우선순위 결정방법의 경우 의사결정을 위해 지나치게 많은 시간이 소요되는 단점이 있는 것으로 알려져 왔다. 본 연구에서 이러한 문제점을 보완하고자 의사결정나무 알고리듬을 이용한 신속한 의사 결정 수립 방법을 제안하였으며 이를 Thin Film Transistor - Liquid Crystal Display (TFT-LCD) 생산라인에 적용한 사례연구를 수행하였다.; This dissertation focuses on scheduling problems in hybrid flow shops that consist of two or more production stages in series, but there exist one or more parallel machines at each stage. The parallel machines are added to each stage for the objective of increasing productivity as well as flexibility. The hybrid flow shops can be found mainly in the electronics industry such as printed circuit board manufacturing, semiconductor manufacturing, and lead frame manufacturing. Also, various traditional industries, such as food, chemical and steel, have hybrid flow shops. Ac-cording to product flows, the hybrid flow shops can be classified into two types: (a) those with unidirectional flows; and (b) those with reentrant flows. The unidirectional flows imply that each job starts at the first stage and finishes at the last stage. On the other hands, in the reentrant flows, each job may visit (enter) each serial stage two or more times. In this dissertation, we consider the scheduling problems in unidirectional and reentrant hybrid flow shops. First, we consider the two-stage unidirectional hybrid flow shop sche-duling problem for the objective of minimizing the number of tardy jobs. Each job is processed through the two production stages in series, each of which has multiple identical parallel machines. The problem is to de-termine the allocation of jobs to the parallel machines as well as the se-quence of the jobs assigned to each machine. To solve the problem, a branch and bound algorithm, which incorporates the methods to obtain the lower and upper bounds as well as the dominance properties to re-duce the search space, is suggested that gives the optimal solutions. In addition, two-phase heuristic algorithms are suggested to obtain good solutions for large-size problems within a reasonable amount of compu-tation time. To show the performances of the optimal and heuristic algo-rithms suggested in this chapter, computational experiments are done on a number of randomly generated test problems, and the test results are reported. Second, we consider the scheduling problem in two-stage reentrant hybrid flow shops in which each job has reentrant flow, i.e., the job visits each production stage several times. The objective is to minimize makes-pan subject to the maximum allowable due-dates in the form of a con-straint set with a certain allowance. To solve the problem, two types of algorithms are suggested: (a) a branch and bound algorithm that gives optimal semi-permutation schedules; and (b) heuristic algorithms that give non-permutation schedules. Computational experiments were done on a number of test problems and the results show that one of the heu-ristics is competitive to the branch and bound algorithm with respect to the solution quality while requiring much shorter computation times. Third, as an extension of the first problem, we consider the scheduling problem in multi-stage unidirectional hybrid flow shops for the objective of minimizing the number of tardy jobs. Due to the complexity of the problem, we suggest search heuristics that incorporate a new method to generate neighborhood solutions. In particular, to evaluate and select neighborhood solutions, three surrogate objectives are additionally sug-gested because not much difference in the number of tardy jobs can be found among the neighborhoods. To test the performances of the search heuristics, computational experiments were performed on a number of test problems and the results show that the search heuristics with sur-rogate objectives were better than the original ones. Also, they gave the optimal solutions for most small-size test problems. Finally, as an extension of the second problem, we consider the sche-duling problem in multi-stage reentrant hybrid flow shops. Unlike the theoretical approach on reentrant hybrid flow shop scheduling, we sug-gest a real-time scheduling mechanism with a decision tree when select-ing appropriate dispatching rules. Here, the decision tree, one of the commonly used data mining techniques, is adopted to eliminate the computational burden required to carry out simulation runs to select dispatching rules. To illustrate the mechanism suggested in this study, a case study was performed on a thin film transistor - liquid crystal dis-play (TFT-LCD) manufacturing line and the results are reported.-
dc.publisher한양대학교-
dc.titleScheduling Algorithms for Unidirectional and Reentrant Hybrid Flow shops-
dc.title.alternative단방향 및 재방문을 고려한 혼합흐름공정에서의 일정계획 문제에 관한 연구-
dc.typeTheses-
dc.contributor.googleauthor최현선-
dc.sector.campusS-
dc.sector.daehak대학원-
dc.sector.department산업공학과-
dc.description.degreeDoctor-
Appears in Collections:
GRADUATE SCHOOL[S](대학원) > INDUSTRIAL ENGINEERING(산업공학과) > Theses (Ph.D.)
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE