工件具有入树或链约束的排序问题

发布时间：2021-07-05 15:13

　　排序理论是组合优化方向的一个活跃的分支,它起源于制造业,后来被推广到越来越多高新技术领域.随着各个行业间的交叉与融合,许多生产和运输问题都会作为排序问题里的新模型,被专家学者们关注与交流.本文中主要讨论了工件具有入树或链约束的几类排序问题.在考虑工件之间带有优先约束关系这类排序问题时需要注意工件在有向无圈图中的位置.本论文分四个章节对这类模型做了如下研究工作.第一章介绍了排序论的背景、相关基本知识以及符号.第二章研究了工件具有入树约束和单位加工时间的两台同类机排序问题,工件具有不同的到达时间,目标为极小化最大完工时间.对于该NP-难问题,首先我们设计了一个分支定界算法并证明了算法的正确性,然后通过一个具体的算例执行了该分支定界算法的运算过程.第三章研究了工件具有链优先约束的平行机排序问题,目标为极小化加权总完工时间.对于该NP-难问题,首先我们针对两台平行机设计了伪多项式时间动态规划算法,并证明了工件具有相同的加工时间的特殊情形是多项式可解的.然后将相应的算法和结论推广到了m台平行机上以及同类机上.第四章考虑工件具有链优先约束和成比例线性退化的单机排序问题,其中工件的加工时间是其开始时... 

【文章来源】：曲阜师范大学山东省

【文章页数】：38 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 具有优先约束的排序问题
    1.2 退化效应的排序问题
    1.3 P类问题和NP类问题
    1.4 算法
    1.5 三参数法
    1.6 符号说明
第二章 具有入树约束的同类机排序问题的分支定界算法
    2.1 引言
    2.2 基础知识介绍
    2.3 分支定界算法及算例
        2.3.1 分支定界算法
        2.3.2 算例
    2.4 小结
第三章 具有链约束的极小化加权总完工时间的平行机排序问题
    3.1 引言
    3.2 问题及符号
    3.3 问题P2|chains|∑wjCj
        3.3.1 一般情形
        3.3.2 多项式可解情形
    3.4 问题Pm|chains|∑w_jC_j
    3.5 问题Q2|chains|∑w_jC_j
    3.6 小结
第四章 工件具有链约束及成比例线性退化的单机排序问题
    4.1 引言
    4.2 问题及符号
    4.3 问题1|strong chains,pij=b_(ij)(A+Bt)|∑w_(ij)C_(ij)
    4.4 问题1|weak chains,pij=b_(ij)(A+Bt)|∑w_(ij)C_(ij)
    4.5 小结
参考文献
在校期间发表的学术论文、专利及艺术作品等
致谢


【参考文献】：
期刊论文
[1]关于问题Pm|chains|Cmax的PTAS算法[J]. 张传林,曹丽霞,郑培华.  北方工业大学学报. 2008(03)
[2]单位加工时间有链约束的恒速机排序问题[J]. 左兰.  绍兴文理学院学报(自然科学版). 2008(02)
[3]含作业到达时间的同类机调度问题启发式算法[J]. 李凯,靳鹏.  系统工程理论与实践. 2007(10)
[4]一类处理机具有准备时间的恒速机排序问题[J]. 石锐,赵传立.  沈阳师范大学学报(自然科学版). 2007(01)
[5]关于问题Pm|intree;pj=1;rj|Cmax的分支定界算法[J]. 张玉忠,张咸昭,孙志慧.  运筹学学报. 2006(02)
[6]带机器准备时间的同类机在线与半在线排序问题[J]. 丁际环,曲桂东,张伟,岳丽,张玉忠.  曲阜师范大学学报(自然科学版). 2003(03)
[7]任务具有链约束的平行机调度问题[J]. 赵传立,张庆灵,唐恒永.  控制与决策. 2001(S1)
[8]处理机具有准备时间的恒速机排序问题[J]. 赵传立,唐恒永,张庆灵.  系统工程学报. 2001(02)
[9]处理机具有准备时间的Qm,aj｜pj=1｜Cmax排序问题[J]. 赵玉芳,赵传立,唐恒永.  运筹与管理. 1999(03)

硕士论文
[1]带有链优先约束的两类排序问题[D]. 邹娟.曲阜师范大学 2004



本文编号：3266312