The purpose of this study is to develop an efficient exact algorithm for the problem of scheduling n independent jobs on m unequal parallel processors to minimize makespan. Efficient solutions are already known for the preemptive case. But for the non-preemptive case, this problem belongs to a set of strong NP-complete problems. Hence, it is unlikely that the polynomial time algorithm can be found. That is the reason why most investigations have been directed toward the fast approximate algorithms and the worst-case analysis of algorithms. Recently, great advances have been made in mathematical theories regarding Lagrangean relaxation and the subgradient optimization procedure which updates the Lagrangean multipliers. By combining these mathematical tools with branch-and-bound procedures, there have been some successes in constructing pseudo-polynomial time algorithms for solving previously unsolved NP-complete problems. This study applies similar methodologies to the unequal parallel processor problem to find the efficient exact algorithm. [In Korean].
