첫단계에 이종병렬기계가 배치된 2단계 혼합흐름생산시스템의 일정계획

A Heuristic Schedule for a Two-Stage Hybrid Flowshop with Nonidentical Parallel Machines at the First Stage

본 논문에서는 첫 번째깨 작업장에 두 대의 이종병렬기계가 배치되고 최종단계인 두 번째 작업장에 단일기계가 배치된 2단계 홉합흐름생산시스템의 총완료시간을 최소화하는 일정계획 문제를 다룬다. 이러한 일정계획 문제는 총완료시간을 최소화하기 위하여 각 기계에의 작업할당 방법과 작업 처리순서를 결정하는 문제이다. 본 논문에서는 작업할당이 주어지면 Johnson의 규칙을 이용하여 작업처리순서를 결정하고, 작업처리순서가 주어지면 각 기계에서의 작업처리시간을 비교하여 하나의 작업을 선택하여 다른 이종병렬기계로 이동하는 새로운 작업할당을 하여 초기 일정계획으로부터 개선된 일정계획을 반복적으로 찾아가는 일종의 개선 알고리즘을 제안하였다. 수치 예제를 통하여 제안 알고리즘의 과정을 자세히 설명하였으며, 모의실험을 통하여 제안 알고리즘의 성취도를 현재까지 가장 좋은 것으로 알려진 알고리즘의 성취도와 비교하였다. 또한 여러 가지 하한들을 이용하여 제안 알고리즘의 성과를 비교하였다. 제안 알고리즘은 작업 처리시간이 랜덤하게 생성된 모의실험 문제들을 대상으로 우수한 성과를 나타내는 것을 보여주었다.

This paper deals with the problem of scheduling a two-stage hybrid flowshop with nonidentical parallel machines. The objective is to minimize the makespan for the problem that consists of two nonidentical machines at the first stage and a single machine at the second stage. The decision variables for the problem are the allocation of jobs for each machine and the determination of the sequence of jobs. This paper presents a heuristic algorithm which employs a sequencing rule based on the sequence obtained by applying Johnson's rule. The proposed algorithm is an improvement algorithm that tries to find a better solution from a given schedule. An example is also given to illustrate the solution procedure. The performance of the proposed algorithm is evaluated by comparing with that of the existing algorithm and the easily computable lower bounds. The proposed algorithm has been shown to perform significantly better than the existing algorithm for most bench mark problems.