带无向环优先级的单机总加权完成时间调度问题

单机调度是生产调度领域的一个经典问题,研究了工件间有加工优先级要求的单机总加权完成时间调度问题,考虑了若将工件优先级关系构成的优先级图视为无向图,包含有环的情况。针对该问题,设计了结合双向动态规划的拉格朗日松弛算法进行求解,使得可以求解一个工件可能有多个紧前或紧后工件的情况。大量实验测试结果表明,该算法能够在较短时间内得到令人满意的近优解。

具有链式约束的单机随机排序问题

研究具有链式约束的单机随机排序问题,目标函数为加权总完工时间的数学期望.分别对于链可中断和链不可中断两种情况,通过理论分析,给出了该问题的优先策略.

可变费用的单机等待损失排序问题

证明了可变费用的单机等待损失排序问题１‖Σｆ＿ｉ（ｃ＿ｉ）是ＮＰ－ｈａｒｄ；给出了一般情形下工件优先安排加工的两个判别条件；对几种特殊情形给出了多项式时间算法或最优解的判定条件。