Two-Agent Scheduling with Linear Deteriorating Jobs on a Single Machine
Two-Agent Scheduling with Linear Deteriorating Jobs on a Single Machine
复制标题
DOI：
10.1007/978-3-540-69733-6_63
复制
发表时间：
2008-06
期刊：
影响因子：
--
通讯作者：
Peng Liu;Lixin Tang
中科院分区：
文献类型：
--
作者：
Peng Liu;Lixin Tang
研究了在单机上处理线性退化作业的双智能体调度问题。所谓退化作业，我们指的是该作业的处理时间是其开始时间的函数。两个代理竞争使用同一台机器，每个代理都有自己的优化标准。有四个目标函数：完工时间、最大延迟、最大成本和总完成时间。证明了两种不同的调度问题的一些基本性质，即当一个智能体的目标函数有约束时，另一个智能体的目标函数是最小的。基于这些性质，分别针对两种不同的调度问题给出了多项式时间的最优算法。
This paper considers the two-agent scheduling problems with linear deteriorating jobs to be processed on a single machine. By a deteriorating job we mean that the processing time of the job is a function of its starting time. Two agents compete for the usage of a common single machine and each agent has his own criterion to optimize. There are four objective functions: makespan, maximum lateness, maximum cost, and total completion time. Some basic properties of two different scheduling problems to minimize the objective function for one agent with a constraint on the other agent’s objective function are proved. Based on these properties, the optimal algorithms with polynomial time are presented for two different scheduling problems, respectively.