Multitasking scheduling problems with two competitive agents. Issue 11 (1st November 2020)

• Record Type: Journal Article
• Authors: Li, Shi-Sheng; Chen, Ren-Xia; Tian, Ji
• Is Part Of: Engineering optimization. Volume 52:Issue 11(2020)
• Page Start: 1940
• Page End: 1956
• Publication Date: 2020-11-01
• Subjects: multitasking -- optimization -- scheduling -- two-agent algorithms; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2019.1678609
• Languages: English
• ISSNs: 0305-215X

Abstract

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.