搜索结果: 1-15 共查到“数学 排序问题”相关记录23条 . 查询时间(0.128 秒)
一类博弈排序问题的纳什均衡存在性证明
弈排序 纳什均衡 激活费用 成比例分配
2018/3/12
研究机器带有激活费用的博弈排序问题. 机器集由两类组成: 一类是速度为1、 激活费用为B的k_1台同型机; 另一类是速度为a(>1)、激活费用为aB的k_2台同型机,
其中k_1与k_2是任意正整数. 工件作为``局中人", 其目的是极小化自身的费用, 工件的费用是由其所在机器的负载和其所承担的激活费用组成, 其中工件承担的激活费用与工件的加工时间成正比. 针对不同的情况, 设计不同的算法, 并...
工件可自由下线最小化总完工时间的平行分批排序问题
分批排序 工件可自由下线 总完工时间
2018/3/12
考虑工件可自由下线最小化总完工时间的有界平行分批排序问题. 在该问题中, 一台平行批机器可以同时处理 b 个工件作为一个平行批, 这里b 是批容量, 一个批的加工时间等于分配给这个批的工件的最大加工时间. 关于可自由下线工件, 每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和. 也就是, 如果一个批B 有一个开工时间S, 那么包含在批B 中的每一个工件J_j 的开工时间定义为...
具有等级约束的三台机排序问题的可中断在线算法
在线排序 可中断 等级 竞争比
2014/2/5
研究具有等级约束的三台机在线排序问题. 机器和工件的等级数均为1或2，工件只能在等级数不超过自身等级的机器上加工，且加工允许中断，目标是极小化最大工件完工时间. 如果有两台机器等级为1，给出竞争比为3/2的在线算法，并证明算法是最好可能的；如果只有一台等级为1的机器，也给出竞争比为3/2的在线算法.
研究具有前瞻区间的两个不相容工件组单位工件单机无界平行分批在线排序问题. 工件按时在线到达, 目标是最小化 最大完工时间. 在无界平行分批排序中, 一台容量无限制机器可将多个工件形成一批同时加工, 每一批的加工时间等于 该批中最长工件的加工时间. 具有前瞻区间是指在时刻\ $t$, 在线算法能预见到时间区间\ $(t,t+\beta]$内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不...
工件可转包加工的排序问题研究
排序 伪多项式时间最优算法 FPTAS
2012/8/3
研究工件可以转包加工的单台机排序问题: 有$n$个工件, 在零时刻已经到达一个单台机处, 每个工件可以由加工者自有的单台机器加工或者转包给其他机器加工. 如果工件被转包加工, 那么其完工时间等于在自有机器上的加工时间, 而产生的加工费用与在自有机器上加工的费用不同. 假设被转包加工的工件的完工时间和加工费用与转包加工机器的总负载没有关系.目标函数是最小化工件最大完工时间与总加工费用的加权和. 该问...
工件可转包加工的排序问题研究
排序 伪多项式时间最优算法 FPTAS
2012/4/9
研究工件可以转包加工的单台机排序问题: 有$n$个工件, 在零时刻已经到达一个单台机处, 每个工件可以由加工者自有的单台机器加工或者转包给其他机器加工. 如果工件被转包加工, 那么其完工时间等于在自有机器上的加工时间, 而产生的加工费用与在自有机器上加工的费用不同. 假设被转包加工的工件的完工时间和加工费用与转包加工机器的总负载没有关系.目标函数是最小化工件最大完工时间与总加工费用的加权和. 该问...
工件带强制工期,指工件必须在已给定的工期内完工,不得延迟.这种环境在实际应用中随处 可见.如果工件过早提前完工,意味着工件还需要保管,将会产生额外费用.本文讨论了在单机上,加工带准备时间与强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过奇偶划分问题归约,证明了其是NP-complete的.而后,讨论了加工时间相等的特殊情形,由于工件...
文章研究加工时间仅依赖于机器的两台机自由作业排序问题 O2 | pij = pi, p2 < p1 < 2p2, Non-Idle | ΣCj。项思明和唐国春(1998)证明了可将该问题转化成指派问题。俞文ci 和应刚(1998)给出了这一问题的显式解，并用较长的篇幅证明其显式解的正确性；他们还举例说明所给出的显式最优排序并不排除其他形式的最优解的存在；但他们未说明所给出的显式解何时才是唯一最优解...
具有线性恶化效应的在线分批排序问题
分批排序 恶化效应 竞争比 在线算法
2012/8/6
本文研究一类具有线性恶化效应的单机在线分批排序问题,工件$J_j$的加工时间为$p_j=b_j+\alpha t$, 其中$b_j$为基本加工时间, $\alpha>0$为恶化率, $t$是开工时间. 工件的到达时间是未知的, 工件的基本加工时间只有在工件到达之后才能知道.多个工件可以作为一批被机器同时加工, 批的加工时间为该批中工件最大加工时间.本文对于目标为极小化makespan的批容量无限的...
有多种运输方式的供应链排序问题
排序 供应链 运输方式 承诺到货时间
2012/8/6
本文考虑了由一个制造商和多个客户组成的供应链系统。每个客户有一个订单交给制造商加工,每个订单都有一个强制交货期。工厂采用承诺到货时间的发货方式，目标是在满足客户强制交货期的情况下，合理的安排订单的加工顺序，以极小化总的运输费用。本文考虑了多种情况，分别给出了相应的算法。
两类加工时间是一般函数的单机排序问题
排序 单机 加工时间函数 依时间
2012/8/6
考虑了两类有一般加工时间函数的排序问题. 工件的加工时间分别为基本加工时间与开工时间函数、位置函数的和. 对加工时间依赖开工时间的模型，证明了一定条件下极小化最大完工时间和极小化总完工时间是多项式可解的. 对加工时间依赖开工位置的模型，给出极小化最大完工时间和极小化总完工时间的最优序，同时证明了极小化加权总完工时间的一个最优排序性质并给出一个贪婪算法.
带机器准备时间的平行机排序问题
运筹学 排序 带机器准备时间 多项式时间近似方案 全多项式时间近似方案
2010/8/31
研究了带机器准备时间的$m$台平行机排序问题，设计出了一个多项式时间近似方案(PTAS),并给出了一个机器数$m$为固定常数的情形下的全多项式时间近似方案 (FPTAS).
预知工件大小上界的平行机排序问题
排序 半在线 算法设计与分析 竞争比
2010/8/31
平行机排序问题广泛出现并应用于各领域,如通讯网信道分配的负载均衡, 大型计算中的并行计算,柔性制造系统的任务编排等等.研究了预知工件大小上界的半在线平行机排序问题.考察了仅预知工件大小上界和既预知工件大小上界又预知最优目标值的两类半在线模型.基于资源分配公平性和提高服务质量的考虑,针对每类模型都分别考察了两个目标:$C_{\rm max}$(极小化机器最大负载~makespan) 和~$C_{\r...
交货期窗口大小给定和待定情况下的单机排序问题
排序 交货期窗口 提前 延误
2009/11/19
研究有公共交货期窗口的单机排序问题,其目标是最小化提前和延误的赋权工件数.首先考虑交货期窗口大小给定的情况,进而讨论了当其大小待定且有线性时间惩罚的情形.分别给出最优排序的一些性质,根据这些性质提出了多项式时间的最优算法以最小化所有费用的和.
带磨损因子的排序问题
排序 带磨损因子
2009/10/30
本文考虑下述带磨损因子的排序问题：n个工件j，j=1,2,…,n，在同一台机器上依次加工，其所需的加工时间同它被开始加工的时间有关，越后加工其所需的加工时间越多;要求适当排列这n个工件的加工顺序，使目标函数值达最小．对加工全程、完工时间之和这两个目标函数文中给出了相应条件下的最优算法．