误工排序问题

论文摘要

经典排序论中使误工工件的个数为最少的单台机器排序问题,简称为误工问题[14],它是排序论中最基本的问题之一,具有重要的理论意义和实用价值.本文研究误工排序问题及其推广,研究这些问题的算法和改进.本文第一章,综述了排序论的学术意义和排序问题的研究概况.本文第二章,介绍了排序问题的一些基础知识.本文第三章,首先研究经典的误工问题1‖∑Uj,著名的Moore-Hodgson算法可以在时间O（n log n）内得到误工问题的最优解.虽然经过改进,然而Moore-Hodgson算法最优性的证明仍然非常复杂.本文研究Moore-Hodgson算法最优性新的证明,给出Moore-Hodgson算法最优性的几种简单的证明.并且在Moore-Hodgson算法最优性证明的基础上,又分析和研究了求解几种推广的误工排序问题的算法,并且也给出相应的比较简单的新的证明.比如研究求解在保证工件的一个子集T中的工件必须不误工的前提下,使误工工件的个数为最少的误工问题1｜T｜∑Uj的Sidney算法,并且给出Sidney算法最优性新的证明;研究求解工件的就绪时间不相同、但是与交货期有“一致性”关系时,使误工工件的个数为最少的误工问题1｜（ri≤rj）（?）（di≤dj）｜∑Uj的KIM算法.对误工排序问题1｜（ri≤rj）（?）（di≤dj）｜∑Uj,最近李杉林、陈志龙、唐国春用反例指出Kise、Ibaraki、Mine证明最优性时提出的引理2是错误的.本文分析引理2的错误所在,给出修改后的引理2’,由此应该相应修改KIM算法,然而,最后,我们证明KIM算法仍然可以得到最优解.在本文中也给出了越民义先生对KIM算法最优性的一个新的简单的证明.接着本文分析和研究了工件之间存在先后关系的误工问题1｜prec｜∑Uj,根据工件之间的先后关系找到一个求解这个误工排序问题的有效算法.并且在此基础上,本文又分析和研究了工件有先后约束的最小带权误工工件数排序问题1｜prec｜∑wjUj,在没有任何约束条件的情况下,根据工件之间的先后关系找到一个求解这个带权误工工件数排序问题的有效算法.本文第四章,分析和研究了多台机器的误工排序问题.在罗守成,唐国春研究两台平行机误工排序问题P2‖∑Uj的基础上,给出了三台平行机误工排序问题P3‖∑Uj的解的一些性质.并且在Moore-Hodgson算法的基础上研究了多台机器误工排序问题Pm｜pj=1｜∑wjUj和Pm｜T,pj=1｜∑Uj等.本文第五章,对全文作了一个总结,并提出了一些有待研究的问题.

论文目录

• 中文摘要
• 英文摘要
• 1 绪论
• 1.1 课题的学术和应用意义
• 1.2 排序问题的研究概况
• 1.3 本文的研究的目的和研究内容
• 2 基础知识
• 2.1 排序问题的定义、分类、三参数表示及求解
• 2.2 排序问题的算法与复杂性
• 3 单台机器误工排序问题
• j'>3.1 经典的误工排序问题1‖∑U_j
• j的性质和Moore-Hodgson算法'>3.1.1 误工排序问题1‖∑U_j的性质和Moore-Hodgson算法
• 3.1.2 Moore-Hodgson算法最优性的几种证明
• j'>3.2 误工排序问题1|T|∑U_j
• i≤r_j）（?）（d_i≤d_j）|∑U_j'>3.3 误工排序问题1|（r_i≤r_j）（?）（d_i≤d_j）|∑U_j
• 3.3.1 KIM算法及其引理2
• 3.3.2 李杉林、陈志龙、唐国春的反例
• 3.3.3 修改后的引理2
• 3.3.4 KIM算法仍然可以得到最优解
• i≤r_j）（?）（d_i≤d_j）|∑U_j'>3.4 误工排序问题1|T,（r_i≤r_j）（?）（d_i≤d_j）|∑U_j
• j'>3.5 工件有先后约束的误工工件数排序问题1|prec|∑U_j
• jU_j'>3.6 工件有先后约束的最小带权误工工件数排序问题1|prec|∑w_jU_j
• 4 多台机器误工排序问题
• j'>4.1 平行机误工问题Pm‖∑U_j
• j'>4.1.1 平行机误工问题P2‖∑U_j
• j和Pm‖∑U_j'>4.1.2 平行机误工问题P3‖∑U_j和Pm‖∑U_j
• j=1|∑w_jU_j误工排序问题'>4.2 Pm|p_j=1|∑w_jU_j误工排序问题
• 5 总结与讨论
• 参考文献
• 致谢
• 附:1. 作者在攻读硕士学位期间发表的论文目录、科研情况