This thesis describes a no-wait in-process job shop sequencing problem(NWP). We relax the assumption that infinite intermediates storage exists which can hold all the partially processed jobs when these jobs cannot be further processed because the subsequent machines are busy.
We illustrate this problem with the establishment of the military movement plans. The convoy column is regarded as a job and the junction where more than two convoy columns meet one another is thought of as a machine. The problem is to find an ordering of convoy columns which minimizes the total time to complete marching through all the junctions.
The NWP is formulated as an integer linear problem with either-or constraints. Using order relations, the NWP can be transformed into the problem of finding the transitive tournament with the minimum weight. The transitive tournament is defined as a complete asymmetric digraph.
We suggest a branch and bound algorithm of constructing an optimal solution. Computational results show that a good solution can almost always be obtained in a reasonable time. The military movement plans can be established successfully in terms of the NWP.
본 논문은 공정간 무대기특성(in-process no-wait)을 갖는 문제를 다룬다. 공정간 무대기특성 문제는 한 기계(machine)에서 처리된 작업(job)이 다음 기계로 이행할 때 기계와 기계사이에 저장공간이 없어서 대기행렬이 허용되지 않는다 는 특성을 가지고 있다. 이 문제에서는 일단 처리되기 시작한 작업은 멈추지 않고 계속 흘러가야 하며 이러한 연속성을 보장하기 위하여 대기해야 한다면 최초의 처리가 시작되기 전에만 대기가 가능하다. 이런 종류의 문제는 군 이동계획수립문제에서 발견될 수 있는데, 이동부대는 작업대상으로, 부대가 서로 만나는 교차지점은 기계로 고려하면 된다.
공정간 무대기문제는 이동순서를 나타내는 변수(decision variable)를 도입하여 정수계획문제로 나타낼 수 있다. 이동순서를 네트워크(network)의 순서관계(order relation)에 의하여 해석하면 transivity를 갖는 토너먼트 (tournament)와 동등하다.
이 문제는 분지한계법(branch and bound procedure)을 이용하여 최적해를 구한다. 시험용으로 산출한 문제크기에 대한 계산시간은 본 논문의 해법이 비교적 빠른 시간내에 최적해를 구할 수 있다는 것을 보여 준다.
