This thesis considers scheduling problems concerned with manufacturing systems including assembly and disassembly features where each produced product is the final product in the assembly system but it is a component for the associated subsequent lines in the disassembly system. In the assembly system, several types of components are produced first at pre-assembly stage of feeding machines and then assembled into final products(jobs) at an assembly stage. Each assembly operation cannot start its processing until all of the associated components are prepared from the precedent pre-assembly stage. In the disassembly system, a disassembly operation for splitting a product into several components is performed and then subsequent parallel machines work with their respective components.
The first problem to be considered in this thesis is to minimize the total weighted completion time of jobs at the pre-assembly stage. The problem is shown to be NP-complete in the strong sense even when there are only two feeding machines. In the analysis, two lower solution bounds are derived and tested in a proposed branch-and-bound scheme. Some solution properties are also characterized, based upon which three heuristic algorithms are derived. The effectiveness of the heuristics is tested with numerical problems and a worst-case analysis is also done.
Secondly, three problems are considered to minimize makespan in a two-stage(pre-assembly stage and final assembly stage) assembly system, a disassembly system, and a combined assembly/ disassembly system, respectively. In the analysis, several solution properties for dominating schedules are characterized, based on which it is proved that the first two problems are equivalent. These results and Johnson*s rule are used to develop a heuristic algorithm. For the last combined system, two meta -heuristic algorithms, taboo search and simulated annealing, are suggested.
The last problem is to minimize total job completion time in a two-stage assembly system with two feeding machines. For the problem, three heuristic algorithms are exploited. The effectiveness of the algorithms is tested with numerical problems, and a worst-case analysis is also done.
본 논문의 목적은 조립 및 분리 공정을 포함하는 생산 시스템에서의 일정계획 수립을 위한 방안을 강구하는데 있다. 지금까지의 조립라인에서의 일정계획과 관련된 연구는 주로 흐름라인(flowshop) 체계에 편중되어 왔다. 그러나 각 부속공정에서 추출물, 도료나 기타 화학 물질이 일정한 비율로 주 조립공정에서 혼합됨으로써 최종 물질이 만들어지는 석유, 화학 산업이나 자동차 및 항공기의 엔진조립라인 등의 비교적 대형의 제품 생산라인은 동시작업 (synchronous operation)라인과 조립작업장이 혼재된 형태로서 기존의 선형라인을 위한 일정계획 도출 방안으로는 좋은 결과를 기대할 수 없다.
본 논문에서 다루는 첫번째 모델은 중간 조립품(부속품)들을 만드는 여러 대의 입력기계(feeding machines)로 구성되는 조립 전단계(pre-assembly stage)에서 작업들의 총가중완료시간(total weighted completion time)을 최소화 하는 일정계획해을 찾는 문제이다. 먼저 제시된 문제가 비다항문제(NP-complete)임을 보이고 해의 공간을 줄이기 위한 여러 개의 우월성질을 규명하였다. 이를 바탕으로 최적해를 위한 분지한계법(branch-and-bound)을 개발하였고 효율적인 해의 도출을 위한 세가지 발견적 해법을 제시하였다. 제시된 발견적 해법의 성능평가를 위해 한계분석(worst-case analysis)과 수치데이타를 통한 실험을 병행하였다.
다음으로는 조립 전단계와 주 조립단계로 구성되는 조립시스템, 분리단계와 병렬처리단계로 구성되는 분리시스템 그리고 조립과 분리가 통합된조립/분리 시스템에서 최대작업완료시간(makespan)을 최소화하기 위한 일정계획 문제를 다루고 있다. 여러 개의 우월성질이 규명되었으며 조립시스템과 분리시스템에서의 문제는 서로 같은 문제임이 증명되었다. 또한, 좋은 성능을 보이는 발견적 해법이 제시되었다. 조립/분리 시스템을 위해서는 한계분석이 수반된 하나의 발견적 해법이 제시되었고 두개의 반복수행 알고리즘이 사용되었다.
마지막으로 두 대의 입력기계와 한대의 조립기계로 구성된 조립시스템에서 총작업완료시간(total completion time)을 최소화 하기 위한 일정계획 문제를 다루고 있다. 문제의 복잡성이 논의 된 후 작업완료시간을 줄이기 위한 방안이 제시된다. 이를 바탕으로 세가지 발견적 해법들을 제시하고 수치실험을 통해 제시된 해법들의 성능비교가 수행되었다.
