A Competitive Two-Agent Scheduling Problem on Parallel Machines with Release Dates and Preemption. (17th November 2013)

• Record Type: Journal Article
• Authors: Qi, Yawei; Wan, Long
• Other Names: Yin Yunqiang Academic Editor.
• Is Part Of: Mathematical problems in engineering. Volume 2013(2013)
• Publication Date: 2013-11-17
• Subjects: Engineering mathematics -- Periodicals; 510.2462
• DOI: 10.1155/2013/124083
• Languages: English
• ISSNs: 1024-123X

Abstract

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.