等间隔工期规则下的调度问题研究

来源 :江西财经大学 | 被引量 : 0次 | 上传用户:bianyitijie
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在调度问题的研究中,传统的工期规则规定每个工件的工期由工件自身决定,与工件在调度方案中的加工排序位置无关。但现实生活却存在这样一种情况:制造类企业有时依靠第三方物流企业提供车辆运输产品。货车会根据时间安排表定期到达制造工厂将产品运送到仓库。到达工厂的第i辆货车负责运输第i批产品。如果第i批产品在第i辆货车到达前完成,那么制造商会产生库存成本,否则货车就会产生等待成本;若第i批产品恰好在第i辆货车到达时完成加工,则不会产生成本。在这种情况下,传统的工期规则不利于对现实情况进行建模。因此,本文将工件的工期设定为由具体的调度方案中工件的加工排序位置决定,并且连续两个工期之间的间隔长度均相等。这种工期的设定规则称为等间隔工期规则。本文对四类不同机器环境中等间隔工期规则下的调度问题进行研究,考虑的优化目标为最小化工件最大延误时间。研究内容包含以下几个方面:(1)研究单机环境中等间隔工期规则下的调度问题:结合调度理论中的SPT规则设计了一个多项式时间算法,时间复杂度为O(nlog n),并进行数值实验验证理论结果的准确性。(2)研究两台及m台同型机环境中等间隔工期规则下的调度问题:利用弱NP-完全问题Equal-Size Partition问题构造实例,证明两台同型机环境下的调度问题是弱NP-难问题以及利用强NP-完全问题3-Partition问题构造实例证明m台同型机环境下的调度问题是强NP-难问题。此外,针对两台同型机环境的调度问题,本文还设计了一个时间复杂度为O(n·2 n·P/2)的动态规划算法,并进行数值实验验证理论结果的准确性。(3)研究两台机器流水作业环境中等间隔工期规则下的调度问题:利用强NP-完全问题3-Partition问题构造实例,证明该调度问题是强NP-难问题。同时得到推论,当目标函数改为工件总延误时间之和或工件总误工工件数时,这两个问题依然是强NP-难问题。这是对现有研究结果的改进。(4)研究两台机器开放作业环境中等间隔工期规则下的调度问题:利用强NP-完全问题3-Partition问题构造实例,证明该调度问题是强NP-难问题。本文利用各种实例构造和方法证明调度问题的复杂性或设计求解问题的算法,在理论上对这些调度问题的研究进行了补充,在实际应用中可以帮助制造类企业在面临相似问题时,及时地掌握其数学模型,从而为其迅速作出决策提供建议。
其他文献
山西省地处黄土高原,自然灾害频繁、水土流失严重,同时城镇化、工业化的进一步发展,使得土地资源的供需矛盾日益尖锐,土地利用问题愈发严重。土地利用系统的健康程度也体现出土地能否可持续利用,在一定程度上对土地资源的可持续利用起引导作用。本文经过深入研究土地利用系统健康理论,结合山西省的实际情况,根据PSR(Pressure-State-Response)模型构建了土地利用系统健康的指标体系,共包括26个
学位
伴随着中国城市的崛起与发展,工业化结构性矛盾逐渐凸显,负外部现象日益显著。双碳背景下,工业碳减排已成为中国碳达峰行动方案的重要任务。数字经济是中国工业绿色低碳转型的重要引擎,能够通过促进工业领域资源要素优化配置、绿色知识共享交流等方式推动工业节能降碳,为推进城市工业绿色治理、提高城市工业碳生产率提供了新路径。本文基于全要素生产率理论、资源基础观、知识溢出理论、新经济地理学等理论,以2011—201
学位
目的 基于《辅行诀》所载“汤液经法图”理论体系,对1例采用中药复方汤剂治疗的消渴病患者进行药学监护。方法 患者为老年女性,患有糖尿病、高血压、冠心病等多种疾病,以口干、口渴15年,伴夜间血压升高10 d就诊。从患者入院开始纳入药学监护,采用“汤液经法图”所示的五脏虚实辨证和五味补泻治疗理论原则,确定患者的病因病机和治则治法,并分析每次临床处方的合理性。开展药学问诊,监护临床治疗的有效性和安全性,并
期刊
股权结构作为公司控制权配置的决定性因素,在公司治理领域占据着核心地位。对于中国资本市场而言,控股股东“一股独大”是一种常见的股权结构。关于控股股东的治理效应,学术界存在两种对立观点:堑壕效应观(Entrenchment)和利益协同观(Alignment)。一方面,控股股东存在利用控制权优势攫取私利的堑壕效应,表现为第二类代理问题;另一方面,控股股东也存在利益协同效应,较大的持股比例和较高的利益一致
学位
在全球经济整合的潮流中,各国会计准则的改进方向均朝着国际财务报告准则(IFRS)靠拢。一个高质量、标准化的准则框架不仅可以有效稳定资本市场的发展,而且在一定程度上能优化经济资源的配置。2014年,《企业会计准则第39号——公允价值计量》(以下简称CAS 39)在我国正式出台。这一改变完善了公允价值的计量体系,进一步规范了公允价值信息的具体披露方式,逐步实现了准则的国际趋同。但是,CAS 39的颁布
学位
目的:采用能谱CT结合有限元分析建立股骨近端三维模型;分析股骨近端骨密度分布特点及骨质疏松骨折时骨量流失特征;与双能X线进行比较,评估能谱CT结合有限元分析测量股骨近端骨密度的价值。方法:回顾性分析近五年同时接受双能X线骨密度测定和双髋关节能谱CT扫描的老年女性40例,平均年龄(68.32±9.07)岁,其中骨折组27例,未骨折组13例。将能谱CT扫描数据导入专业有限元软件,建立股骨近端三维模型。
学位
晚清民初是中国女性服装发展史中的重要时期之一,受到中国传统“重奢”文化和外来时尚“西化”风俗的双重影响[1]。其中衣襟是晚清民初女性服饰中的重要部位,注重装饰工艺的运用。该时期女装衣襟的造型结构上多样;纹样构图上,晚清比民初更饱满;主要采用的镶、滚、刺绣等装饰工艺,晚清相比民初更精湛,也成为了晚清民初服饰设计中的代表性文化符号。本文以晚清民初的女装衣襟为研究对象,首先通过史料搜集、文献调研以及实物
学位
纵观中国的经济建设历程,我国的社会主义事业建设取得了巨大进步,但是在社会经济发展的同时伴随的生态问题也日渐凸显。在面临资源趋紧与环境污染双重约束的生态形势下,保护生态环境刻不容缓。在党的十八大报告中,党高度重视生态问题,首次将美丽中国作为党的执政理念而被提出。在党的十九大报告中提出要“加快生态文明体制改革,建设美丽中国”(1),强调了生态文明建设在美丽中国建设中的重要地位。美丽中国建设的主要内容就
学位
基于生物学基本原理的烙印理论提出以后,烙印理论在管理学领域的研究不断深入,并成为行为金融学研究的范畴。该理论认为,“敏感期”给生物留下的“烙印”是深远的,并持续影响到生物未来的行为。因此,企业实际控制人过往贫困经历对其认知、价值观具有重要的影响,并将对其行为产生深远且持续性的影响。然而,当前学术界却鲜有文献从这一视角进行研究。基于此,本文以我国民营企业的实际控制人贫困经历为切入点,研究具有贫困经历
学位
当前阶段,新基建、新技术不断涌现,新业态、新模式层出不穷。信息网络加速生产各要素整合效率并实践于实体经济方方面面,不断创新制造模式、生产管理组织方式和产业体系结构,推动传统产业行业转型和数字化提升,全面释放数字经济发展的新动力。而就业是人民之根本、安定之基、发展之要和安邦之策。稳定就业增量、盘活就业存量、培养就业新动力是国民经济高质量发展的关键保障,是促进社会共同富裕的重要步骤。国家一直高度重视就
学位