共查询到20条相似文献,搜索用时 375 毫秒
1.
本文考虑基于波分复用技术 (WDM)的光学网络中的排序与波长分配问题 .在波长数目固定的情况下 ,我们证明此问题是NP 困难问题 ,并且给出一个多项式时间近似方案 .若波长数目不固定 ,我们证明此问题不存在多项式时间近似方案 相似文献
2.
系列平行图上带时间约束的Steiner最小树问题 总被引:1,自引:0,他引:1
陈光亭 《高校应用数学学报(A辑)》2008,23(1):30-34
对一类特殊系列平行图上带有时间约束的Steiner最小树问题,证明了其复杂性为NPC,并给出了一个完全多项式时间近似方案. 相似文献
3.
研究的单机供应链排序问题中, 机器有一个不可用时间限制, 工件的加工时间与恶化率及其开工时间有关, 且工件的加工不可恢复. 一个或多个完工工件可组成一个发送批由车辆发送给客户, 且在机器不可用时间限制之前完工的工件必须在限制开始之时或之前完成发送. 问题的目标是最小化总发送时间与总发送费用之和. 证明问题是NP-难的, 提出了伪多项式时间的动态规划算法. 进一步, 在确定问题目标函数值的上界及下界之后, 设计了一个完全多项式时间近似方案(FPTAS). 相似文献
4.
5.
6.
本文研究一个目标是最小化最大交付时间的能分批处理的非中断单机排序问题.这个问题来源于半导体制造过程中对芯片煅烧工序的排序.煅烧炉可以看成一个能同时最多加工B(〈n)个工件的处理机.此外,每个工件有一个可以允许其加工的释放时间和一个完成加工后的额外交付时间.该问题就是将工件分批后再依批次的排序加工,使得所有工件都交付后所需的时间最短.我们设计了一个用时O(f(l/ε)n^5/2)的多项式时间近似方案,其中关于1/ε的指数函数厂(1/ε)对固定的ε是个常数. 相似文献
7.
8.
研究工件可以转包加工的单台机排序问题: 有n个工件, 在零时刻已经到达一个单台机处, 每个工件可以由加工者自有的单台机器加工或者转包给其他机器加工. 如果工件被转包加工, 那么其完工时间等于在自有机器上的加工时间, 而产生的加工费用与在自有机器上加工的费用不同. 假设被转包加工的工件的完工时间和加工费用与转包加工机器的总负载没有关系.目标函数是最小化工件最大完工时间与总加工费用的加权和. 该问题已经被证明是NP-难的. 最后给出该问题的伪多项式时间最优算法, 并且提出一个完全多项式时间近似方案(FPTAS). 相似文献
9.
本文考虑极小化最大完工时间的单机分批加工问题.设有n个工件和一台批加工机器.每个工件有一个释放时间和一个加工时间.批加工机器可以同时加工b(b相似文献
10.
本文考虑了机器具有不可用区间且工件可拒绝下的单机重新排序问题,在该问题中,给定一个工件集需在一台机器上加工,每个工件有自己的加工时间和权重,且对该工件集目标函数为极小化总加权完工时间的排序计划已给定,根据该排序计划中每个工件的完工时间已确定每个工件的承诺交付时间。然而,在工件正式开始加工前,原计划用于加工的某段时间区间因临时用于检修机器而导致机器在该时间区间不再可用,需要对工件重新排序。为了确保在新的重新排序中,工件的延误成本不致太大,决策者可以选择拒绝部分工件,但需支付相应的拒绝费用。任务是确定接受工件集和拒绝工件集,并将接受的工件在考虑机器具有不可用区间的条件下重新排序使得接受工件集的总加权完工时间,总拒绝费用及赋权最大延误之和最小。该问题是NP-困难的,对此给出了伪多项式时间动态规划精确算法,利用稀疏技术设计了完全多项式时间近似方案。 相似文献
11.
12.
In this paper, we consider the single machine scheduling problem with release dates and rejection. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on the machine. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. We show that the problem is NP-hard in the ordinary sense. Then we provide two pseudo-polynomial-time algorithms. Consequently, two special cases can be solved in polynomial-time. Finally, a 2-approximation algorithm and a fully polynomial-time approximation scheme are given for the problem. 相似文献
13.
F. Zeynep Sargut 《Operations Research Letters》2007,35(4):549-557
We study a new class of capacitated economic lot-sizing problems. We show that the problem is NP-hard in general and derive a fully polynomial-time approximation algorithm under mild conditions on the cost functions. Furthermore, we develop a polynomial-time algorithm for the case where all cost functions are concave. 相似文献
14.
15.
In this paper, we propose a fully polynomial-time randomized approximation scheme (FPRAS) for a closed Jackson network. Our
algorithm is based on the Markov chain Monte Carlo (MCMC) method. Thus our scheme returns an approximate solution, for which
the size of the error satisfies a given bound. To our knowledge, this algorithm is the first polynomial time MCMC algorithm
for closed Jackson networks with multiple servers. We propose two new ergodic Markov chains, both of which have a unique stationary
distribution that is the product form solution for closed Jackson networks. One of them is for an approximate sampler, and
we show that it mixes rapidly. The other is for a perfect sampler based on the monotone coupling from the past (CFTP) algorithm
proposed by Propp and Wilson, and we show that it has a monotone update function. 相似文献
16.
Mikhail A. Kubzin Vitaly A. Strusevich 《4OR: A Quarterly Journal of Operations Research》2005,3(4):303-313
We study a two-machine flow shop scheduling problem with no-wait in process, in which one of the machines is subject to mandatory
maintenance. The length of the maintenance period is defined by a non-decreasing function that depends on the starting time
of that maintenance. The objective is to minimize the completion time of all activities. We present a polynomial-time approximation
scheme for this problem.
Received: November 2004 / Received version: March 2005
AMS classification:
90B35, 90B30, 90C59
The research was partly supported by INTAS (Project 03-51-5501)
All correspondence to: Vitali A. Strusevich 相似文献
17.
We consider the problem of scheduling a set of jobs with different release times on parallel machines so as to minimize the makespan of the schedule. The machines have the same processing speed, but each job is compatible with only a subset of those machines. The machines can be linearly ordered such that a higher-indexed machine can process all those jobs that a lower-indexed machine can process. We present an efficient algorithm for this problem with a worst-case performance ratio of 2. We also develop a polynomial time approximation scheme (PTAS) for the problem, as well as a fully polynomial time approximation scheme (FPTAS) for the case in which the number of machines is fixed. 相似文献
18.
Paat Rusmevichientong Zuo-Jun Max Shen David B. Shmoys 《Operations Research Letters》2009,37(4):230-238
Motivated by an application in assortment planning under the nested logit choice model, we develop a polynomial-time approximation scheme for the sum-of-ratios optimization problem with a capacity constraint and a fixed number of product groups. 相似文献
19.
Jia-quanGao 《计算数学(英文版)》2004,22(1):55-60
A practical parallel difference scheme for parabolic equations is constructed as follows: to decompose the domain Ω into some overlapping subdomains, take flux of the last time layer as Neumann boundary conditions for the time layer on inner boundary points of subdomains, solve it with the fully implicit scheme on each subdomain, then take correspondent values of its neighbor subdomains as its values for inner boundary points of each subdomain and mean of its neighbor subdomain and itself at overlapping points. The scheme is unconditionally convergent. Though its truncation error is O(τ h), the convergent order for the solution can be improved to O(τ h2). 相似文献
20.
Yongyong Cai & Yan Wang 《数学研究》2020,53(2):125-142
We consider the nonlinear Dirac equation (NLD) with time dependent external electro-magnetic potentials, involving a dimensionless parameter $ε\in(0,1]$ which is inversely proportional to the speed of light. In the nonrelativistic limit regime $ε\ll1$ (speed of light tends to infinity), we decompose the solution into the eigenspaces associated with the 'free Dirac operator' and construct an approximation to the NLD with $O(ε^2)$ error. The NLD converges (with a phase factor) to a coupled nonlinear Schrödinger system (NLS) with external electric potential in the nonrelativistic limit as $ε\to0^+$, and the error of the NLS approximation is first order $O(ε)$. The constructed $O(ε^2)$ approximation is well-suited for numerical purposes. 相似文献