In this thesis, the dominance relations among several lower and upper bounds are represented clearly by schedule graphs. An existing decomposition rule is computationally experimented. Based on the observation, blockwise heuristics are devised to improve the efficiency of branch and bound algorithm for large problems. Finally, we show that a branch and bound algorithm may be improved by excluding some of the popular precedence conditions and incorporating a dominance property between nodes."
본 논문은 각 작업에 작업중요도에 따른 가중치와 납기가 주어졌을 때, 납기를 준수하면서 총가중완성시간을 최소화하는 단일기계의 일정계획에 관한 연구이다. 이 문제는 NP-complete임이 증명되었는 바, 대부분의 연구들은 분지한계법하에서 하한의 개선과 우선조건의 발견에 집중되어왔다.
본 논문에서는 여러 하한 및 상한들간의 우월관계를 그래프를 이용하여 명확하게 표현하였다. 그리고 기존의 분해규칙의 실제적 유효성에 대한 실험을 하였으며, 그 결과를 기초로 대규모 문제에서 분지한계법의 효율성을 제고할 수 있는 blockwise heuristic을 고안하였다. 마지막으로 분지한계법에 이용되는 우선조건들중에 비효과적인 것들을 제거하고, 마디(node)간 우월조건을 효율적으로 구현함으로써 분지한계법의 효율성이 향상됨을 보이고 있다.
