In this thesis, four flowshop scheduling problems in which no queues are allowed at any intermediate machine are considered. Firstly, a problem in which jobs have sequence dependent setup times only at the first machine is treated. The objective is to minimize the weighted mean flow time. A branch-and-bound method is derived by exploiting lower bounds and a dominance property. Secondly, a problem in which jobs have non-separable and sequence dependent setup times at all machines is considered. A dynamic programming algorithm is provided for the objective of minimizing the makespan. Thirdly, for the case of cyclic production, a problem in which jobs have sequence dependent setup times only at the first machine is discussed. The objective is to minimize cycle time. Lastly, a problem which is similar to the third problem but has an additional restriction is investigated. The restriction is that for a sequence of consecutive batches of jobs, the first job of a succeeding batch can start its processing only after its preceding batch of jobs all completed. For the problem, the objective is to minimize the makespan and it is shown that the optimal solution can be found in traveling salesman problem soving approach. Numerical examples are presented for all the corresponding algorithm illustrations.
본 논문은 공정간 대기가 허락되지 않는 연속공정작업들의 일정계획에 관한 문제 네가지를 다룬다.
첫번째, 작업들이 첫번째 기계에만 작업순서에 따라 다른 준비시간을 갖는 경우에 가중평균 가공 시간(Weighted Mean Flow Time)을 최소로 하는 일정계획 문제이다. 이 문제에 대하여 분지한계기법을 제시하였다. 두번째, 모든 기계에 분리될 수 없고 작업순서에 따라 다른 준비시간을 갖는 경우에 총 완성시간(Makespan)을 최소로 하는 동적계획법이 제시 되었다. 세번째, 순환 생산인 경우에 첫번째 기계에만 작업순서에 따라 작업순서에 따라 다른 준비시간을 갖는 경우에 주기(Cycle Time)를 최소로 하는것이 목적이다. 최적해는 순회 판매원 문제를 푸는 접근 방식으로 구할수 있다. 마지막으로, 세번째 문제에 한가지 제약이 첨부된 문제를 고려한다. 그 제약은 다음과 같다. 선행하는 배치(Batch)의 작업이 완전히 끝났을 때 연속적으로 뒷따라오는 배치의 첫번째 작업이 시작될 수 있다. 총 완성 시간(Makespan)을 최소로 하는것이 목적이고, 최적해는 순해 판매원 문제를 푸는 접근 방식으로 구할 수 있다. 알고리즘을 설명하기 위해 각각의 예제들이 주어져 있다.
