中文摘要：

本课题通过运筹学与组合优化的研究途径，对精益生产中常见的完成时间偏差问题进行数学概括，并进行优化改善。广义完成时间偏差问题是对精益生产中常出现的一大类时间偏差问题的统一数学表达。本课题拟通过对广义完成时间问题在各个维度(如权重、完成时间等)的简化，建立原问题与文献中各类相关的时间偏差优化问题之间的联系，探索原问题的最优解的特殊性质和数学结构，对文献现有结果进行高阶推广。在算法层面，本课题一方面拟通过模拟最优解的一系列性质，设计高效可靠的启发式算法。另一方面拟结合优化约束理论，在复杂约束条件上构建具有良好求解特征的数学结构，对优化过程的收敛速度进行改善。本课题的研究拟以广义完成时间偏差问题为突破口，形成一系列适用于高阶时间偏差优化问题的优化方法，整合和推广文献中各类低阶模型最优解存在的各类优良性质。对精益生产理论中广泛存在的时间偏差问题进行有机的理论概括和提升。

结论摘要：

本项目着眼于研究在单台加工机器上复杂加权完成时间偏差优化模型（1||GWCD）。这个问题在数学上可以转化为大量现有的文献中的非常规调度优化模型，非常典型且具有一般性。本课题组所获得的科研成果可以直接用于解决这一大类非常规调度问题，并为非常规调度问题的整体解决提供了一些新的思路。 在本项目以理论研究为主，获得了重要成果。本课题组证明了1||GWCD与对应的等候时间的1||GWWD问题在任意阶等效。这个结果大幅推进了70年代Merten等人有关2阶的成果。当所有工作的权重相同时，课题组证明经了最大的工作必须放在首位，这是对Kanet和Schrage在80年代1阶和2阶工作的任意阶推广。对于工作大小相等的情况，课题组证明此问题属于P类，并给出了其解必须满足的螺旋形结构，此解几何结构非常优美，但在非常规调度问题中非常罕见，是在此课题的研究中首次提出。对于工作大小和权重都任意的一般情况，课题组还证明了对工作大小与权重正比下的LPT的最优性质，这是一般情况中极少的还能多项式时间可解的例子。 本项目的研究成果对实践也有重要的指导意义，权重相等的情况可以为准时生产在单机情况下的情形提供的数学依据。而工作大小相等的情况则为计算机科学中，特别是CPU计算过程中的线程调度提供了数学依据。课题组还成功的将本项目的研究成果推广到订单调度的相关工作中，取得了重要成果。