Integrating Group Setup Time Deterioration Effects and Job Processing Time Learning Effects with Group Technology in Single-Machine Green Scheduling

Abstract

We study single-machine group green scheduling considering group setup time deterioration effects and job-processing time learning effects, where the setup time of a group is a general deterioration function on its starting setup time and the processing time of a job is a non-increasing function on its position. We focus on confirming the job schedule for each group and group schedule for minimizing the total weighted completion time. It is proved that this problem is NP-hard. According to the problem’s NP-hardness, we present some optimal properties (including lower and upper bounds) and then propose a branch-and-bound algorithm and two heuristic algorithms (including the modified Nawaz–Enscore–Ham algorithm and simulated annealing algorithm). Finally, numerical simulations are provided to indicate the effectiveness of these algorithms, which demonstrates that the branch-and-bound algorithm can solve random instances of 100 jobs and 14 groups within reasonable time and that simulated annealing is more accurate than the modified Nawaz–Enscore–Ham algorithm.