带有线性恶化工件和释放时间的两个代理单机调度问题

摘要：

研究了带有简单线性恶化工件和释放时间的两个代理单机调度问题。所有工件在一台机器上加工，每个代理有各自依赖于自己工件的优化目标。针对工件释放时间相同与不同两种情况，研究了有约束的优化模型，即找到调度最小化一个代理的目标函数而使得另一个代理的目标函数不超过一个给定的上界。当工件具有相同的释放时间，我们主要考虑的目标函数有：总加权完工时间和总加权拖期工件数。当工件具有不同释放时间，我们考虑的目标函数有：最大完工时间、总完工时间以及拖期工件数。对于每一个问题，我们分析了问题的计算复杂性。此外，对于NP 难问题的一些特殊情况本文分析了最优解性质，基于这些性质给出了最优算法。

关键词：调度、两个代理、恶化工件、释放时间、单机

分类号：O22;TP3

资助基金：国家自然科学基金重点项目71032004;国家自然科学基金创新研究群体科学基金项目71321001资助Supported by Supported by Key Project of National Natural Science Foundation of China71032004;the Fund for Innovative Research Groups of the National Natural Science Foundation of China71321001

在线出版日期：2015-02-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：104-112