Online Task Assignment with Controllable Processing Time

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.

Authors

• Ruoyu Wu The University of Sydney
• Wei Bao University of Sydney
• Liming Ge

Keywords

• Planning and Scheduling: PS: Planning under uncertainty
• Planning and Scheduling: PS: Scheduling