Algorithms for a two-agent single machine scheduling problem to minimize weighted number of tardy jobs

Abstract

This paper considers a two-agent single machine scheduling problem, with a weighted number of tardy jobs as objectives. Each agent has a finite set of jobs to be processed on a single machine. Parameters like the processing time, the due date, and the weight of jobs are known in advance. The objective is to minimize the weighted number of tardy jobs of the first agent, subject to the upper bound of the weighted number of tardy jobs of the second agent. Two metaheuristics based on Particle Swarm Optimization and Tabu Search are introduced to solve this problem. To establish the performance of the proposed meta-heuristics, a dynamic programming based exact algorithm is developed. To test the validity of the proposed algorithm, a numerical experiment is performed on randomly generated problem instances to compare the performance of the proposed algorithms.

Subject Classification:

• Primary: 90B35
• Secondary 90C25

Keywords:

• Two-agent scheduling
• Weighted number of tardy jobs
• Particle swarm optimization
• Tabu search