Group scheduling for complex products with time-dependent deteriorating effect

Deteriorating effect is critical for the processing time of a job in group scheduling for complex products, which is caused by the maintenance or repairing of machines. In this paper, we construct a time-dependent deteriorating effect model for the single-machine group scheduling problem with makespan minimization. The problem is proved to be NP-hard in strong sense. A fast makespan calculating method is derived from the analysis on properties for the considered problem. Based on a special grouping strategy, a heuristic and an enumerative method are proposed. The proposed algorithms are compared on a lot of small size instances, along with the statistical analysis on the experimental results by the Analysis of Variance.