A branch-and-bound algorithm for minimizing the total weighted completion time on parallel identical machines with two competing agents

摘要

Scheduling with two competing agents has drawn a lot of attention lately. However, most studies focused only on single-machine problems. In reality, there are many machines or assembly lines to process jobs. This study explores a parallel-machine scheduling problem. The objective is to minimize the total weighted completion time of jobs from agent 1 given a bound of the maximum completion time of jobs from agent 2. We develop a branch-and-bound algorithm to solve the problems with fewer jobs. In addition, we propose genetic algorithms to obtain the approximate solutions. Computational results are given to evaluate the performance of the proposed algorithms.