This dissertation focuses on production planning and scheduling problems in an assembly system operating on a make-to-order basis. Due dates are considered as constraints in the problems, that is, tardiness is not allowed. The assembly system considered in this study consists of several workstations each of which consists of one or more parallel machines or workers. The planning problem is to determine starting and completion periods of items, i.e., final products, subassemblies and parts, and their production quantities in each period under the constraints of due dates, precedence relationships among items, and resource limits. The scheduling problem is to determine schedules of items on parallel machines. An item can be released after a given ready time and must be completed before its due date. An item is split into multiple jobs (batches) and a job is processed on one of the parallel machines. Since the scheduling problem is a lower-level decision making than the planning problem, the scheduling problem is solved using a production plan obtained from the planning problem.
The objective of the planning problem considered here is to minimize holding costs for final product inventory as well as work-in-process inventory. A mixed integer linear programming model is presented and a heuristic algorithm is developed using a solution property and a network model for defining solutions of the problem. The suggested algorithm is shown to outperformed a commercial planning/scheduling software and backward finite-loading methods that employ various priority rules.
For the scheduling problem, two local search heuristics, simulated annealing and taboo search algorithms, are suggested for the objective of minimizing the holding costs of items including work-in-process as well as finished job inventories. Results of computational experiments showed that the simulated annealing algorithm outperformed the taboo search algorithm.
Since aggregated information is used when the planning problem is solved while more detailed information is used when the scheduling problem is solved, a feasible schedule may not be obtained from a production plan. In order to resolve this problem, we suggest two heuristic algorithms, in which an iterative approach is employed to obtain a solution that is feasible for both the planning and scheduling problems.
Finally, as a special case, we consider the assembly system with several workstations each of which consists of single machine. For this case, a mixed integer linear programming model is given and a branch and bound algorithm based on a Lagrangian relaxation method is developed. In the algorithm, a subgradient method is used for obtaining good lower bounds of subproblems (or partial solutions) while a Lagrangian heuristic is used for upper bounds. Results of computational experiments on randomly generated test problems showed that the branch and bound algorithm found optimal solutions of problems of moderate sizes in a reasonable amount of computation time.
본 논문은 주문 생산 방식을 따르는 조립 시스템에서의 생산 계획 및 스케쥴링 문제에 대해서 다룬다. 조립 시스템은 몇 개의 작업장들로 구성되며, 각 작업장에는 몇 대의 기계(혹은 몇 명의 작업자)들이 병렬로 존재한다. 본 연구에서 고려하는 생산 계획 및 스케쥴링 문제에서는 납기 지연을 허용하지 않는다. 생산 계획 문제는 각 품목(최종 제품, 반제품 및 부분품)들의 생산 시작 시점 및 생산 종료 시점을 결정하고, 각 시점별로 작업장들에서 생산하여야 할 품목들의 생산량을 결정하는 문제로 정의된다. 이 때, 최종 제품의 납기 제약, 품목들간의 선후 공정 관계 및 가용 장비의 용량적 제약은 반드시 만족하여야 한다. 스케쥴링 문제는 생산 계획보다는 하위의 의사결정 사항이므로, 생산 계획 결과가 스케쥴링 문제의 입력 정보가 된다. 스케쥴링 문제는 병렬 기계들로 구성된 각 작업장에서 처리하여야 하는 품목들의 생산 스케쥴을 결정하는 문제이다. 각 품목들은 생산 시작 가능 시간 이후에 해당 작업장에 투입되어지며 납기 전에 생산이 완료되어야 한다. 각 품목은 생산 수량에 따라 몇 개의 배치(batch)들로 나뉘어 생산되며, 하나의 배치는 작업장 내의 하나의 기계가 처리한다.
본 논문에서 다루는 생산 계획 문제의 목적 함수는 최종 제품 및 반제품, 부분품들의 재고유지 비용의 합을 최소화하는 것이다. 생산 계획 문제를 해결하기 위하여, 본 연구에서는 먼저 정수 계획 문제로 생산 계획 문제를 수리 모형화하고, 이 수리 모형으로부터 도출한 해의 특성과 네트워크 모형을 이용하여 휴리스틱 알고리즘을 개발하였다. 계산 실험 결과, 제안한 알고리즘은 생산 계획을 위한 상업용 소프트웨어와 다양한 우선순위 결정법을 이용하는 후진 기법들보다도 더 좋은 결과를 주는 것으로 판명되었다.
본 연구에서 다루는 스케쥴링 문제의 목적 함수는 품목들의 재고 유지 비용을 최소화하는 것이며, 이 문제를 해결하기 위해서 시뮬레이티드 어닐링(simulated annealing) 기법과 타부 탐색(taboo search) 기법을 제안하였다. 계산 실험 결과 시뮬레이티드 어닐링 기법이 타부 탐색 기법보다 더 나은 해를 제공하는 것으로 판명되었다.
생산 계획 문제가 축약된 정보를 사용하는 반면, 스케쥴링 문제는 상세한 정보를 사용하기 때문에, 생산 계획 결과를 모두 만족하는 스케쥴을 수립하는 것이 때론 불가능할 경우가 있다. 이러한 문제점을 해결하여, 생산 계획 및 이를 바탕으로 한 스케쥴이 모두 실현 가능할 수 있도록 본 연구에서는 반복적 기법을 이용한 두개의 휴리스틱 알고리즘을 제안하였다.
본 연구에서는 또한 각 작업장이 한대의 기계(혹은 한명의 작업자)로만 구성되어 있을 경우에 대해서도 다루었다. 이러한 상황에서의 생산 계획 및 스케쥴링 문제를 해결하기 위하여, 본 연구에서는 먼저 이산형 변수가 포함된 선형 수리 모형을 제시하고, 최적 해를 제공할 수 있는 분지한계(branch and bound) 알고리즘을 제안하였다. 이 분지한계 알고리즘에서는 해의 좋은 하한 값과 상한 값들을 구하기 위하여 각각 라그랑지안 완화 기법(Lagrangian relaxation method) 및 라그랑지안 휴리스틱 알고리즘을 사용한다. 계산 실험 결과, 제안한 분지한계 알고리즘은 적절한 크기의 문제들의 최적 해를 길지 않은 시간 내에 구할 수 있는 것으로 판명되었다.
