若干新型排序算法与计算复杂性研究

在经典排序中，通常假设工件的加工时间为常数，但在许多实际问题中,工件的加工时间可能与其开工时间和（或）所排位置有着某种联系，由此产生一些新型排序问题。这些问题在钢铁工业及医疗等方面有着广泛的应用，是当今国际研究的热点问题之一。本课题将深入研究工件加工时间可变的新型排序，主要有：(1)工件加工时间与开工时间有关的排序，研究其中的若干未解决问题和更复杂实用的目标函数；(2)工件加工时间与所排位置有关的问题，研究其中的若干未解决问题和更复杂实用的目标函数；(3)建立更符合实际的新模型，分析模型的计算复杂性和算法。(4)将研究成果应用到实际问题中，来检验算法的可行性。这些新型排序比经典排序更为实用，也更为复杂，绝大多数都是NP-难的，将通过探讨可行排序或最优排序的局部及整体性质和数量关系，建立系统有效的计算方法和基本理论。本研究预计将在计算复杂性分析、算法设计及模型建立等方面做出创新性的研究成果

工件加工时间可变的排序问题在钢铁工业及医疗等方面有着广泛的应用，是当今国际研究的热点问题之一。本项目研究成果主要包括三方面内容：（1）工件的加工时间与开工时间有关的排序（恶化工件）；(2)工件加工时间与所排位置有关的问题（学习效应）；(3) 工件加工时间同时具有学习效应、恶化效应和（或）资源分配的排序问题。.在第一方面，对多台机器的流水作业排序问题，目标函数为最大完工时间、总完工时间与加权总完工时间分别提出了分支定界算法和启发式算法；对单机情况，工件具有共同松弛工期问题给出了一个多项式时间最优算法。.在第二方面，研究多台机器的流水作业排序问题，对几个正则目标函数分别提出了近似算法和启发式算法；提出了工件加工时间具有一般学校效应的排序模型，即工件加工时间即与所排位置有关，又与之前完成的工件有关，对一些正则目标函数分别给出了多项式时间最优算法。.在第三方面，提出了工件加工时间与开工时间、所排位置和所用资源都有关系的排序模型，对一些正则目标函数分别给出了多项式时间最优算法。研究了工件加工时间同时具有学习效应和恶化效应的排序问题，取得了一系列成果。