Branch and Bound Method to Solve Multiple Objective Function


Abstract:This paper presents a branch and bound algorithm for sequencing a set of jobs on a single machinescheduling with the objective of minimizing total cost of flow time and maximum earliness, when the jobsmay have unequal ready time.For solving this problem we proposed two lower bounds (LB1, LB2) by decomposing the problem intotwo subproblems. The lower bounds of the problem is the sum of the lower bounds of two subproblems. Theproposed heuristic algorithm, which is used as an upper bound in the branch and bound (BAB) algorithm, iseffective in finding an optimal or near optimal schedule. Also, we prove some special cases of the problemwhich lead to optimal solution. We stated and proved three dominance rules. Results of extensivecomputational tests show the proposed (BAB) algorithm is effective in solving problems up to about (50) jobsat a time less than or equal to (30) minutes.