Two-agent single-machine scheduling to minimize the weighted sum of the agents’ objective functions

• We study a two-agent single-machine multi-objective scheduling problem.
• The backward branch-and-bound algorithm can solve problems of up to 40 jobs.
• The genetic algorithm with initial sequences has the best performance.

Scheduling with two competing agents on a single machine has become a popular research topic in recent years. Most research focuses on minimizing the objective function of one agent, subject to the objective function of the other agent does not exceed a given limit. In this paper we adopt a weighted combination approach to treat the two-agent single-machine scheduling problem. The objective that we seek to minimize is the weighted sum of the total completion time of the jobs of one agent and the total tardiness of the jobs of the other agent. We provide two branch-and-bound algorithms to solve the problem. In addition, we present a simulated annealing and two genetic algorithms to obtain near-optimal solutions. We report the results of the computational experiments conducted to test the performance of the proposed algorithms.