A Competitive Two-Agent Scheduling Problem on Parallel Machines with Release Dates and Preemption

Abstract EN

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={J1a,…,Jnaa} and ?b={J1b,…,Jnbb}, respectively.

Each job Jj∈?a∪?b has a release date ri and the n=na+nb 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|rj,pmtn|Lmaxa:Lmaxb≤Q can be solved in strongly polynomial time.