带有拒绝工件的工期指派的排序问题-应用数学专业论文.docxVIP

目 录 HYPERLINK \l _bookmark0 第一章 绪 论1 HYPERLINK \l _bookmark1 1.1 排序问题研究背景1 HYPERLINK \l _bookmark2 1.2 工期指派问题的研究现状3 HYPERLINK \l _bookmark3 1.3 拒绝问题的研究现状4 HYPERLINK \l _bookmark4 1.4 资源分配问题的研究现状4 HYPERLINK \l _bookmark5 1.5 本文的主要研究内容6 HYPERLINK \l _bookmark6 第二章 带有恶化和拒绝工件的工期指派的单机排序问题7 HYPERLINK \l _bookmark7 2.1 引言7 HYPERLINK \l _bookmark8 2.2 问题描述7 HYPERLINK \l _bookmark9 2.3 CON 工期指派问题 8 HYPERLINK \l _bookmark10 2.4 SLK 工期指派问题 11 HYPERLINK \l _bookmark11 2.5 小结15 HYPERLINK \l _bookmark12 第三章 带有拒绝和线性资源分配的工期指派的单机排序问题16 HYPERLINK \l _bookmark13 3.1 引言16 HYPERLINK \l _bookmark14 3.2 问题描述16 HYPERLINK \l _bookmark15 3.3 线性资源分配问题17 HYPERLINK \l _bookmark16 3.3.1 CON 指派问题 17 HYPERLINK \l _bookmark17 3.3.2 SLK 工期指派问题 19 HYPERLINK \l _bookmark18 3.3.3 DIF 工期指派问题 21 HYPERLINK \l _bookmark19 3.4 小结23 HYPERLINK \l _bookmark20 第四章 带有拒绝和凸资源分配的工期指派的单机排序问题24 HYPERLINK \l _bookmark21 4.1 引言24 HYPERLINK \l _bookmark22 4.2 最优解性质24 HYPERLINK \l _bookmark23 4.3 小结27 HYPERLINK \l _bookmark24 结论和展望28 HYPERLINK \l _bookmark25 参考文献29 HYPERLINK \l _bookmark26 致 谢32 HYPERLINK \l _bookmark27 个人简历及在学期间的研究成果和发表的学术论文33 带有拒绝工件的工期指派的排序问题 带有拒绝工件的工期指派的排序问题 1 1 第一章 绪 论 1.1 排序问题研究背景 经过几十年的发展，排序问题已成为组合最优化问题的一个重要分支，排序 问题是指在时间上对资源作一安排以完成若干个任务。这里的资源可以表示机 器、设备、计算机等，而任务可以代表工件、产品、计算机要算的程序等[1]。随 着现代工业的发展，排序模型被不断突破。在经典排序模型中，一般地，假设工 件的加工时间是一个固定不变的参数，并且工件只能在机器上被逐个加工。然而 在一些实际问题中，工件开始加工的越晚，它的加工时间越长，例如钢铁工业， 消防，医疗急救等，任何耽搁都会导致工件的完工时间变大。另外，在一些制造 系统中，工件的加工时间可能是通过分配资源来控制的，如额外的钱、加班、能 源、燃料、催化剂、分包或额外的人力。在这种系统中，工件的加工顺序和资源 分配量应该仔细协调使得系统达到最有效的性能。资源分配分为两种情况：线性 资源分配和凸资源分配。 在销售谈判过程中，一家公司向其客户提供一个工期时，工期指派问题就出 现了。如果提供的工期远远超过客户的预期，该公司将不得不降低价格。在许多 情况下，工期是通过谈判设定的，而不是简单的由客户决定。工期固定的越晚， 产品按时完工或按时交货的可能性越高。如果工件提前完工必须被储存；如果工 件在其工期后完工将引发消费惩罚。因此工期指派也是制造系统中的一个重要方 面。工期指派分为公共工期(CON)，相同松弛(SLK)和无限制工期(DIF)。 公共工期指派(CON)：所有工件的工期都相同，即 d j ??d, j ??1,2,?, n ； 松弛工期指派(SLK)： d j ??p j ??q, j ??1,2,?, n ，其中 q ??0 为决策变量； 无限制工期指派(DIF)：所有工件可以无限制的指派一个工期； 在一些实际问题中，为了降低加工成本，工厂的决策者可能选择一些加工时 间长的任务由其它工厂制造，同时支付一些费用。因此我