Minimizing total weighted completion time under makespan constraint for two-agent scheduling with job-dependent aging effects

• Two-agent single-machine scheduling with linear job-dependent position-based aging effects.
• Branch-and-bound algorithm with properties for dominance and feasibility.
• Efficient simulated annealing using three different methods to generate the initial solution.
• The superiority of the suggested algorithms using a numerical experiment.
• Consistent and relatively outstanding performance for larger systems.

In this paper, we consider a two-agent single-machine scheduling problem with linear position-based aging effects and job-dependent aging ratios. The objective is to minimize the total weighted completion time of all jobs for two agents, where the makespan for one agent is constrained under an upper bound. After showing that this problem is at least NP-hard, we develop two solution algorithms: First, we devise a branch-and-bound algorithm to find an optimal solution through the establishment of several dominance and feasibility properties, and a lower bound. Second, we propose efficient simulated annealing algorithms, using three different methods to generate an initial solution. Through a numerical experiment, we demonstrate that the suggested algorithms can be applied to efficiently find near-optimal solutions within a reasonable amount of CPU time. In particular, we show that the initial solution method (arranging the jobs for one agent in non-increasing order of aging ratio, and scheduling the jobs for the other in the weighted shortest normal processing time order) is superior to others. Moreover, through scalability testing, we verify its consistent and relatively outstanding performance for larger systems with many processing jobs.