检索结果-南通市图书馆

一个可拒绝分批排序的NP-困难性及其fptas算法

在线全文

学校读者我要写书评

暂无评论

一个可拒绝分批排序的NP-困难性及其FPTAS算法

作者：常慧曲阜师范大学

学位级别：硕士

一直以来,排序理论都是组合优化领域的一个热门方向,有着坚实的理论背景和深刻的实际意义,它产生的主要背景是机器制造,后来被广泛应用于计算机科学、管理科学、工农业生产、交通运输等许多领域。从普通的生产部门的计划安排、人员调度... 详细信息

一直以来,排序理论都是组合优化领域的一个热门方向,有着坚实的理论背景和深刻的实际意义,它产生的主要背景是机器制造,后来被广泛应用于计算机科学、管理科学、工农业生产、交通运输等许多领域。从普通的生产部门的计划安排、人员调度,学校课程表的制定,到宇宙飞船的复杂庞大的飞行计划,都要用到排序的理论和算法。从50年代起,人们就一直努力于排序问题理论与实践的研究,已经取得了许多有意义的成果。可拒绝排序和分批排序都是比较新颖的现代排序模型,本文主要讨论了这两个模型,做了以下一些工作。论文共分三章。第一章首先介绍了排序问题的应用背景及表示形式,接着给出了必要的预备知识,简单介绍了本文涉及的基本定义和定理,最后概述了本文研究的主要问题以及研究成果。第二章主要考虑了工件带有拒绝费用的排序问题：可拒绝的排序问题是近年来出现的一类新型排序问题,为了满足现实需要,在加工时需要进行更高的决策,拒绝某些工件的加工,并支付一定的拒绝费用。在这一章中我们首次考虑了目标函数为极小化最大延误(最大延迟)与被拒绝工件的惩罚费用之和的单机无界平行批排序问题,利用二划分问题证明了问题1|B≥n,rej|Tmax+TCP为NP-困难的。第三章继续讨论问题1|B≥n,rcj|Tmax+TCP,给出了一个基于动态规划的O(n2∑u(?))时间的伪多项式时间算法,接着给出了2-近似算法和fptas.最后在本文证明的基础上,对目标函数是Lmax的情况进行了简单的讨论。

关键词：可拒绝排序分批排序最大延误最大延迟动态规划 fptas

Parallel-batch scheduling with deterioration and rejection on a single machine

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

Applied Mathematics(A Journal of Chinese Universities) 2020年第2期35卷 141-156页

作者： LI Da-wei LU Xi-wen School of Science East China University of Science and TechnologyShanghai 200237China.

The single machine parallel-batch scheduling with deteriorating jobs and rejection is considered in this paper.A job is either rejected,in which a rejection penalty should be paid,or accepted and processed on the machine.Each job’s processing time is an increasing linear function of its starting time.The machine can process any number of jobs simultaneously as a batch.The processing time of a batch is equal to the largest processing time of the jobs in the batch.The objectives are to minimize the makespan and the total weighted completion time,respectively,under the condition that the total rejection penalty cannot exceed a given upper bound Q.We show that both problems are NP-complete and present dynamic programming algorithms and fully polynomial time approximation schemes(fptass)for the considered problems.

关键词： parallel-batch scheduling rejection deterioration fptas NP-complete

带到达时间的加工时间离散可控的单机排序问题1|r_j,dm|C_(max)+TPC的fptas算法

在线全文

学校读者我要写书评

暂无评论

洛阳大学学报 2006年第4期21卷 39-42页

作者：周瑞扬曹志刚张玉忠曲阜师范大学运筹与管理学院山东日照276826

考虑工件加工时间离散可控的单机分批排序问题,目标函数是极小化最大完工时间与加工费用之和.对于工件不同时到达的情况,本文给出了fptas算法.

关键词：离散可控到达时间最大完工时间 fptas

基于背包问题算法的中长期电力合同签约优化问题

在线全文

学校读者我要写书评

暂无评论

电力设备管理 2022年第19期 301-303页

作者：屈源广东大唐国际电力营销有限公司

根据中长期合同签约中的总量限制问题,建立有效的数学模型。引入背包问题的伪多项式时间复杂度算法,给出合理的解决方案,并从近似度、复杂度等方面对方案进行评估。

关键词：中长期合同背包问题算法 fptas 时间复杂度近似度

具有退化工件和老化效应的单机可拒绝排序问题

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

运筹与管理 2017年第6期26卷 95-101页

作者：刘春来王建军大连理工大学管理与经济学部辽宁大连116023

研究同时具有退化工件和老化效应的单机可拒绝排序问题,即工件的实际加工时间是与其开工时间和所在位置有关的函数,同时生产商可以通过支付一定的处罚费用而拒绝加工某些工件。在生产加工过程中,考虑对机器进行选择性维修活动来提高加... 详细信息

研究同时具有退化工件和老化效应的单机可拒绝排序问题,即工件的实际加工时间是与其开工时间和所在位置有关的函数,同时生产商可以通过支付一定的处罚费用而拒绝加工某些工件。在生产加工过程中,考虑对机器进行选择性维修活动来提高加工的效率;机器进行维修活动后将恢复到初始状态,老化效应也将重新开始。目标是确定拒绝哪些工件、何时进行维修活动以及接受工件集中工件的次序,以便极小化接受加工工件的最大完工时间与拒绝加工工件总处罚费用的和。证明得到了所研究的问题是NP-难解的,并给出了解决问题的一个全多项式时间近似方案(fptas)算法。

关键词：单机排序拒绝维修活动 fptas

在线全文

学校读者我要写书评

暂无评论

工件可转包加工的排序问题研究

运筹学学报 2012年第1期16卷 121-126页

作者：仲维亚刘晓蕾霍志明上海大学理学院数学系上海200444

研究工件可以转包加工的单台机排序问题:有n个工件,在零时刻已经到达一个单台机处,每个工件可以由加工者自有的单台机器加工或者转包给其他机器加工.如果工件被转包加工,那么其完工时间等于在自有机器上的加工时间,而产生的加工费用与... 详细信息

研究工件可以转包加工的单台机排序问题:有n个工件,在零时刻已经到达一个单台机处,每个工件可以由加工者自有的单台机器加工或者转包给其他机器加工.如果工件被转包加工,那么其完工时间等于在自有机器上的加工时间,而产生的加工费用与在自有机器上加工的费用不同.假设被转包加工的工件的完工时间和加工费用与转包加工机器的总负载没有关系.目标函数是最小化工件最大完工时间与总加工费用的加权和.该问题已经被证明是NP-难的.最后给出该问题的伪多项式时间最优算法,并且提出一个完全多项式时间近似方案(fptas).

关键词：排序伪多项式时间最优算法 fptas

在线全文

学校读者我要写书评

暂无评论

极小化加权总完工时间的工件可拒绝排序

重庆师范大学学报（自然科学版） 2012年第5期29卷 10-12页

作者：张树霞张峰镇江船艇学院船艇指挥系江苏镇江212003 上海第二工业大学理学院上海201209

经典的排序问题要求工件都必须进行加工,然而在实际中有时候由于一些特殊的原因可以考虑工件不加工。例如,加工时间非常大,或加工所需费用非常高,于是就不加工这一工件,而是通过支付一定的费用后送到外边"外加工"或购买更合算,这类问题... 详细信息

经典的排序问题要求工件都必须进行加工,然而在实际中有时候由于一些特殊的原因可以考虑工件不加工。例如,加工时间非常大,或加工所需费用非常高,于是就不加工这一工件,而是通过支付一定的费用后送到外边"外加工"或购买更合算,这类问题称为工件可拒绝排序问题。需要研究的任务是怎样选择工件在机器上进行加工或拒绝,并且如何安排被接受加工工件的加工次序使给定的目标函数值最优。本文研究了工件可拒绝排序中,目标函数是有限的总惩罚费用(总惩罚费用约束下)极小化加权总完工时间,工件到达时间都相同的同型机问题,设计了伪多项式时间的动态规划算法,并给出了相应的fptas算法。

关键词：可拒绝排序动态规划 fptas

在线全文

学校读者我要写书评

暂无评论

工件可拒绝排序问题综述

运筹学学报 2020年第2期24卷 111-130页

作者：张玉忠曲阜师范大学运筹学研究院山东日照276826

可拒绝排序问题是兴起于2000年前后的有代表性、应用背景极强的的排序问题,是经典排序问题的衍生和推广.经典排序问题总是要求每个工件必须被加工,然而在实际中由于某些特殊原因,决策者会选择拒绝加工某些工件.把允许工件被拒绝的这类... 详细信息

可拒绝排序问题是兴起于2000年前后的有代表性、应用背景极强的的排序问题,是经典排序问题的衍生和推广.经典排序问题总是要求每个工件必须被加工,然而在实际中由于某些特殊原因,决策者会选择拒绝加工某些工件.把允许工件被拒绝的这类问题称为工件可拒绝排序问题,有的文献称之为外包的排序问题.这些问题不仅具有很强的应用价值,在理论上也有重要的意义.近年来该领域受到越来越广泛的关注,新的研究成果不断涌现.现就离线、在线情况下的可拒绝排序问题的进展情况作了全面介绍,展示了已有的研究成果和新的问题,给出了此方面的比较重要的参考文献,旨在帮助感兴趣的读者迅速了解问题研究的进展并由此进入此研究领域的前沿.

关键词：可拒绝排序在线排序离线排序近似算法复杂性竞争比 NP-难 PTAS fptas

工件加工可拒绝的无界批量分批排序问题的几点探讨(英文)

在线全文

学校读者我要写书评

暂无评论

运筹学学报 2009年第3期13卷 23-30页

作者：张咸昭蔡增霞任剑锋临沂师范学院数学系临沂276005 曲阜师范大学运筹与管理学院日照276826

本文对两个加工可拒绝的无界批量分批排序问题1|B≥n,rej|∑w_jT_j+TP和1|B≥n,rej|∑w_jU_j+TP进行了研究,对这两个问题分别给出了伪多项式时间算法和(fptas)近似算法.目前为止它们都是比较好的精确算法和近似算法.

关键词：运筹学可拒绝 NP-困难伪多项式时间 fptas