Scheduling with competing agents, total late work and job rejection

We study a single-machine scheduling problem with two competing agents. The objective function of one agent is minimizing total late work, whereas the maximum cost of the jobs of the second agent cannot exceed a given upper bound. We introduce and test a pseudo-polynomial dynamic programming algorithm for this NP-hard problem. Our tests indicate that the algorithm can handle large-size instances (containing hundreds of jobs) fairly quickly. We then extend the setting to that of job rejection, where the scheduler may decide to process only a subset of the jobs. The dynamic programming algorithm is modified accordingly, and our numerical tests verify that medium-size instances (containing less than 100 jobs) are solved in reasonable time.

Automated summary

This study examines a single-machine scheduling problem involving two competing agents, with a focus on minimizing total late work and limiting job costs within a specified upper bound. An innovative pseudo-polynomial dynamic programming algorithm is introduced and tested on large-size instances, proving its effectiveness. The research also extends to job rejection scenarios, with modifications made to the algorithm for solving medium-size instances efficiently.