【摘 要】
：
工件可拒绝的排序问题是从实际问题中提炼出来的,具有较强的应用背景。在实际生产中,制造商可能会选择拒绝加工一些成本高、耗时长或回报低的工件,并支付一定的费用。且在传统的排序问题中,工件的加工时间总是固定的。而在实际加工过程中,工件的加工时间可能会因为诸多因素而发生变化。由于机器的磨损或者温度的改变等原因,工件的加工时间随着开始加工时间的增加而增加,即产生退化效应;随着工人熟练度的提高,工件被加工的位
论文部分内容阅读
工件可拒绝的排序问题是从实际问题中提炼出来的,具有较强的应用背景。在实际生产中,制造商可能会选择拒绝加工一些成本高、耗时长或回报低的工件,并支付一定的费用。且在传统的排序问题中,工件的加工时间总是固定的。而在实际加工过程中,工件的加工时间可能会因为诸多因素而发生变化。由于机器的磨损或者温度的改变等原因,工件的加工时间随着开始加工时间的增加而增加,即产生退化效应;随着工人熟练度的提高,工件被加工的位置越靠后,加工时间就越短,即产生学习效应。由于机器的维修、保养或更换工具等原因,导致机器在某些时间段不可用,即产生不可用区间。因此,对带有拒绝和可变加工时间的排序问题的研究将有助于提高机器利用率、降低在制品库存、提高顾客满意度。本文主要研究了带拒绝的若干单机排序问题。主要内容概括如下:1.考虑了工件带有截止日期约束的可拒绝单机排序问题,目标为极小化总加权误工量与拒绝惩罚之和,其中工件的误工量是指这个工件误工时在工期之后的加工时间。在此排序问题中,每个工件都有一个截止日期。首先说明了在截止日期约束下,当工件的工期都相同时,极小化总加权误工量与拒绝惩罚之和的单机排序问题是NP-难的,然后用依次列举关键工件的方法求解了此问题,提出了时间复杂度为O（n ~3d）的拟多项式动态规划算法,并用数值例子进行了验证。2.考虑了带有退化和不可用区间的可拒绝单机排序问题。假设工件有不同的基本加工时间和相同的退化率,被拒绝的工件需要支付拒绝惩罚,机器在给定的时间区间内是不可用的且工件加工中断后再加工时是不可恢复的。目标是极小化接受工件的总完工时间与被拒绝工件的总拒绝惩罚之和。对于该NP-难问题,提出了一个拟多项式时间的动态规划算法,进而给出了一个完全多项式时间近似策略。3.当机器有不可用区间且工件不可恢复时,考虑了具有De Jong学习效应的可拒绝单机排序问题,目标为极小化总完工时间与拒绝惩罚之和。工件的实际加工时间与位置有关,被拒绝的工件需要支付拒绝惩罚。对于该NP-难问题,应用过程划分的方法构造了一个完全多项式时间近似策略,并分析了算法的复杂性。
其他文献
因为传统化石能源的大量采用和即将面临的能源短缺,氢能被选用为有潜力的能源载体。化石燃料制氢等方法制取氢气会造成大量污染,利用催化剂催化硼氢化钠（Na BH4）水解产生氢气已经被人们广泛关注。贵金属催化剂表现出良好的催化活性和稳定性,但是有限的资源和较高的成本限制了它的大规模使用。所以,开发非贵金属催化剂成为首要任务。本文制备了两类不同的负载型催化剂。一类是全部采用非贵金属材料制备了单载体（泡沫铜）
石墨烯是一类主要由碳原子经过sp~2杂化后构成的二维碳材料,呈蜂窝状结构,其厚度仅为单原子层厚度。由于其独特的结构,石墨烯表现出许多优异的特性,比如高透光率、极高的电子迁移率、高导热系数、极大的比表面积等。由于这些独特的性质,石墨烯在微电子、有机光电、储能、生物医学和复合材料等众多领域显现出了巨大的研究价值和光明的应用前景。介电常数作为石墨烯光电特性的重要参数之一,已有很多学者展开了研究,但目前对
γ′-Ni3Al作为镍基高温合金的关键强化成分,被广泛用于商用合金中。但因其低的高温蠕变强度和本征脆性而严重影响了其应用。研究表明添加Mn元素可以提高Ni3Al的延展性。但对于Mn在Ni3Al中的占据行为,由于实验条件的不同导致Mn的占据有所不同。Mn在Ni3Al中的占位倾向仍需进一步研究。由于添加B可以进一步增强Mn改善合金延展性的成分范围,且B易向Ni/Ni3Al界面偏聚,对界面处Mn占位的影
共价有机框架（Covalent Organic Frameworks,COFs）是一种由有机小分子结构单元通过共价键自组装形成的一类有序结晶性有机多孔材料。其中,光响应的共价有机框架因其良好的光化学活性、较强的稳定性及可调节性,已成为一种可用于光致有机小分子转化的新型非均相光催化剂。然而,在可见光驱动的区域选择性碳氢键活化反应中,如想实现区域选择性的获得,往往需要借助过渡金属活性中心与底物的有效螯
线上教学的实施和推广促使信息技术在教育领域的快速发展,对教师信息化教学能力提出了更高的要求。因此本研究在整合技术的学科教学知识（TPACK）视阈下进一步探究初中英语教师的信息化教学能力。通过研究梳理发现以往的研究主要是以TPACK为基础从不同的维度分析教师信息化教学能力现状以及教师信息化教学能力提升的影响因素。与以往研究不同的是,本研究以辽宁省新中考增加的口语和听力测试为背景,通过课堂观察分析营口
当前,世界科技的高速发展需要信息技术也要更快地革新与突破,这导致电子科技产品生产所必需的新型功能材料亟待开发。现在以半导体为代表的传统微电子学元器件因处理速度,稳定性等因素,发展逐渐缓滞,所以研发新型功能材料需要尽快提上日程。因此,自旋电子学应运而生。基于自旋电子学研发的电子设备不仅会极大地改善电子信息计算处理速度与资料存储问题,其稳定性也将大幅度增强。在众多新型功能材料中,Heusler合金蕴藏
巨共振已成为当今核物理研究中的热点课题,人们对其进行了大量研究,目前人们对同中子异荷素十分感兴趣,所以本文对N=82及N=126同中子异荷素的巨共振性质展开了研究。本文选用的模型为独立粒子模型,以准粒子无规位相近似方法（QRPA）与Skyrme-Hartree-Fock+BCS为理论基础,采用Skyrme相互作用（参数分别为Sk M*、SGII和SLy5）计算了N=82和N=126同中子异荷素链原
在大规模的生产流水线上,常常有一台或者多台机器在成批地加工工件,因此,对于串行分批排序的研究有很大的理论意义和实际应用价值。在串行分批排序问题中,批的加工时间为这个批内所有工件的加工时间的和,批的完工时间为批内最后一个工件加工完成的时间。在同一批中的工件有相同的开始加工时间与相同的完工时间,分别为这批的开始加工时间和完工时间。每一批工件在加工过程中不可中断,只有当批中所有的工件都到达后,该批才可以
磷是植物生长过程中的必需元素,也是不可再生资源。在农业生产中,化学磷肥施加后,作物的磷肥利用率仅为15-20%,大部分被固定在土壤中。微生物是土壤磷素循环过程中重要参与者,对土壤磷转化有重要意义。本研究基于辽宁省农科院不同磷肥施用量的定位试验,试验处理包括四个化学磷肥施用梯度:P0:无磷肥施加,P90:90 kg P2O5/hm~2,P180:180 kg P2O5/hm~2,P360:360 k
近年来,随着计算机技术不断发展,材料热力学和动力学数据逐渐完备。相场模型逐渐成为一种模拟各种材料微结构演化过程的重要工具。Allen-Cahn方程、Cahn-Hilliard方程作为常用的相场方程,被广泛应用于中尺度水平微观结构演化预测以及材料科学领域,也逐渐被应用到天体物理学、流体力学、热力学以及化学等科研领域。这两类方程由于求得解析解均较困难,因此在一般情况下,其近似解借助数值方法来求解。但是