This dissertation focuses on system setup and scheduling problems with the overall objective of meeting due dates in flexible manufacturing systems (FMSs). In general, the system setup problem is concerned with decisions that have to be made before the FMS begins to produce parts, while the scheduling problem is concerned with running the FMS once it has been setup. In this dissertation, we consider multi-period order selection and loading problems for system setup, and a scheduling problem that results from these system setup problems, since other operational problems could be considered to be less critical than these problems. In general, system setup and scheduling problems are considered to be very critical, and hence solutions of these problem can play an important role in the operation of FMSs.
The multi-period order selection problem is the problem of selecting orders to be produced in each period during the upcoming planning horizon with the objective of minimizing earliness and tardiness costs and subcontracting costs. The earliness and tardiness costs are incurred if an order is not finished on time, while subcontracting cost is incurred if an order is not selected within the planning horizon (and must be subcontracted) due to processing time capacity or tool magazine capacity. This problem is formulated as a 0-1 integer program which can be transformed into a generalized assignment problem. To solve the order selection problem, a heuristic algorithm is developed using a Lagrangian relaxation technique, and effectiveness of the algorithm is tested on randomly generated problems.
The FMS loading problem is the problem of allocating operations and associated cutting tools to machines for a given set of selected parts (orders). There may be different environments for the loading problem that result from three ways of grouping machines in an FMS, i.e., no grouping, partial grouping, and total grouping. In this dissertation, we focus on the loading problem resulting from partial grouping, in which each machine is tooled differently but each operation can be processed by one or more machines. Two types of heuristic algorithms are suggested for the loading problem with the objective of balancing workloads, i.e., minimizing the maximum workload of the machines. In addition, we show through simulation experiments that loading plans from partial grouping give significantly better performance than those from total grouping.
There is a strong interdependence between the multi-period order selection and loading problems. That is, if the two problems are considered separately and sequentially, a solution of the multi-period order selection problem may make the resulting loading problem infeasible. To avoid such infeasibility, the multi-period order selection problem should be solved in such a way that resulting loading problems may be feasible. In this dissertation, four iterative procedures are developed and compared with each other. In these procedures, the two algorithms given above are used for the multi-period order selection and loading problems, respectively.
Finally, a scheduling problem that results from the loading problems is considered. Unlike most previous studies, this study deals with the scheduling problem resulting from a loading plan obtained for the configuration of partial machine grouping. Planned workload of each machine specified by the loading plan may or may not be maintained when scheduling and controlling part flows. Two solution algorithms in which a given planned workload is maintained are suggested based on decomposition of the entire problem into route selection and jobshop scheduling problems. In one algorithm, the two subproblems are solved simultaneously by employing rules for part selection and rules for machine selection, while in the other they are solved using a simulated annealing algorithm and dispatching rules. Also, we show through computational experiments that it is better to maintain planned workloads.
본 논문에서는 유연 제조 시스템(flexible manufacturing system)에서의 주요한 의사결정 문제인 시스템 셋업(system setup) 및 일정 계획(scheduling) 문제를 납기 만족 및 외주 비용의 최소화라는 목적 함수하에 다루고 있다. 유연 제조 시스템에서의 시스템 셋업 문제란 시스템이 가공품을 가공하기 전에 결정해야 할 문제로 다기간 오더 선택 문제(multi-period order selection problem) 및 작업 할당 문제(loading problem)를 본 논문에서는 다루고 있다. 여기서, 다기간 오더 선택 문제란 주어진 계획 기간(planning horizon) 내의 각 기간(period)에서 어떤 오더를 선택하여 생산할 것인가를 결정하는 문제를 말하며 작업 할당 문제란 각 가공품의 생산에 필요한 오퍼레이션 및 공구들을 기계에 어떻게 할당할 것인가를 결정하는 문제를 말한다. 그리고, 일정 계획 문제란 시스템의 가동 시 내려야 할 의사결정 문제로 하나의 오퍼레이션이 두 개 이상의 기계에서 가공이 가능할 때 발생하는 기계 선택 문제 및 오퍼레이션들의 가공 순서를 결정하는 문제를 말한다.
먼저, 2 장에서는 시스템 셋업 문제 중 다기간 오더 선택 문제를 다루고 있다. 목적 함수는 납기에 이전에 생산했을 때 발생하는 비용(earliness costs) 및 납기 지연 비용(tardiness costs)과 외주 비용(subcontracting costs)의 합을 최소화하는 것으로 두었다. 본 연구에서는 이 문제를 먼저 0-1 정수 계획(integer programming) 문제를 이용한 수리 모형을 만들었고 이를 기존의 일반 할당 문제(generalized assignment problem)로 변형시킨 후 라그랑지안 완화(Lagrangian relaxation) 기법을 이용한 알고리듬을 제안하였다. 이 알고리듬의 성능을 평가하기 위하여 계산 실험을 실시하였으며 그 결과 본 논문에서 제안하는 알고리듬이 적절한 시간 내에 효과적인 해를 줄 수 있음을 보였다.
다음으로, 3 장에서는 작업 할당 문제의 환경을 형성하는 여러 가지 기계 집합화(machine grouping) 형태 중 부분적 집합화(partial grouping) 하에서의 작업 할당 문제를 작업 부하의 균등화(workload balancing)라는 목적 함수하에서 다루고 있다. 여기서, 부분적 집합화란 각각의 기계에는 다른 공구들이 장착되나 하나의 오퍼레이션이 한 개 이상의 기계에서 가공이 가능하도록 작업을 할당하는 형태를 말한다. 본 논문에서는 이 문제에 대하여 여러 가지 알고리듬들을 제안하고 있으며 제안된 알고리듬의 성능이 기존의 연구에서 제시된 알고리듬보다 우수함을 계산 실험을 통하여 보였다. 또한, 대부분의 기존 연구에서 적용한 기계 집합화 형태인 완전 집합화(total grouping) - 전체 기계들을 기계 집합(machine group)으로 구분하고 각 기계 집합 내의 기계는 동일한 공구들이 장착되어 형태의 집합화 - 와의 비교를 위한 시뮬레이션 실험에서 본 논문에서 제시하는 알고리듬이 기존의 완전 집합화 형태하의 알고리듬들보다 우수한 성능을 줌을 보였다.
일반적으로, 다기간 오더 선택 문제와 작업 부하 할당 문제와는 서로 밀접한 관련이 있다. 즉, 이 두 문제를 독립적으로 고려하는 경우 다기간 오더 선택 문제의 해가 작업 부하 할당 문제에 이용될 때 작업 부하 할당 문제가 비가능(infeasible) 해질 수 있다. 따라서, 이 두 문제를 동시에 해결해야 할 필요가 발생되며 이에 본 논문의 4 장에서는 이 두 문제를 동시에 해결할 있는 반복적인 문제 해결 절차(iterative procedure)들을 제안하고 있다. 이 해결 절차들은 앞의 2 장과 3 장에서 제안한 각 하부 문제별 해결 절차를 이용하고 있으며 이 장에서는 이 두 해결 절차를 어떻게 체계적으로 결합할 것인가가 주요한 초점이 된다. 그리고, 제안된 문제 해결 절차들을 비교하기 위하여 계산 실험을 수행하였으며 그 결과 bisection search 기법에 기반한 반복적 알고리듬이 우수한 성능의 해를 줌을 보였다.
마지막으로, 5 장에서는 앞의 두 가지 시스템 셋업 문제를 해결한 후 발생하는 일정 계획 문제를 다루고 있다. 본 논문에서 다루고 있는 유연 제조 시스템 일정 계획 문제는 기존의 연구와는 달리 작업 할당 계획(loading plan)이 주어진 경우의 문제이다. 즉, 작업 할당 계획에 의해 결정된 기계별 작업 부하를 유지하도록 일정 계획을 수립하는 것이다. 본 연구에서는 먼저 전체 문제를 경로 선택 문제(route selection problem)와 개별 공정 일정 계획 문제(jobshop scheduling problem)로 나눈 후 두 가지 형태의 알고리듬 - 우선 순위 일정 계획 알고리듬(priority scheduling algorithms) 및 복합 알고리듬(hybrid algorithms) - 을 제시하였다. 첫번째 형태의 알고리듬들은 앞의 두 하위 문제를 기계 선택 규칙(machine selection rule) 및 가공품 선택 규칙(part selection rule)을 이용하여 동시에 해결하는 방법이며 두 번째 형태의 알고리듬들은 두 하위 문제를 시뮬레이티드 어닐링(simulated annealing) 알고리듬 및 가공품 선택 규칙을 이용하여 반복적으로 해결하는 방법이다. 제시한 알고리듬들의 비교를 위하여 계산 실험을 수행하였으며 그 결과 복합 알고리듬들이 간단한 우선순위규칙을 이용하는 우선 순위 일정 계획 알고리듬들보다 우수한 해를 주었다. 또한, 추가적인 실험을 통하여 작업 할당 문제에 의해 결정된 기계 별 작업부하가 유지되도록 하는 것이 그렇지 않은 경우보다 우수함을 알 수 있었다.