带有减少线性恶化效应的双代理调度问题

本文研究带有减少线性恶化效应的双代理单机调度问题.该问题来源于钢铁企业中的连铸-轧制生产过程.两个代理在共同的单机上竞争加工各自的工件,每个代理都有自己的目标函数需要优化.目的是找到一个调度使得满足第二个代理的目标函数不超过一个给定的上界的约束下,第一个代理的目标函数最小.本文把减少线性恶化效应引入到双代理调度中,工件的加工时间定义为它们开始时间的减少线性函数.对于带有减少线性恶化效应的双代理单机调度的两个问题,分别给出了问题的一些最优性质,并提出了多项式时间最优算法.