Branch and bound method to solve multiple objective function

Abstract EN

This paper presents a branch and bound algorithm for sequencing a set of jobs on a single machine scheduling with the objective of minimizing total cost of flow time and maximum earliness, when the jobs may have unequal ready time.

For solving this problem we proposed two lower bounds (LB1, LB2) by decomposing the problem into two subproblems.

The lower bounds of the problem is the sum of the lower bounds of two subproblems.

The proposed heuristic algorithm, which is used as an upper bound in the branch and bound (BAB) algorithm, is effective in finding an optimal or near optimal schedule.

Also, we prove some special cases of the problem which lead to optimal solution.

We stated and proved three dominance rules.

Results of extensive computational tests show the proposed (BAB) algorithm is effective in solving problems up to about (50) jobs at a time less than or equal to (30) minutes.