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

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.

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

基于工件恶化的并行批调度是更切合实际的一种现代调度模型，在实际中具有广泛的应用。目前国内外对于这种模型的研究处于起步阶段。本项目所做的主要工作:（1）批容量无限情形，对具有到达时间的极小化最大延迟单机排序问题和可拒绝恶化工件排序问题等，给出了NP-难的证明，并提出了近似算法、伪多项式时间算法及全多项式时间近似方案；（2）批容量有限情形，对最大完工时间的两类恶化工件的单机及平行机排序问题及极小化总完工时间的成比例恶化的排序问题等，分别给出了全多项式时间近似方案和部分最优序；（3）对资源有约束的恶化工件排序及继列批排序及其他相关排序给出了一些结论。本项目部分结论对相关企业生产具有一定的指导意义。