We consider a two-stage hybrid flowshop scheduling problem with a production ratio constraint in the presence of dynamic job arrivals. The first stage is composed of parallel identical machines and there is a single batch processing machine in the second stage. Also, at the batch processing machine product ratio of product types should be satisfied in order to maintain a required yield rate. The batch processing machine can process multiple jobs up to its capacity simultaneously and the processing time is determined by the longest processing time job in the batch. Since it is very difficult to obtain optimal solution for the problem considered in this study in a reasonable amount of time., we present heuristic algorithms for the problem with the objective of minimizing makespan. A forward approach and a backward approach are proposed along with a few scheduling rules employed in each approach, and these are evaluated with a series of computational experiments on randomly generated test problems. The result shows that the heuristics suggested in the study work better than algorithms used in practice.
본 논문은 제품이 다이나믹 하게 도착하는 상황에서 제품별 구성의 비율을 고려하는 혼합 병렬 흐름에서 최종 가공 시간을 최소화 하는 일정 계획을 구하는 것이다. 공정의 첫번째 작업장은 동일한 병렬 기계로 구성되어 있으면, 두번째 작업장은 단일 배치 기계가 있다. 가공에서 적절한 수유을 얻기 위해서 배치는 제품별로 일정한 비율을 만족해야 한다. 배치는 여러 개의 제품을 동시에 작업하므로 배치의 가공시간은 배치에 포함된 작업들 중 가장 가공 시간이 긴 제품에 의해 결정된다. 이러한 문제에 대해 적절한 시간 이내에 최적해를 구하는 것이 어려우므로 휴리스틱 방법들을 제안하여 최소의 최종 가공 시간을 구한다. 포워드 접근법과 백워드 접근법이 제안되었고, 이를 무작위적으로 발생시킨 문제를 사용하여 테스트 하였다. 실험결과 본 연구에서 제안한 알고리듬이 실제로 사용되는 알고리듬보다 좋은 결과를 보여 주었다.
