Multitasking scheduling problems with two competitive agents

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.