重新排序问题及其研究

Scheduling is an important combinatorial optimization. For the morden industrial production manangement and the morden service industry management, reschdeuling problems are a very important research topic. Rescheduling has a close relation with practical application background, and is so intimately associated with multicriteria scheduling and multiagent scheduling. The project involves two rescheduling types: The first is pure rescheduling, the objective of which is to find a new schedule that is an optimal in the new environment with respect to the original objective function. The second is to consider both the original objective function and a measure of deviation from the original schedule. The proect attempts to study rescheduling models with offline, online and vary processing time and their algorithms, including (a) investigating some class objective of multicriteria and multiagent rescheduling under sequence disruption and time disruption; (b) researching post-disruption management and predictive-disruption management of machine scheduling models under machine disruption or job disruption; (c) studying approximation algorithm or online algorithm for the above two problems. Results of this research will reveal some new ideas, new methods and new result for the application in rescheduling theory.

排序问题是一个重要的组合优化问题，重新排序的研究对于现代工业生产管理和现代服务业运作管理来说是一个重要的研究课题。重新排序问题具有很强的实际背景，经常与多代理排序、多目标排序紧密相关。本项目研究重新排序的两种类型：一是纯重新排序，也就是在新的环境下找到最优序，另一个是考虑原目标函数和与原始序列的偏离费用。针对离线、在线、工件加工时间可变的排序模型及其算法问题展开一系列的研究。研究的主要内容为：（1）时间错位和序列错位下的讨论经典目标函数的有效算法和多目标、多代理的重新排序问题；（2）机器扰动或者工件扰动下的后干扰管理和先干扰管理的机器排序模型研究。（3）两类问题的近似算法和在线算法研究。项目的预期成果将为重新排序理论方面提供一些新的思想、方法和理论研究成果。

1) 结合加工时间可变的情形，研究了工件的工期和加工时间具有一致关系性质的重新排序问题，分别证明了在最大序列错位限制和总序列错位限制下，最小化总误工问题是多项式时间可解的。在最大时间错位限制和总时间错位限制下，最小化总误工问题具有拟多项式时间算法。2）具有工件位置相关的退化效应，机器需要多次维修且维修具有退化效应时，对于目标函数为最小化提前、误工、交货期的大小和交货期位置的组合问题，通过广义指派问题给出了最优算法。3）工件具有学习效应作用下，研究了最小化总完工时间的重新排序问题，其中工件加工时间是其所在序列加工位置有关的函数。对于最大序列错位、总序列错位和最大时间错位下最小化总完工时间问题均给出了多项式时间算法，对于总时间错位下最小化总完工时间问题提出了动态规划算法，并证明这个算法是拟多项式时间的。4）工件加工时间是加工所在的位置和开工时间的非增函数，目标函数为最小化误工工件个数和总误工。利用Moore-Hodgson算法作为启发式算法，对于目标函数位误工工件个数情形给出了最坏竞争比近似于2，利用EDD规则作为启发式算法，对于最小化总误工给出非常数的最坏竞争比。如果工件加工时间和工期具有一致关系，分别给出了两个多项式时间算法。5)pred-mgt和post-mgt 两类情形，对于目标函数为总完工时间和最大延迟问题，利用SPT-EDD规则进行了初步分析，给出了工件具有一致情形下的多项式时间算法。