带有不可用区间的可拒绝排序问题-运筹学与控制论专业论文.docxVIP

目 录 HYPERLINK \l _bookmark0 第一章 绪 论1 HYPERLINK \l _bookmark1 1.1 排序问题研究背景1 HYPERLINK \l _bookmark2 1.2 退化效应问题研究现状1 HYPERLINK \l _bookmark3 1.3 拒绝问题研究现状1 HYPERLINK \l _bookmark4 1.4 不可用区间问题研究现状2 HYPERLINK \l _bookmark5 1.5 本文涉及的符号表示2 HYPERLINK \l _bookmark6 1.6 本文主要研究内容4 HYPERLINK \l _bookmark7 第二章 极小化最大完工时间的可拒绝单机排序问题5 HYPERLINK \l _bookmark8 2.1 引言5 HYPERLINK \l _bookmark9 2.2 问题描述5 HYPERLINK \l _bookmark10 2.3 动态规划算法5 HYPERLINK \l _bookmark11 2.4 数值例子7 HYPERLINK \l _bookmark12 2.5 全多项式近似方案9 HYPERLINK \l _bookmark13 2.6 本章小结12 HYPERLINK \l _bookmark14 第三章 极小化加权总完工时间的可拒绝单机排序问题13 HYPERLINK \l _bookmark15 3.1 引言13 HYPERLINK \l _bookmark16 3.2 问题描述13 HYPERLINK \l _bookmark17 3.3 全多项式近似方案13 HYPERLINK \l _bookmark18 3.4 算法复杂性分析15 HYPERLINK \l _bookmark19 3．5 本章小结18 HYPERLINK \l _bookmark20 第四章 极小化加权总完工时间的可拒绝平行机排序问题19 HYPERLINK \l _bookmark21 4.1 引言19 HYPERLINK \l _bookmark22 4.2 问题描述19 HYPERLINK \l _bookmark23 4.3 全多项式近似方案19 HYPERLINK \l _bookmark24 4.4 算法复杂性分析22 HYPERLINK \l _bookmark25 4.5 本章小结26 HYPERLINK \l _bookmark26 结论与展望27 HYPERLINK \l _bookmark27 参 考 文 献28 HYPERLINK \l _bookmark28 致谢31 HYPERLINK \l _bookmark29 个人简历及在学期间的研究成果和发表的学术论文32 带有不可用区间的可拒绝排序问题 带有不可用区间的可拒绝排序问题 PAGE PAGE 10 第一章 绪 论 1.1 排序问题研究背景 排序问题是组合最优化问题中的一类，也是运筹学中比较的一个分支[1]。排 序问题主要包括三个要素：机器、任务和目标函数。在实际生产过程中，退化现 象是由于生产设备长时间使用而导致的。加工工件在排序中的开始加工时间越 晚，它的实际加工时间就会越大。比如钢铁生产，消防，资源分配等等。同时， 机器通常需要进行保养，或发生故障时进行维修等原因，导致机器在某一时间段 内无法工作，该时间段即为机器的不可用区间。在一些实际问题中，厂家通常会 拒绝一些获利相对较小的工件，虽然节约了一定的生产成本，但是需要付出一定 的惩罚费用，如航空业、电子工业等等。 1.2 退化效应问题研究现状 现实生活、生产中，任何延迟都会导致退化现象的产生，例如钢铁生产，消 防，医疗等。退化效应模型由 Gupta 和 Gupta[3]以及 Browne 和 Yechiali[4]提出， 工件的实际加工时间为 pj ??aj ??bjt ( bj ??0 )，目标为极小化最大完工时间，证明 了最优排序为工件按{ a j / bj }不减顺序排列。对于工件带有退化效应的模型， Mosheiov[5]研究了有多项式时间算法的单机排序问题，目标为极小化最大完工时 间、加权总完工时间等。Wu 等[6]研究了加权总完工时间问题，给出了该问题的 启发式算法和分支定界算法。Ji 等[7]研究了目标为极小化总完工时间以及加权总 完工时间的问题，给出了全多项式近似方案。崔苗苗等[8]研究了机器带有不可用 区间的加权总完工时间问题，分别研究了单机以及两台机器的平行机问题，给出 了动态规划算法，该算法是拟多项式时间的。Wang 等[9]研究了平行机排序问题， 且机器带有不可用区间，目标函