带有固定区间的双代理排序问题

【目的】研究带有固定区间的双代理排序问题。【方法】第一个代理的工件加工过程可以中断，考虑两种机器类型：单台机器时考虑的目标函数为总权误工损失或总权提前损失；两台平行机时考虑的目标函数为总完工时间，同时必须在规定的固定区间加工第二个代理的工件，目标是在满足第二个代理目标的可行性前提下寻找一个使第一个代理的目标函数值更小的排序方案。【结果】设计了单台机器固定区间工件损失问题的排序算法，也为两台平行机总完工时间问题设计了相应算法。【结论】设计的算法可在多项式时间内得到解决，且证明了算法的最优性，并用数值实验说明了算法的可行性。     

具有前瞻区间和不相容工件族的流水车间在线排序问题

研究对多台单位流水车间上具有前瞻区间的不相容工件族无界批处理的在线排序问题。通过组合优化的方法分类讨论得到问题的下界，对算法Am（β）进行了竞争比分析说明这是该问题最好可能的在线算法。给出了该问题的下界为1+η，其中η是方程(2f－1)η2+(f+β)η+β－f=0的一个正根，这里0≤β<1。同时提供了一个最好可能的在线算法Am（β）。通过竞争比分析说明了算法的可行性。