单台机器排序问题中工件的预排序

• 作者: 孙亮 窦文卿
• 来源期刊: 科学技术与工程
• 学科: 数学
• 关键词: 预排序 单台机器排序 标号
• 年，卷（期）: 2012,（2）
• 所属期刊栏目: 论文
• 页码范围: 256-259
• 分类号: O223
• 字数: 4297字
• 语种: 中文
• DOI: 10.3969/j.issn.1671-1815.2012.02.002

摘要

在排序问题中,为了寻找一个工件的加工次序,有时需要对原来工件进行重新编号,即对工件进行预排序.例如用动态规划求解工件有先后约束关系的单台机器排序问题时,需要对工件进行预排序,使得先加工的工件的序号小于它的后继工件的序号,且使得某种指标达到最优.对于工件之间的先后关系呈链状结构的单台机器排序问题,给出了一个算法,并证明了该算法是最优的.对于工件之间的先后关系呈树形结构的单台机器排序问题,也给出了一个算法,并证明了对于某些特殊的树形结构的单台机器排序问题,该算法是最优的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	窦文卿	上海第二工业大学理学院	4	9	1.0	3.0
2	孙亮	上海第二工业大学理学院	1	0	0.0	0.0