需要安装时间的平行多功能机排序问题的启发式算法

考虑需要安装时间的平行多功能机排序问题。在该模型中,每个工件对应机器集合的一个子集,其只能在这个子集中的任一台机器上加工,称这个子集为该工件的加工集合;工件分组,同组工件具有相同的加工时间和加工集合,不同组中的工件在同一台机器上连续加工需要安装时间,目标函数为极小化最大完工时间。对该问题NP-难的一般情况设计启发式算法:首先按照特定的规则将所有工件组都整组地安排到各台机器上,然后通过在各机器间转移工件不断改进当前最大完工时间。通过与下界的比较检验算法的性能,大量的计算实验表明,算法是实用而有效的。     

无限批量调度中最小化加权完工时间和问题的一个线性时间近似方案

本文考虑n个工件的无限批量机器调度问题．一台机器可以同时加工B≥n个工件．每个工件具有一个正权因子、一个释放时间和一个加工时间．一个批次的加工时间是该批次所包含所有工件的加工时间的最大者．在同一批次中加工的工件有相同的完工时间，即它们的共同开始时间加上该批次的加工时间．对于最小化加权完工时间和问题，本文给出了第一个多项式时间近似方案(PTAS)．对任意给定精度，该算法的运行时间为线性的．     

单位工件的平行机并行分批在线排序问题的算法

本文研究一类批容量有界的并行分批、平行机在线排序问题。模型中有n个相互独立的工件J={J₁,…,J_n}要在m台批处理机上加工。批处理机每次可同时加工至多B(Bj(1≤j≤n)的到达时间为r_j,加工时间为1,工件是否会到达事先未知,而只有等到工件的到达时间才能获知它的到达。目标为最小化工件的最大完工时间。针对该排序问题,本文设计了两个竞争比均达到最好可能的在线算法。     

平行机中关于关于同类机近似算法的研究

我们考虑平行机排序问题中的这样一类:机器两台,类型一样,但效率不同.其中n个工件在第一台机器上的加工时间分别为p1,p2,…,Pn,在第二台机器上的加工时间分别为αρ1,αρ2,…,αρn,其中0<α≤1.每台机器上的工件总数不受限制.n个工件的权分别为w1,w2,…,wn,我们的目标是如何在这两台机器上安排这n个工件以及如何确定每台机器上工件加工的先后顺序,使得这n个工件的完工时间的总权和 达到最小.该问题记为 .对于这个问题,我们给出一个1.1755近似算法.     

一致条件下具学习因子的几个单机排序问题

n个工件需在同台机器上依次加工，工件j,j=1，2，…，n所需的正常加工时间为pj,如在某序中工件j第r个加工，则机器对其实际加工的时间为pjr^α，其中α≤0为一学习因子．要求适当排列这n个工件的加工顺序，使某目标函数达最小．本文对加权完工时间之和，最大迟后，延误工件数这三个目标函数，给出了在相应的一致条件下，对应的WSPT规则，EDD规则，修正Moore-Hodgson算法可获最优序，并估计了在一般情况下由该三规则所获序的误差．     

具有学习效应的两台机上最优混合流水作业算法

研究相同工件在两台机器（分别称为机器M₁和M₂）上的混合流水作业问题,每个给定工件有两个任务,分别称之为任务A和任务B,任务B只能在任务A完工后才能开始加工,每个工件有两种加工模式供选择：模式1是将两个任务都安排在机器M₂上加工;模式2是将任务A和B分别安排在机器M₁和M₂上加工.假设在加工工件时,机器具有学习效应,即工件的实际加工时间与工件的加工位置有关.目标函数是最小化最大完工时间.分别讨论了具有无缓冲区与无限缓冲区两种加工环境情况,两种情况下都得到了最优算法.     

工件加工时间随加工顺序变动的单机排序问题

本文讨论了一类工件加工时间随加工顺序而变的单机排序问题,在目标函数sum from i=1 to nC_i与Lmax下,Smith法则与Jackson法则仍然成立。从而推广了Smith与Jackson的结果。一般所考虑的单机排序问题是:有n个工件需要在一台机器上加工,而该机器只能一次加工一个工件,且工件j在该机器上所需的加工时间为P_i,这里P_j为一常量,即与工件早加工或晚加工无关。现在需要确定工件加工的一个顺序,使得在不同的目标下最优。     

极小化最大提前完工时间的两平行机排序问题

讨论了在两台同型平行机上,加工带截止期限的n个工件,在机器可空闲条件下,确定一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,问题可能会无可行排序.先讨论问题的可行性,通过子集和问题归约,证明了判定问题的可行性是NP-complete的.如果问题可行,接着讨论了问题的复杂性,通过划分问题归约,证明了其是NP-complete的.最后,考虑了工件加工时间相等的特殊情形,提出了一个算法在多项式时间内获得最优排序.     

关于第二类Zagreb指数猜想的一个证明

设G是一个n阶简单图.G的第二类Zagreb指数定义为M₂(G)=■d_id_j.其中d_i表示顶点i的度.Xu等(2014)提出了一个关于第二类Zagreb指数的猜想:在所有阶数为n、边数为m的图中,M₂(G)最大的图是拟完全的.借助于门槛图的Ferrers表的性质,本文将上述猜想转化为组合矩阵论优化问题,并给出该猜想的一个代数证明.     

极小化最大完工时间的单机分批加工问题

本文考虑极小化最大完工时间的单机分批加工问题．设有n个工件和一台批加工机器．每个工件有一个释放时间和一个加工时间．批加工机器可以同时加工b(b相似文献   

5-正则图的全控制数的一个注记

设G是不含孤立点的图,S是G的一个顶点子集,若G的每一个顶点都与S中的某顶点邻接,则称S是G的全控制集.G的最小全控制集所含顶点的个数称为G的全控制数,记为γt(G).Thomasse和Yeo证明了若G是最小度至少为5的n阶连通图,则γt(G)≤17n/44.在5-正则图上改进了Thomasse和Yeo的结论,证明了若G是n阶5-正则图,则,γt(G)≤106n/275.     

两台带服务等级的可拒绝同型机排序问题的在线算法

两台同型机M_1,M_2, 加工速度一致, 但拥有不同的加工能力,用其服务等级表示, M_1的服务等级为1, M_2的服务等级为2. 工件j按列表在线到达,每个工件带有三个参数: 长度t_j,等级g_j=1或2, 罚值p_j. 当j到达时, 可以被拒绝, 但要付出相应的罚值p_j, 也可以被接受并分配给服务等级不超过该工件等级的机器加工,事实上等级为1的工件只能分给M_1加工, 等级为2的工件可以分给M_1或M_2加工, 加工不允许中断. 目标为极小化加工工件集的最晚完工时间(makespan)和拒绝工件集的总罚值之和. 对于该问题给出了一个在线算法, 其竞争比为11/6, 以及问题一个下界5/3.     

工件有到达时间及可拒绝下的同类平行机排序问题的近似算法

本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$时, 该算法近似比为3, 当接受工件个数小于$(m-1)$时, 该算法近似比为$(2+\rho)$, 其中$\rho$为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。     

关于平行机排序问题的两点注记

本文考虑了有完工约束的平行机排序问题,证明了问题 pm|T|∑c_i是 NP-完全的,而对问题 pm|T,[_i≡p|∑w_ic_i 提出 O(n~2)的算法,并证明其最优性.将 n 个互相独立的工件(工件集 N={1,2,…,n))放在 m 台等速率平行机(机器M={M_i,…,M_m})上加工.已知每个工件必须且仅须在一台机器上加工一次,并且加工时不允许中断.工件 i(i∈N)在不同机器上加工时间不变,设为 p_i,罚权 w_i 也与机器无关,p_i 和 w_i 皆为非负实数.我们将多台机器加工工件的一个安排称为一个时间表.当时间表π确定后,记工件 i 的完工时间为 c_i(π     

工件有到达时间及可拒绝下的同类平行机排序问题的近似算法

本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$时, 该算法近似比为3, 当接受工件个数小于$(m-1)$时, 该算法近似比为$(2+\rho)$, 其中$\rho$为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。     

带两个服务等级的三台机最优在线算法

研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法.     

带运输机的流水车间调度的最优算法

研究带运输时间的流水调度:在该问题中有两台机器A,B和一个运输机V,n个工件,工件需要先在机器A上加工然后在机器B上加工最后被运输机V运往目的地,而且运输机V最初停在机器B旁边.模型的目标是使所有工件都运往目的地的时间最短.文中给出了三种情况下的最优调度算法:i)A,B机器加工工件顺序给定时我们给出了线性时间的最优算法;ii)所有的工件加工时间在机器B上时间相等时我们给出了时间复杂度为O(nlogn)的最优算法;iii)机器B上工件最短加工时间大于等于机器A上工件最长加工时间时给出了时间复杂度为O(n~2)的最优算法.     

极小化总完工时间的同时加工排序

讨论了并行工件同时加工排序问题,即n个同时到达的工件在m台批处理机上排序的问题.批处理机一次最多能加工B个工件.每批的加工时间等于该批中所含工件的加工时间的最大者.主要考虑B n的特殊情况,即每批可包含任意多个工件,目标函数是极小化总完工时间.首先对同型批处理机的情况给出了动态规划算法,算法的运行时间为O(m nm+1),并进一步将结论推广到同类批处理机的情况.     

小直径单圈与双圈图的Mostar指标与不规则度的差（英文）

任给一个连通图,高芳等人首先引进了G的一个不变量?M(G)=M_o(G)-irr(G),并提出一个问题:怎样确定所有含n个顶点的连通图G的?M(G)的极值,其中M_o(G)和irr(G)分别表示G的Mostar指标和不规则度.本文针对这个问题,刻画所有直径为3的单圈图和双圈图G的?M(G)的上界,并给出它们的极图.     

带强制工期的双机开放车间排序问题

讨论了强制工期相等的n个工件在双机开放车间加工.在允许机器空闲的条件下,寻找一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,同题可能会无可行排序.先讨论了问题的可行性.如果问题可行,找出一个可行序列作为预排序列,并提出了一个算法计算每个工件尽可能迟的开工时间.而后,提出了一个多项式时间最优算法,在预排序列的基础上,通过调整两台机器上最先加工的工件来获得最优排序.