Bounded parallel-batching scheduling with two competing agents
Bounded parallel-batching scheduling with two competing agents
复制标题
具有两个竞争代理的有界并行批处理调度
DOI：
10.1007/s10951-012-0274-0
复制
发表时间：
2013
影响因子：
2
通讯作者：
Q. Feng
中科院分区：
文献类型：
--
作者：
Baoqiang Fan;T.C.E. Cheng;S.S. Li;Q. Feng
我们考虑了一个调度问题，其中两个代理，每个代理都有一组非抢占式作业，在一个公共的有界并行批处理机上竞争执行他们的作业。每个代理都希望最小化一个依赖于其自身作业完成时间的目标函数。目标是调度作业，使总体调度相对于两个代理的目标函数执行得很好。我们专注于最小化一个代理的完工时间或总完成时间，满足另一个代理的完工时间上限。我们根据代理的兼容性来区分两类批处理。在代理不兼容的情况下，它们的作业不能在同一批中处理，而当代理兼容时，所有作业可以在同一批中处理。我们证明了相容情况下的最大完工时间问题可以在多项式时间内求解，相容情况下的最大完工时间问题在一般意义下是NP难的。此外，我们还证明了后者允许完全多项式时间逼近方案。我们证明了总完工时间问题是NP难的，并且对于具有固定作业类型的不相容情况是多项式可解的。
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.
登录
查看更多内容
影响因子：
6.4
作者：
Potts, CN;Kovalyov, MY
通讯作者：
Kovalyov, MY
影响因子：
2
作者：
Shisheng Li;Jinjiang Yuan
通讯作者：
Shisheng Li;Jinjiang Yuan
影响因子：
2
作者：
Baker, KR;Smith, JC
通讯作者：
Smith, JC
影响因子：
2.7
作者：
Leung, Joseph Y. -T.;Pinedo, Michael;Wan, Guohua
通讯作者：
Wan, Guohua
影响因子：
1
作者：
Ng, C. T.;Cheng, T. C. E.;Yuan, J. J.
通讯作者：
Yuan, J. J.