Single machine problem with multi-rate-modifying activities under a time-dependent deterioration

The single machine scheduling problem with multi-rate-modifying activities under a time-dependent deterioration to minimize makespan is studied. after examining the characteristics of the problem,a number of properties and a lower bound are proposed. a branch and bound algorithm and a heuristic algorithm are used in the solution,and two special cases are also examined. the computational experiments show that,for the situation with a rate-modifying activity,the proposed branch and bound algorithm can solve situations with 50 jobs within a reasonable time,and the heuristic algorithm can obtain the near-optimal solution with an error percentage less than 0.053 in a very short time. in situations with multi-rate-modifying activities,the proposed branch and bound algorithm can solve the case with 15 jobs within a reasonable time,and the heuristic algorithm can obtain the near-optimal with an error percentage less than 0.070 in a very short time. the branch and bound algorithm and the heuristic algorithm are both shown to be efficient and effective. © 2013 m. huang et al.