병렬처리기계상에서 작업의 상호교환에 의한 휴리스틱 해법의 효율성 개선에 관한 연구

Abstract

1회 가공(single operation)을 요하는 다수의 작업들이 다수의 기계 중 어느 기계를 통해서도 처리될 수 있는 상황에서 일정한 작업배정을 통하여 특정 성과척도(measure of performance)를 최소화하거나 최대화하는 경우 문제를 일정계획(scheduling)이라 한다. 일정계획분야에서 주요한 문제 중의 하나는 서로 다른 납기(due date)를 가지는 일련의 독립된 작업들(a set of independent jobs)을 일련의 병렬기계(a set parallel processors)상에서 처리할 때 최대납기지연시간(the maximum lateness)을 최소화하는 작업할당과 처리순서를 구하는 문제이다.