The purpose of this thesis is to develop effective scheduling methodologies for real-life shop scheduling problems which have several complicated operating characteristics. Effective control of material movement through manufacturing facilities becomes a very important issue in today's highly competitive environment.
In the first part of the thesis, we consider two kinds of scheduling problems of a flow line with a set of jobs given. The flow line consists of two machines where only one of them has separable, external, and sequence-dependent setup times. A most unusual aspect of the problems is that the setup times required for a job in one of the two machines depend not on the immediately preceding job but on the job which is n steps prior to it. The problems are solved by a dynamic programming with the objective of the minimum makespan. An optimal schedule is found utilizing the sequence dominance condition. Since the computational requirements of the dynamic programming are impracticably demanding for large-sized problems, a genetic algorithm is developed whose performance is examined through a comparative study.
The second part addresses a shop scheduling problem where a set of n jobs needs to be scheduled on two machines for the side frame press shop in a truck manufacturing company. In the problem, the first machine has sequence-dependent setup times and the length of setup times required for a job depends on the job which is two steps prior to it. Moreover, the problem is complicated by the presence of reentrant work flows. Redefining the job elements, the problem is formulated into a general two machine flow shop problem which can be solved by a dynamic programming with the objective of the minimum makespan. An optimal schedule is found utilizing the sequence dominance conditions and the decision-delay scheme. Due to the impracticably demanding computational requirements of the dynamic programming for large-sized problems, a genetic algorithm is developed and its performance is examined through a comparative study.
The final part of this thesis deals with a general job shop problem characterized by reentrant work flows and sequence-dependent setup times. We use the disjunctive graph representation of the job shop with the objective of the minimum makespan to capture the interactions between machines. For this representation, two single-path heuristics and two shift bottleneck approaches are proposed. The obtained solutions are further improved by reversing the directions of some critical disjunctive arcs of the graph. Also, we propose a local improvement imbedded genetic algorithm which combines a genetic algorithm with an efficient improvement heuristic. In this case, we utilize the Taguchi method to determine the values of various genetic parameters and examine the validity of the result by comparing its SN ratios with those obtained by an experiment with full factorial design. A comparative study is conducted to examine the performances of these proposed algorithms.
오늘날과 같이 경쟁적인 경영 환경하에서 제조시스템의 생산성을 높이기 위해서는 시스템내의 물류를 효율적으로 관리할 수 있는 방법론이 필수적으로 요구된다. 본 논문에서는 여러 가지 복잡한 특성을 갖고 있는 실제 현장의 제조시스템을 대상으로 효율적이면서도 효과적인 스케쥴링 방법론을 개발하였다.
본 논문의 첫부분에서는, 두 대의 기계로 구성된 흐름라인에서 주어진 작업들의 작업 순서를 결정하는 문제를 다루었다. 다루어진 문제상황의 특성으로서 두 기계중 어느 한 기계에서 기계 가공 전에 세트업시간(setup time)이 존재하는데 이 세트업은 기계 가공 중에도 외부에서 다른 작업의 세트업을 수행할 수 있으며 작업 순서에 종속적인 특성을 갖고 있다. 문제가 갖는 특성 중 가장 특이한 점은 세트업시간이 n-단계 전 작업에 따라 달라진다는 것이다. 이 문제를 총 작업시간의 합(makespan)을 최소화하는 목적하에서 동적계획법을 이용하여 최적해를 구하는 방법론을 제시하였다. 또한 대형 문제에 적용하기 위하여 유전해법을 개발하였다. 개발된 해법에 대해, 먼저 소형의 문제에 대해 동적계획법의 효율성에 대해 평가하여 현실적인 문제에 적용 가능함을 o}맙눗,} 유전해법의 효율성과 효과성을 평가하기 위해 소형의 문제에 대해서는 동적계획법에 의해서 구한 최적해와 비교하였으며 대형의 문제에 대해서는 하한치와 비교를 수행하였다.
본 논문의 두번째 부분에서는, 상용차 제조업체의 프레스 공정을 대상으로 두 대의 기계로 구성된 시스템에서의 일정계획 문제를 다루었다. 이 문제에서는 첫번째 기계에서 가공 순서에 종속적인 세트업시간을 갖는데 그 시간이 두단계 전 작업에 따라 달라지며 재진입하는 작업 흐름이 존재하여 문제의 복잡성이 더해진다. 작업 요소를 재정의함으로써 본 문제는 일반적인 두 기계 흐름공정으로 변환가능하고 총 작업시간의 합을 최소화하는 목적하에 동적계획법을 개발하였다. 순서우세조건(sequence dominance condition)과 결정연기기법(decision-delay scheme)을 활용하여 최적해를 구하는 방법론을 제시하였다. 대형 문제에 적용하기 위하여 유전해법을 제시한 후, 소형문제에 대해서는 동적계획법을 통해 구한 최적해와 비교 평가하였으며 대형 문제에 대해서는 기존에 개발된 해법들과 비교함으로써 유전해법의 효과와 효율성을 평가하였다.
본 논문의 마지막 부분에서는, 일부의 기계에서 작업 순서에 종속 순서에 세트업시간을 갖고 재진입하는 작업 흐름을 갖는 일반화된 개별공정(job shop)에서의 일정계획 문제를 다루었다. 분리성그래프 표현법(disjunctive graph representation)을 통해 문제를 모형화하여 기계들 간의 상호 작용을 파악하였다. 기존의 연구에서 제안된 개념을 이용하여 네 개의 해법을 제시하였고, 추가로 국부 향상기법(local improvement)이 내재된 유전해법을 제시하였다. 또한 다구치방법을 이용하여 유전해법의 성능에 큰 영향을 미치는 여러 인수들을 결정하는 방법론을 제안하고 완전요인실험(full factorial experiment)을 통해 그 타당성을 평가하였다. 제안된 해법들의 수행도를 평가하기 위해 비교 실험을 수행하였다.
