基于退化效应或可控加工时间的竞争排序研究

Scheduling is an important combinatorial optimization. For the modern industrial production management and the modern service industry management, it is a very important research topic in scheduling prolems with deteriorating effect or controllable processing times. We attempt to study scheduling models with deteriorating effect (The actual processing time of a job is a non-decreasing function of starting time or its position) or controllable (The job processing time can be controlled by allovating additional resources) processing times, and their algorithms, including (a) researching some new models and the valid algorithms of competitive scheduling problems, especially two-agent competitive scheduling problems. The objective functon is maximum cost function, total late work, total tardiness and the number of tardy jobs. We present optimal algorithms by dynamic programming method. (b) competitive scheduling problems with batch processing times. Batch includes: s-batch, the objective function with the total compression cost; p-batch, the compatiblity of the agents. This research belongs to the problem driven applied foundation research. It not only has very valubable application background, but also has certain difficulty for solving these problems. Results of this research will provide some new ideas, new methods and the new result for the application in scheuling theory research with non-constant.

排序问题是一个重要的组合优化问题。工件具有退化效应或可控加工时间相关排序理论研究对于现代工业生产管理和现代服务业运作管理来说也是一个重要的研究课题。结合退化效应（工件的实际加工时间是开工时间或加工所在位置的非减函数）或可控加工时间（工件的实际加工时间被额外的资源分配所控制），本项目对于竞争排序模型以及涉及的算法问题进行展开研究。研究的主要内容为：（1）竞争排序，特别是两个代理情形下的新型模型和有效算法；涉及最大费用、总迟后、总误工和误工工件个数等目标函数，通过动态规划算法思想设计出所研究模型的最优算法。（2）批处理在竞争排序中的应用，批处理包括：继列分批，考虑压缩费用相关的目标函数；平行分批，考虑代理之间的工件是否兼容。本项目属于问题驱动型的应用基础研究，不仅具有很强的应用背景，而且具有一定的难度。项目的预期成果将为加工时间非常数的情形在排序理论上的应用提供一些新的思想，方法和理论。

排序问题是一个重要的组合优化问题。工件加工时间可变的相关问题的理论研究对于现代工业生产管理和现代服务业运作管理也是一个非常重要的研究课题。本项目围绕工件加工时间可变，考虑竞争排序问题的数学模型，在线算法和机器具有维修限制为主要研究内容。此类模型的一般形式中工件加工方式可能分批也可能不分批。分批方式有两种：平行分批和继列分批。具体研究内容如下：(1) 对于工期相关的两个代理排序问题，考虑误工损失以及总误工为代理的目标，第二个代理的目标是最大费用函数，总完工时间以及误工工件个数。涉及到工件可中断，在固定区间内加工，具有到达时间限制。给出问题的复杂性证明以及近似算法分析，拟多项式时间算法或者给出算法实例分析。首次研究在自由作业机器下两个竞争代理最大完工时间的权组合问题，针对权系数任意和权系数等于1给出了强NP难和NP难的证明，以及提出两个近似算法；(2) 结合加工时间可变，机器具有可变的维修限制等情形，考虑了退化效应和可变维修区间，共同或者松弛工期指派问题，通过动态规划思想给出了拟多项式时间算法。结合医疗服务管理问题，考虑了截断退化效应的情形。分析了问题的最坏竞争比分析；(3) 结合按时或者列表在线排序情形，考虑目标函数为最大完工时间和最小化权加工时间。对于批容量不同以及工件按时到达，提供最好可能的在线算法和稠密算法分析在线竞争比分析。对于批容量有界和工件按列表到达，给出了最坏竞争比分析。针对医院实验室的在线情形，考虑到不同病人的不同样本，分批处理检验指标的问题，对于无界分批和有界分批，目标函数最大权完工时间问题，针对权系数范围提供了最好可能的在线竞争比分析；(4) 考虑工件带有位置效应和学习效应的单机排序问题，涉及到一般位置效应，一般学习效应矩阵，工件成组加工，序相关安装时间，多层供应链排序等，涉及到目标函数有最大完工时间，总完工时间，加权总完工时间或者总误工，给出问题的复杂性证明以及启发式算法的最坏界分析，利用动态规划算法思想给出了拟多项式时间算法或者给出算法实例分析。