单台批处理机总加权完成时间最小化的启发式算法

批处理机总加权完成时间最小化问题的复杂性目前还没有确定,因此有必要研究该问题的启发式算法.基于对该问题最优解性质的分析,提出了工件分批的最优性质.分别基于W SPT规则和SPT规则对工件进行总排序,利用工件最优分批性质进行分批,提出了两种启发式算法(简称为W SPTS和SPTS).为了检验算法的性能,将提出的算法与此问题的基准算法和常规算法进行了比较,结果表明,启发式算法W SPTS要优于其他的算法,而SPTS算法的性能最优.

单机排序中关于完工前总损失的应急管理

该文研究了扰动环境下的关于完工前总损失的单机排序问题,也就是这样一个问题:在时刻t,一部分工件已经完工了,一个扰动发生了,在这种情形下,原来的排序已经不是最优排序甚至是不可行排序了.因此就需要对未完成的工件找一个新的排序.作者采用的方法与大多数重新排序问题所不同的是:模型里包含了原始排序与新排序之间的偏差所造成的损失.作者主要研究了在原始排序中加权最短加工时间规则(WSPT)是最优排序的情形.根据扰动的类型,应急管理策略的类型以及目标函数,研究了几个问题.对于每个问题,作者找到了最优排序或者得出了一些重要结果.

产品协同设计中的任务排序研究

针对产品协同设计中任务排序的复杂性及动态性,提出了基于最小化完工时间的在线排序方法。在该方法中,通过分析设计者在协同设计过程中的行为状态,确定了任务剩余处理时间和任务的权。在此基础上,研究了在线排序的三种决策时间点上的优化排序以及有约束关系的任务排序问题,得出了协同设计任务排序规则。最后通过算例验证了该排序方法的有效性。

关于问题1‖∑W_j(1—e^(-rC_j))的一点注记

对于问题1‖∑W_j(1-e^(-rC_j)),分别讨论了当 r 充分接近于零或所有权 W_j=1时的最优排序.

具有公共交货期和提前—后惩罚的单机排序问题最优解的结构

求解具有公共交货和提前－滞后惩罚的单机排序问题是很困难的，其计算复杂性是强ＮＰ完全问题．作者研究这类问题的最优解的结构特征，得出了对于完工时间比公共交货期大的工件按ＷＳＰＴ序排列，对于完工时间少于公共交货期的工件按ＷＬＰＴ序排列，一般情况下的最优解具有Ｖ形结构的结论。