检索结果-南通市图书馆

子集和问题的一个伪多项式时间算法

引用

通信学报 1992年第2期13卷 52-58页

作者：胡学林北京海燕新技术开发中心北京100091

提出了一个求解子集和问题的伪多项式时间算法,该算法可有效地求解很大一类密度d(A)>1的子集和问题。

关键词：组合论子集和问题伪多项式算法

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

机器有不可用时间段的可拒绝排序问题

机器有不可用时间段的可拒绝排序问题

引用

作者：池晶晶曲阜师范大学

学位级别：硕士

由于实际生产的需要,机器可能有些时间段不能工作,所以机器有不可用时间段的排序问题被广泛应用到各个领域.不仅如此,生产商开始对工件进行选择,他们尽量选择一些能给企业带来更大收益的工件进行生产,同时拒绝加工耗时长而又收益小的工... 详细信息

由于实际生产的需要,机器可能有些时间段不能工作,所以机器有不可用时间段的排序问题被广泛应用到各个领域.不仅如此,生产商开始对工件进行选择,他们尽量选择一些能给企业带来更大收益的工件进行生产,同时拒绝加工耗时长而又收益小的工件,或者将拒绝的工件外包给其他企业进行生产.当然,机器并不是一直可用的,比如工人有自己的上班时间,机器需要维修或者保养,那么在工人休息时间或者机器维修保养、更换零件的时间,是不允许加工工件的,而且根据具体需要,工件的加工时间可遵循恶化效应.作为供应链的一部分,制造商不仅需要加工工件,而且完工工件需要被尽快运输到客户,可以选择第三方物流企业帮助运输.总之,随着时代的发展和实际生产生活的需要,如何合理接受工件、安排接受工件的生产、组织工件运输、分批运输以提高客户的服务水平,同时极小化工件的配送时间,这一问题已得到更多关注.文章结构安排如下:第一章主要介绍了排序问题的基本知识、主要概念以及组合优化中的基本常识,而且简要介绍了机器有不可用时间段的排序问题、可拒绝排序问题以及供应链排序问题的基本概念,最后简单说明了一下该问题的研究现状以及本文的主要成果.第二章研究了两台机器,其中一台机器有一个固定不可用时间段的可拒绝排序问题,工件可以接受并在机器上加工或者拒绝加工,目标是极小化接受工件的最大时间表长与拒绝工件的拒绝费用之和,主要有以下两个模型:(1)工件加工不可恢复,通过动态规划算法最优地解决该问题;(2)工件加工可恢复,本节给出了伪多项式动态规划算法.第三章考虑了m台平行机,每台机器有一个固定不可用时间段的可拒绝排序问题,主要有以下两个模型:(1)机器加工不可恢复,生产商可以选择接受并加工工件,也可以选择拒绝或将工件外包,会产生一定的拒绝费用,目标是极小化接受工件的总完工时间以及拒绝工件的总拒绝费用之和,通过动态规划算法得到问题最优解;(2)机器加工不可恢复,对工件可以进行选择性加工,工件的加工时间是开工时间的简单线性函数,目标是极小化接受工件的总加权完工时间与拒绝工件的总拒绝费用之和.文中给出了一个伪多项式动态规划算法.第四章研究了单机生产的排序问题,机器上有一个固定不可用时间段,工件加工允许拒绝,完工工件需运输到同一个客户,本章主要考虑了以下三个模型:(1)单机生产,工件加工允许拒绝,不可用时间段之前未完工的工件,在之后可以继续加工,工件的加工时间是其基本加工时间和开工时间的线性函数,完工工件需要批运输到同一客户,运输车辆无限,车容量有限,目标是极小化最后一批工件配送到客户的时间、运输费用与拒绝工件的拒绝费用之和,本节给出了伪多项式动态规划算法及其复杂性;(2)单机生产,机器上有一个不可用时间段,在这个时间段之前未完工的工件,在其后可以继续加工,工件加工允许拒绝,完工工件需要批运输到同一个客户,运输车辆无限,车容量有限,目标是极小化接受工件的总配送时间、运输费用与拒绝工件总拒绝费用之和,通过动态规划算法得到该问题的最优解;(3)单机生产,机器上有一个不可用时间段,工件加工可恢复,允许拒绝,完工工件单个立即运输,车辆无限,车容量为1,每个工件有一个交货期,目标是极小化最大延误时间、运输费用与拒绝工件的拒绝费用之和.本节给出了伪多项式动态规划算法.

关键词：排序不可用时间段配送伪多项式动态规划算法拒绝

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：