The Hoist Scheduling Problem (HSP) is directly related to the management of chemical processing lines, also known as electro-plating lines, such as those that can be found in the PCB industry for instance. Such lines are composed of several tanks containing the chemicals, a rail that runs above the tanks and multiple hoists, moving on the mentioned rail, that must carry jobs from tank to tank. Jobs must go through the line according to a given production sequence (also called a routing). All jobs do not necessarily have the same production sequence. A production sequence gives not only the tanks sequence, but also the treatment times (as an interval). The problem is to appropriately schedule the tanks and hoists to minimize the number of defective jobs while maximizing the throughput. This thesis proposes a layered system for solving the HSP as three sub-problems, namely the Input Date Decision Problem (IDDP), the Hoists Assignment Problem (HAP) and the Hoists Conflict Resolution Problem (HCRP) . Each layer uses multiple agents with mixed cooperative and competitive behaviors. Agents represent resources such as the tanks or the hoists.
The first layer is concerned with the resolution of the IDDP for new jobs. The second layer is concerned with the assignment of transfer operations to hoists. The third and last layer is designed to ensure the integrity of the line by providing mechanisms to resolve remaining conflicts between physical entities of the production line.
The first layer is based on a democratic algorithm (DA), which is a contribution of this thesis, that is used as a method for cooperative decision-making. This democratic algorithm is based on a repetitive process “proposal-making → vote ”. These two steps are described and a few instances of the DA are suggested. Since no predictive scheduling of the allocations of hoists to transfer operation, or tanks to processing operations, is performed, the representation of the tanks occupation as well as that of the hoists must reflect the uncertainty inherent to the resolution mechanism. A representation mechanism based on possibility distributions is proposed that can be parameterized to reflect various policies.
The second layer uses a contract net based system to decide on the allocation of hoists to transfer operations. Although based on auctions, and thus competition, the proposed system is not purely competitive as mechanisms are included for bid adjustments based on priori conflict evaluation. Bids are calculated as an evaluation of the remaining flexibility in the schedule of the considered hoist when accepting the currently auctioned transfer operation. The system is shown to have better performance than commonly used heuristics such as the NRF (Nearest Robot First), the ARA (Average Robot Assignment) or the BSJL (Boundary Shift by Job Location) heuristic dispatching rules.
The third layer is constructed as a last layer above the physical system for resolving remaining conflicting situations. It is based on self-assigned priorities. Basic priority classes are designed and the priorities assignment is discussed for each of these classes. Also discussed are the consequences of some of the assignment models with respect to some of the rules usually applied in conventional resolution systems.
Whenever possible numerical examples of application are given and the results are compared to other published results.
호이스트 스케쥴링 문제는 PCS 전자회로 기판과 같은 공장 자동화 라인에서의 로봇 스케쥴링 문제를 그 이슈로 한다. 공장 자동화 라인은 크게 화학약품이나 회로부품을 저장하고 있는 탱크, 이를 운반하는 호이스트, 그리고 호이스트가 움직이는 레일, 이렇게 3가지의 구성요소를 가진다. 이러한 시스템의 궁극적인 목적은 주어진 작업 시퀀스에 따라서 가장 효율적인 호이스트들의 스케쥴을 최적화하는 것이다. 보다 세부적으로는 탱크와 호이스트들에게 효과적인 작업 시간과 순서를 할당함으로써 최대 생산성을 산출하는 것으로 볼 수 있다.
본 논문에서는 이와 같은 스케쥴링 문제는 다중 에이전트를 이용한 협력을 이용한 계층적 해결 방안을 제시한다. 제안하는 계층적 시스템은 입력 시간 결정을 위한 IDDP(Input Date Decision Problem), 호이스트간 충동 방지를 위한 HCRP(Hoists Conflict Resolution Problem), 호이스트 할당을 위한 HAP(Hoist Assignment Problem)의 세가지 부분으로 구성된다. 각 계층은 에이전트간 협약과 협력의 과정으로 모델링된다.
