Constant-factor online scheduling of subadditive batches
Statement
Tasks arrive as a rate-one Poisson process and have types in ; batch processing time is monotone and strictly subadditive and type incurs waiting cost rate . Is there an explicit online algorithm and universal constant whose long-run average cost satisfies for every and whenever the optimal value is finite?
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.