Algorithms for single-machine scheduling to minimize the total tardiness with learning effects and two competing agents

摘要

Scheduling with learning effects or scheduling with two competing agents has been widely studied in recent years. However, they are seldom discussed at the same time. In this article, we consider a single-machine scheduling problem with learning effects where the objective is to minimize the total tardiness of jobs from one agent, given that the maximum tardiness of jobs from the other agent cannot exceed an upper bound. We provide a branch-and-bound algorithm to search for the optimal solution and a genetic algorithm equipped with a local search to obtain near-optimal solutions. In addition, we conduct some computational experiments to investigate the solution quality and execution speed of both algorithms.