작업 준비시간을 고려한 병렬기계 일정계획 수립에 대한 연구 = (A) Study on Scheduling for Parallel Machines with Setup Considerations

다국어 초록 (Multilingual Abstract)

The objective of this research is to develop heuristic procedures to minimize the maximum total weighted tardiness on parallel identical machines with two sequence dependent setup time cases. For each of the two cases this dissertation proposes an efficient heuristic that minimize the total weighted tardiness when a set of tasks with known processing times, due dates, weights and setup times are to be assigned on parallel machines. Those heuristic are developed to be used in industrial situations, in particular the algorithm best fits in the scheduling of the module process in TFT-LCD manufacturing plants.
Among the developed two, the first heuristic places its focus on the problem with family setup times and parallel machines. In the problem jobs are classified into different families where machine tools spends a long setup time when they switch a processing job family to another family type. Jobs in the same have the same processing time. A two-phase heuristic is presented to minimize total weighted tardiness. In the first phase, the time horizon in the scope is divided into intervals with equal length and the jobs whose due date belongs the same interval division are grouped together. Starting from the most early group, jobs in a group are sequenced by the index calculated by the Apparent Tardiness Cost with Setup(ATCS) rule. The sequence of jobs then is improved upon through use of a proposed Tabu Search(TS) algorithm. In the second phase, jobs are allocated to machines using Threshold value and Look-ahead parameter, and these are also devised for this particular problem.
The second heuristic is developed for the same problem with the first one but an exception is it has sequence dependent setup times and no family setup time. In the heuristic, jobs are first listed by due dates and grouped into given number of clusters. Clusters are formed by the proximity of due dates of jobs. Then a TS algorithm is applied to interchange job positions in intra and inter clusters. A finalized sequence of jobs emerged after the improvement by the proposed TS. Jobs are then allocated to machines by the considering of due date and setup types.
We also present some comprehensive simulation results of the proposed methods and compare these with the ATCS and RHP algorithms. The results showed the proposed methods in most cases outperform ATCS and RHP in terms of computation time and solution quality.

목차 (Table of Contents)

• 목차 = Ⅲ
• 제1장 서론 = 1
• 제1절 연구의 배경 및 목적 = 1
• 제2절 논문의 구성 = 4
• 제2장 기존연구의 고찰 및 TFT-LCD 공정 = 5
• 제1절 기존연구의 고찰 = 5
• 제2절 TFT-LCD 공정 = 11
• 1. TFT 공정 = 12
• 2. 셀(Cell) 공정 = 13
• 3. Module(모듈) 공정 = 14
• 제3장 패밀리 셋업을 고려한 병렬기계 일정계획 = 16
• 제1절 문제의 정의 및 가정 = 16
• 제2절 접근방법 = 18
• 제3절 용어정의 = 20
• 제4절 APFS 알고리즘 = 21
• 1. 선행 계획단계(Pre-Processing Procedure) = 21
• 2. 할당단계(Allocation Procedure) = 31
• 3. 수치 예제 = 37
• 제5절 비교 대안 = 44
• 제6절 실험 데이터 = 45
• 제7절 실험결과 및 분석 = 48
• 1. 전체 수행도 분석 = 49
• 2. 결정모수(λ)에 따른 수행도 분석 = 51
• 3. 할당규칙에 따른 수행도 분석 = 52
• 4. ATCS와 APFS 알고리즘의 수행도 분석 = 55
• 5. TS 알고리즘의 수행도 분석 = 59
• 6. 알고리즘별 수행속도 분석 = 61
• 제4장 순서 의존적인 셋업을 고려한 병렬기계 일정계획 = 62
• 제1절 문제의 정의 및 가정 = 62
• 제2절 접근방법 = 63
• 제3절 용어정의 = 64
• 제4절 DDBC 알고리즘 = 65
• 1. 제1단계: 납기에 의한 정렬 = 65
• 2. 제2단계: 작업군 편성 = 65
• 3. 제3단계: 작업순서 개선 = 69
• 4. 제4단계: 작업할당 = 72
• 제5절 비교 대안 = 75
• 제6절 실험 데이터 = 76
• 제7절 실험결과 및 분석 = 78
• 1. 전체 수행도 분석 = 79
• 2. 기계수에 따른 수행도 분석 = 81
• 3. 작업수에 따른 수행도 분석 = 82
• 4. 셋업의 형태수에 따른 수행도 분석 = 83
• 제5장 결론 = 85
• 참고문헌 = 87