Single machine scheduling to minimizing sum penalty number of late jobs subject to minimize the sum weight of completion time

Abstract

This paper considers of scheduling ( ) jobs on single machine to minimize the sum penalty number of late jobs with minimum sum of weighted of completion time . To solve this lower bound and some dominance rule are derived and it is incorporated in a branch and bound (B&B) algorithm. We propose heuristic method to find near optimal solution. We also report on computational experience with the branch and bound. Also we develop compare and test different local search method (Threshold accepted (TA), Tabu search (TS) and Ant colony optimization (ACO) algorithm) for the problem. Computational experience is found that these local search algorithms solve problem to 5000 jobs with reasonable time. Keyword:- Scheduling Single machine, Bicriteria, Lexicographical optimization, Branch and bound, Local search methods