基于工件恶化的并行批调度研究

项目名称： 基于工件恶化的并行批调度研究

项目编号： No.11201259

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 苗翠霞

作者单位： 曲阜师范大学

项目金额： 22万元

中文摘要： 基于工件恶化的并行批调度是更切合实际的一种现代调度模型，在实际中具有广泛的应用。目前国内外对于这种模型的研究处于起步阶段。本项目将对这种调度模型开展如下研究：首先讨论极小化最大完工时间、总完工时间等目标下线性恶化工件的单机或平行机调度问题的复杂性；其次，对其中的NP-难问题，我们将设计问题的"有效的"近似算法，分析算法的最差性能比并进一步利用数据的舍入等技术设计问题的伪多项式时间算法或全多项式时间近似方案。最后，对工件加工时间为二次函数的并行批调度问题，我们将讨论其复杂性及有效算法，并进一步推广到工件加工时间为更高阶函数的并行批调度问题上。

中文关键词： 批调度；恶化工件；NP-难；近似算法；全多项式时间近似方案

英文摘要： The parallel batch scheduling with deteriorating jobs (PBSDJ) is a relative practical scheduling model, and has wide applications in practice. Until now, the research is still in a preliminary step. In this project, the following research topics on PBSDJ are included. Firstly, we will discuss the scheduling of linear deteriorating jobs on a single(parallel) batch machine with minimizing the maximum(total) completion time. For these problems, the complexity analysis will be presented. Secondly, for the NP-hard cases, some effective approximation algorithms will be designed and the worst performance ratio will be analyzed， furthermore, pseudo-polynomial time algorithms and/or fully polynomial time approximation scheme will be proposed based on the technique of rounding the input data. Finally, we will discuss the complexity and algorithms for the quadratic deteriorating model. Furthermore, we will generalize the obtained results to the higher order deteriorating models.

英文关键词： batch scheduling；deteriorating jobs；NP-hard；approxximation algorithm；fully polynomial time approximation scheme