Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/28327
Title: Bounded parallel-batching scheduling with two competing agents
Authors: Fan, BQ
Cheng, TCE 
Li, SS
Feng, Q
Keywords: Competitive agents
Complexity
Dynamic programming
Parallel-batch
Scheduling
Issue Date: 2013
Publisher: Springer
Source: Journal of scheduling, 2013, v. 16, no. 3, p. 261-271 How to cite?
Journal: Journal of scheduling 
Abstract: We consider a scheduling problem in which two agents, each with a set of non-preemptive jobs, compete to perform their jobs on a common bounded parallel-batching machine Each of the agents wants to minimize an objective function that depends on the completion times of its own jobs The goal is to schedule the jobs such that the overall schedule performs well with respect to the objective functions of both agents We focus on minimizing the makespan or the total completion time of one agent, subject to an upper bound on the makespan of the other agent We distinguish two categories of batch processing according to the compatibility of the agents In the case where the agents are incompatible, their jobs cannot be processed in the same batch, whereas all the jobs can be processed in the same batch when the agents are compatible We show that the makespan problem can be solved in polynomial time for the incompatible case and is NP-hard in the ordinary sense for the compatible case Furthermore, we show that the latter admits a fully polynomial-time approximation scheme We prove that the total completion time problem is NP-hard and is polynomially solvable for the incompatible case with a fixed number of job types.
URI: http://hdl.handle.net/10397/28327
ISSN: 1094-6136
EISSN: 1099-1425
DOI: 10.1007/s10951-012-0274-0
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

24
Last Week
1
Last month
1
Citations as of Aug 11, 2017

WEB OF SCIENCETM
Citations

19
Last Week
0
Last month
1
Citations as of Jul 28, 2017

Page view(s)

42
Last Week
2
Last month
Checked on Aug 13, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.