Online Task Assignment with Controllable Processing Time

Online Task Assignment with Controllable Processing Time

Ruoyu Wu, Wei Bao, Liming Ge

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 5466-5474. https://doi.org/10.24963/ijcai.2023/607

We study a new online assignment problem, called the Online Task Assignment with Controllable Processing Time. In a bipartite graph, a set of online vertices (tasks) should be assigned to a set of offline vertices (machines) under the known adversarial distribution (KAD) assumption. We are the first to study controllable processing time in this scenario: There are multiple processing levels for each task and higher level brings larger utility but also larger processing delay. A machine can reject an assignment at the cost of a rejection penalty, taken from a pre-determined rejection budget. Different processing levels cause different penalties. We propose the Online Machine and Level Assignment (OMLA) Algorithm to simultaneously assign an offline machine and a processing level to each online task. We prove that OMLA achieves 1/2-competitive ratio if each machine has unlimited rejection budget and Δ/(3Δ-1)- competitive ratio if each machine has an initial rejection budget up to Δ. Interestingly, the competitive ratios do not change under different settings on the controllable processing time and we can conclude that OMLA is "insensitive" to the controllable processing time.
Keywords:
Planning and Scheduling: PS: Scheduling
Planning and Scheduling: PS: Planning under uncertainty