This thesis considers a fixed cycle scheduling problem with periodically-arriving batches of partially-precedent tasks, where a constant number of parallel machines are available during a fixed cycle and each batch(job) can be completed on any machine by processing its including tasks. Under the assumption that each task requires unit period of processing time, the sum of delay time of all the arrived jobs is to be minimized. In the problem analysis, some solution properties for several types of precedence structures between tasks are characterized. These properties are then used to develop heuristic algorithms and a branch-and-bound algorithm.
본 논문에서는 기간별로 계속되는 묶음단위의 수요를 충족시키기 위한 부분 선행관계가 있는 과제집단의 일정계획을 다루고 있다. 연구 목적은 한 주기내의 모든 수요를 만족시키면서 발생하게되는 모든 묶음작업들의 총 지연시간을 최소화하는 것이다.
각 작업들의 수행시간은 단위기간이고 작업수행기계의 동일형태 작업의 수행능력은 제한이 없는 것으로 가정되었다.
선행관계가 모든 작업들에 있는 경우와 그렇지 않은 경우에 대해 각각 최적해에 대한 분석과 해를 구하는 발견적 방법들이 제시되었다. 또한, 선행 관계의 구조가 나무구조인 경우와 그렇지 않은 경우에 대한 분석도 이루어졌다.
본 논문에서 제시한 방법들은 교육기관에서의 과목들에 대한 일정계획이나, 기타 이와 유사한 문제 환경에서의 일정계획에 간단히 효과적으로 사용 될 수 있다.
