Multitasking scheduling problems with two competitive agents

Abstract

This article addresses several two-agent scheduling problems in the presence of multitasking. Under multitasking, when a task is being executed, it is inevitably interrupted by the tasks that have not been finished, and the interruption time is proportional to the remaining processing time of the interrupting task. Each agent desires to minimize a certain cost function that depends only on its own tasks' completion times. Different cost functions are considered for both agents, including the maximum of regular cost, total completion time, and (weighted) number of tardy tasks. The purpose is to determine a feasible solution for all tasks of the two agents that minimizes the cost value of the first agent while maintaining the cost value of the other agent, not exceeding a given threshold value. Polynomial and pseudo-polynomial time algorithms are proposed to solve the setting, involving various combinations of cost functions.

Keywords:

• multitasking
• optimization
• scheduling
• two-agent algorithms

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Shi-Sheng Li http://orcid.org/0000-0003-3197-1558

Additional information

Funding

This work was supported by the National Natural Science Foundation of China [grant number 11701595], the Key Research Projects of Henan Higher Education Institutions [grant number 20A110037], and the Young Backbone Teachers training programme of Zhongyuan University of Technology.