Unbounded parallel-batching scheduling with two competitive agents
Unbounded parallel-batching scheduling with two competitive agents
复制标题
DOI：
10.1007/s10951-011-0253-x
复制
发表时间：
2011-09
影响因子：
2
通讯作者：
Shisheng Li;Jinjiang Yuan
中科院分区：
文献类型：
--
作者：
Shisheng Li;Jinjiang Yuan
我们考虑调度问题时，两个代理人，每个家庭的工作，竞争执行各自的工作在一个共同的无界并行机器。批处理机可以批量同时处理任何数量的作业。批处理时间等于批中工件的最大处理时间。两个主要类别的批处理的基础上的兼容性的作业族或代理人的区别。在作业系列不兼容的情况下，来自不同系列的作业不能放置在同一处理批次中，而当作业系列兼容时，所有作业可以放置在同一处理批次中。我们的目标是找到一个时间表的所有工作的两个代理，最大限度地减少一个代理的目标，同时保持目标的其他代理低于或在一个固定值Q。多项式时间和伪多项式时间的算法，以解决各种组合的定期目标函数的情况下，工作家庭是不兼容或兼容。
We consider the scheduling problems arising when two agents, each with a family of jobs, compete to perform their respective jobs on a common unbounded parallel-batching machine. The batching machine can process any number of jobs simultaneously in a batch. The processing time of a batch is equal to the maximum processing time of the jobs in the batch. Two main categories of batch processing based on the compatibility of job families or agents are distinguished. In the case where job families are incompatible, jobs from different families cannot be placed in the same processing batch while all jobs can be placed in the same processing batch when job families are compatible. The goal is to find a schedule for all jobs of the two agents that minimizes the objective of one agent while keeping the objective of the other agent below or at a fixed valueQ. Polynomial-time and pseudo-polynomial-time algorithms are provided to solve various combinations of regular objective functions for the scenario in which job families are either incompatible or compatible.