A Competitive Two-Agent Scheduling Problem on Parallel Machines with Release Dates and Preemption. (17th November 2013) - Qi, Yawei; Wan, Long
Abstract : We consider a competitive two-agent scheduling problem on multiple identical machines with release dates and preemption. In the scheduling model, there are two agents a and b each having their own job sets 𝒥 a = J 1 a, …, J n a a and 𝒥 b = J 1 b, …, J n b b , respectively. Each job J j ∈ 𝒥 a ∪ 𝒥 b has a release date r i and the n = n a + n b jobs need to be preemptively scheduled on m identical machines. For m = 2, we show that the trade-off curve of all the Pareto optimal points can be characterized in polynomial time. When m is input, we show that P | r j, p m t n | L m a x a : L m a x b ≤ Q can be solved in strongly polynomial time.