A cyclic shop is a production system that repetitively produces identical sets of jobs, called minimal part sets (MPSs), in the same loading and processing sequence. Each machine repeats identical work cycles. We investigate two versions of cyclic shops. The first version is a cyclic shop where an operation of an MPS instance can be processed prior to an operation of a previous MPS instance. We call such a shop an overtaking cyclic job shop. The overtaking degree is specified by how many MPS instances the operations of an MPS instance can overtake. More overtaking results in more work-in-progress, but reduces the cycle time, in general.
The second version is a cyclic shop where a timing constraint is imposed on an operation. When loading, transferring and unloading jobs are automated by robots or other devices, the space where jobs in progress can reside is very limited. The material handling devices are limited resources that are shared for multiple operations. Therefore, a job that completes processing at a machine may not be able to be immediately unloaded when the next waiting space is full or the material handling devices are busy. The time duration for which a job remains at a machine after processing is called the residency time. In some shops that perform kinds of chemical processes, when the residency time exceeds a specified time limit, the job may be scrapped or reworked due to quality problems. Therefore, the total time for which a job spends at a machine should not exceed the sum of the operation time and the residency time upper bound. The sum is often called a time window. A cyclic shop with time window constraints is called a time-restricted cyclic shop.
For each cyclic shop model with a given processing sequence of the operations at each machine or a sequence of robot tasks, we develop the conditions for which the shop has a qualified schedule. The qualified schedule is called a stable earliest starting schedule such that each operation or each robot task starts as soon as its preceding operations are completed and the scheduling constraints such as the overtaking of operations or the time window constraints are satisfied, the schedule repeats an identical timing pattern for each MPS, and the cycle time is kept to be minimal. To do this, we propose directed graph models, versions of event graphs, for the shop models. Then, we develop linear system models based on the minimax algebra. By analyzing the eigenvectors and eigenvalues of the linear system matrix, we prove the existence of stable earliest starting schedules and present a way of computing all such schedules. From the results, we develop a mixed integer programming model for finding a processing sequence of the operations at each machine that minimizes the cycle time.
Finally, we apply the two versions of cyclic shop models to a robotic cell that consists of several processing machines and a material handling robot with a single arm or dual arms. It can concurrently process multiple job types, has no intermediate storage between the processing machines due to space limitation, and has time window constraints at each machine. Examples include an automated electroplating line for producing printed circuit boards and a cluster tool for chemical vacuum deposition processes in wafer fabrication. For the robotic cell model, we also analyze the existence and computation of the stable earliest starting schedules and the mixed integer programming model for finding the optimal processing sequence at each machine and the optimal sequence of robot tasks.
반복생산 시스템(cyclic shop)은 여러 종류의 제품을 대량으로 생산하는 경우, 생산요구량에 부합하는 일정 비율의 제품 구성을 최소생산단위(minimal part set; MPS)로 하여 반복적으로 생산하는 제조시스템으로서 최소생산단위를 구성하는 품목들은 매 생산 주기마다 같은 순서로 투입되며, 각 장비는 매 생산주기마다 동일한 작업 순서를 반복하게 된다. 본 연구에서는 두가지 형태의 반복생산 시스템 에 대해 논한다.
첫번째 형태로, overtaking cyclic job shop, 즉, 생산단위를 구성하는 작업들이 그 이전의 생산주기에서 수행될 수 있는 것을 허용하는 형태의 반복생산 시스템에 대한 것이다. 이런 형태의 반복생산 시스템에서는 작업이 얼마나 미리 수행되었느냐에 따라서 overtaking 정도가 결정된다. 일반적으로 작업들이 미리 수행되면 될수록 이는 재공재고가 증가함을 의미하지만 시스템의 생산률은 증가하게 된다.
두번째 형태는 시간적 제약을 가지는 반복생산 시스템, 즉, time-restricted cyclic shop에 대한 것이다. 제품의 로딩, 이송, 언로딩이 로봇과 같은 물류시스템에 의해 자동으로 이루어지는 반복생산 시스템에서 물류시스템은 여러 작업들이 공유하게 되는 제한된 자원이 된다. 또한, 이와 같은 시스템에서는 공간의 제약으로 반제품 상태로 작업장 내에서 기다리는 것에 제약이 있을 수 있다. 따라서, 대기장소에 여유가 없거나 물류시스템이 다른 작업을 수행 중일 때는 가공을 마친 반제품들은 바로 언로드 될 수 없게 된다. 이때 반제품이 가공을 마친 후 장비 내에서 기다리는 시간을 잔류시간(residency time)이라 한다. 화학공정을 수행하는 작업장에서는 제품의 품질문제 때문에 잔류시간을 초과한 반제품들은 폐기되거나 재작업을 해야 하는 경우가 발생하게 된다. 공정시간과 최대 허용 잔류시간의 합을 time window라 부르며, 반제품이 장비 내에서 머무는 시간은 이 time window를 초과할 수 없다.
각 형태의 반복시스템에 대해서 모든 작업순서가 주어졌을 때, 이 작업장들이 여러 제약들(overtaking, time window constraint)을 만족하는 스케줄을 갖을 조건을 찾는다. 여기서 여러 제약들을 만족하는 stable earliest starting schedule를 stable modified earliest starting schedule라 정의하며, 이런 스케줄에서는 모든 작업들은 자신의 선행 작업이 완료되고 모든 제약이 만족되면 바로 작업이 개시 될 수 있으며 동시에 모든 MPS에서 동일한 시간 패턴을 보이고 최소의 작업주기를 갖게 된다. 이와 같은 스케줄을 찾기 위해 본 연구에서는 이벤트 그래프 형태의 그래프 모형을 개발하고 minimax 대수를 기반으로한 선형시스템모형을 제시한다. 이 선형시스템모형의 eigenvector와 eigenvalue를 분석하는 것으로 stable earliest starting schedule 또는 stable modified earliest starting schedule이 존재함을 보이고 이러한 모든 스케줄을 찾는 방법을 기술한다. 또한 이 결과를 기반으로 주기시간을 최소화하는 작업순서를 결정하는 정수계획모형을 제시한다.
마지막으로 앞에서 언급한 두가지 형태의 반복생산 시스템의 응용으로 로봇작업장에 대해 기술한다. 몇개의 공정장비들과 물류이송을 담당하는 로봇으로 구성된 로봇작업장은 다품종을 반복적으로 생산하며 공간의 제약으로 작업장내에 반제품의 대기장소가 없으며, 각 공정은 시간적 제약을 갖는다. 예를 들어, printed circuit boards의 생산을 위한 전기도금 작업장과 wafer 생산 중 진공증착을 위한 cluster tool 등이 이와 같은 형태의 작업장이라 할 수 있다. 이런 형태의 작업장을 대상으로 stable earliest starting schedule의 존재 여부와 그것을 계산하는 방법을 기술하며 이를 기반으로 각 장비에서의 작업순서와 로봇의 작업 순서를 동시에 최적화하는 정수계획모형을 제시한다.
