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

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

关于误工的两个代理单机排序问题

【目的】研究与误工相关的两个代理单机排序问题。【方法】第一个代理工件的到达时间与工期满足一致关系,目标函数为总误工或最大误工。第二个代理工件可中断,目标函数为总误工工件个数,在模型确定的情况下结合Lawler算法或EDD规则确定一个最优排序规则,使得满足第二个代理目标可行的情况下,第一个代理的目标函数值最小。【结果】在上述模型最优排序规则确定的前提下,求出最优排序方案使得第一个代理的目标函数最小。【结论】提出了总误工问题的一个拟多项式时间动态规划算法,给出了最大误工问题时间复杂度的证明。
     

关于误工的两个代理单机排序问题

【目的】研究与误工相关的两个代理单机排序问题。【方法】第一个代理工件的到达时间与工期满足一致关系,目标函数为总误工或最大误工。第二个代理工件可中断,目标函数为总误工工件个数,在模型确定的情况下结合Lawler算法或EDD规则确定一个最优排序规则,使得满足第二个代理目标可行的情况下,第一个代理的目标函数值最小。【结果】在上述模型最优排序规则确定的前提下,求出最优排序方案使得第一个代理的目标函数最小。【结论】提出了总误工问题的一个拟多项式时间动态规划算法,给出了最大误工问题时间复杂度的证明。     

误工工件个数和最大费用函数的单机双代理KS公平定价问题

【目的】考虑把资源分配的公平价格问题应用到单机双代理排序中,这里的双代理就是两个代理具有各自的工件集,公平竞争的安排在单台机器上加工自己的工件。【方法】第一个代理的目标函数为在共同工期的前提下最小化总权误工工件个数,第二个代理的目标是为最小化最大费用函数。【结果】给出公平效用的概念和KS公平定价的概念,进而给出了一般情况下KS的价格公平结构性之和紧界分析。【结论】推广了已有文献的结果。     

固定区间下的可中断单机双代理总加权误工问题

【目的】研究在固定区间内工件可中断的单机双代理排序问题。【方法】每个代理都有各自对应的工件集合以及目标函数，它们只能共同使用1台机器来完成各自工件的加工，每个代理的目标都是最小化各自的目标函数。第一个代理工件可中断且到达时间与工期满足一致性关系，目标函数为总加权误工费用；第二个代理中工件位于固定时间窗口内进行加工。【结果】排序的目的是为了第二个代理中工件满足加工时间区间等于固定区间条件下，使得第一个代理的目标函数达到最小化。【结论】利用了分块的原则，给出了最优性质刻画和复杂性分析，以及设计了一个伪多项式时间动态规划算法。     

最小化总完工时间和总延误的两代理公平定价问题

【目的】研究单台机器环境下，一个代理最小化总完工时间而另一个代理最小化总延误的公平定价问题。【方法】每个代理的工件有相同的加工时间，其中：第1个代理的目标是最小化总完工时间，第2个代理的目标是最小化总延误，并且第2个代理的工件拥有不同的交货期；将这一问题分为不同的情形分别进行考虑。【结果】在Pareto排序集合下的KS公平排序可以在线性时间内找到，并且公平定价的值为1/2，举例说明了这个界是紧的。【结论】上述结果对已有文献结果进行了推广，丰富了单台机器环境下两代理排序的公平定价问题的内容。     

总加权误工损失的两个代理单机排序问题

研究同总加权误工损失有关联的两个代理间单机排序的问题.两个代理之间的排序问题中,允许工件在加工过程中中断,设总加权误工损失为第一个代理的目标函数,最大正则函数是第二个代理的目标函数.在此问题中结合EDD规则确定一个最优排序算法,使得满足第二个代理目标可行的情况下,第一个代理的目标函数最小.在上述问题最优排序规则确定的前提下,求出最优排序使得第一个代理的目标函数最小.最终给出了和总加权误工损失有关的排序问题的一个最优算法,并且证明了问题在在多项式时间内可解.     

有公共交货期的单机分批排序问题（英文）

【目的】单机分批排序问题有着广泛的应用背景,很多问题是NP-困难的。有公共交货期的单机分批排序问题是一个非常重要的研究方向。【方法】利用组合最优化的方法,研究工件有公共交货期的最小化误工工件个数和总延误的单机分批排序问题。【结果】对于最小化误工工件个数问题提出了一个多项式时间算法,对于最小化总延误提出了一个伪多项式时间的动态规划算法。【结论】对于其他有公共交货期的分批排序问题的研究提供了重要的研究方法。     

有公共交货期的单机分批排序问题

【目的】单机分批排序问题有着广泛的应用背景,很多问题是NP-困难的。有公共交货期的单机分批排序问题是一个非常重要的研究方向。【方法】利用组合最优化的方法,研究工件有公共交货期的最小化误工工件个数和总延误的单机分批排序问题。【结果】对于最小化误工工件个数问题提出了一个多项式时间算法,对于最小化总延误提出了一个伪多项式时间的动态规划算法。【结论】对于其他有公共交货期的分批排序问题的研究提供了重要的研究方法。
     

平行机最小化误工损失调度问题的粒子群算法

【目的】讨论非同类机环境下最小化任务总误工损失的调度问题。任务的误工损失是与交付期有关的一种惩罚量,该惩罚量的值等于任务滞后于交付期加工的部分。【方法】设计了一个粒子群算法求解该问题,并以数值实验进行验证。【结果】针对问题特性,对粒子群算法中的粒子表达方式、运算操作、初始解生成、种群更新方法等进行了重新定义。【结论】数值实验表明,算法处理该问题时可获得性能良好的解,并且运行时间也在可接受范围之内。